好像是一道简单的高中题目

282842712474

n是一个正整数，$a_1,a_2,...,a_k(k>=2)$是{1,2,…,n}中的不同整数，并且n整除$a_i(a_{i+1}-1)$对于所有i=1,2,…,k-1都成立， 证明：$a_k(a_1-1)$不能被n整除。

nlrte13

高中时候真没做过这么“简单”的题目啊。。。。

nlrte13

可以反证^^
首先容易得到a1不等于1，
若 ak(a1-1)能被n整除，则
(a1-1)(a2-1).....(ak-1)(a1)(a2)(ak)能被n^k整除
即在{2, 6, 12, 20, 30, ..., n(n-1) }中取k个不同的数相乘，结果能被n^k整除，显然这是不可能的。

mathe

证明错误
比如n=6,k=3,
{1*2,2*3,3*4,4*5,5*6}中我们可以选择(2*3),(3*4),(5*6)这三个数,它们乘积可以被6^3整除

nlrte13

证明错误 比如n=6,k=3, {1*2,2*3,3*4,4*5,5*6}中我们可以选择(2*3),(3*4),(5*6)这三个数,它们乘积可以被6^3整除 mathe 发表于 2009-7-29 21:37

mathe哥说的对^^

nlrte13

{
1, 2, 3, 4, 5, 6...
2, 4, 6, 8, 10, 12...
3, 6, 9, 12, 15, 18...
4, 8, 12, 16, 20, 24...
5, 10, 15, 20, 25, 30...
6, 12, 18, 24, 30, 36...
...................................
}
要选择不同行也不同列的k个

ztfreedom

反证：
若n|(A1-1)*Ak,
则有：n^k|A1*A2*...*Ak*(A1-1)*(A2-1)*...*(Ak-1)（*）
易知：若一个正整数a<=n,则如果(n,a)<>1,则(n,a-1)=1
从而在A1,A1-1,A2,A2-1,...Ak,Ak-1中至多有k个数与n不互质，而且这k个数显然都<=n,则易见（*）式不可能成立
mathe说的那个反例好像不满题中条件吧，不满足并且n整除Ai*(Ai+1-1)对于所有i=1,2,…,k-1都成立

mathe

则如果(n,a)<>1,则(n,a-1)=1
--------------------------------------------
这也个是错误的，如n=6,a=3,(n,a)=3,(n,a-1)=2

至于反例不满足题目的条件，这个是自然的，不然题目就错了。反例说的是前面证明的方法不对。

medie2005

mathe哥？ 呵呵，这个称呼有点猫扑的味道。

ztfreedom

呵呵，那个证明有点随意了。
改一个地方：若一个正整数a<=n,则如果(n,a)=d1,(n,a-1)=d2,则d1*d2<=n
因为d1|n,d2|n,(d1,d2)=1,则d1*d2|n,从而d1*d2<=n,这个应该就对了吧
这样(A1*(A1-1),n)=d1*d2<=n,且易见对与k>=2，必存在i,1<=i<=k,s.t.(Ai*(Ai-1),n)<n,从而原证明的(*)成立