數論挑戰1(已解決)

傲月光希

請將每一題以完整且詳細的證明列出，完整答對可得3聲望
一回覆限一題，解法不定，不同人的解法必須些許不同

1.設a_1,a_2,...,a_(n+1)是不超過2n的正整數，則必有i≠j，1≦i,j≦n+1，使(a_i)|(a_j)
2.設p為質數，1≦k≦p-1，則p|C(p,k)
3.若n是大於9的奇合數，則(n^2)|(n-1)!

[ 本文最後由 傲月光希 於 07-12-13 04:54 PM 編輯 ]

M.N.M.

2.

C(p，k)=p*(p-1)*...*(p-k+1)*(p-k)*...*1/[k!(p-k)!]=p*(p-1)*...*(p-k+1)/k!

因為1≦k≦p-1時，(p,k!)=1

所以k!│(p-1)...(p-k+1)

所以p│C(p，k)

[ 本文最後由 M.N.M. 於 07-11-24 10:48 PM 編輯 ]

‧幻星〞

1.設a_1,a_2,...,a_(n+1)是不超過2n的正整數，則必有i≠j，1≦i,j≦n+1，使(a_i)|(a_j)

設集合
S1={1,1*2,1*2^2,...,1*2^(a1)}
S2={3,3*2,3*2^2,...,3*2^(a2)}
...
Sn={2n-1,(2n-1)*2,(2n-1)*2^2,...(2n-1)*2^(an)}
其中a1,a2,..,an滿足條件(2n-1)*2^(ai)<=2n<(2n-1)*2^(a(i+1))
則每一個集合內任兩個元素符合大的數被小的整除
而S1+S2+..+Sn={x|x屬於N,x≦2n}
而n+1個數在這n個集合之中
必有一個集合會有兩個數
而這兩個數必有一個數可以整除另一個數
得證

[ 本文最後由 ‧幻星〞 於 07-11-24 02:23 PM 編輯 ]

傲月光希

解答

3.若n是大於9的奇合數，則(n^2)|(n-1)!

假設n=ab，這邊能分成兩種情況
case 1：a≠b
因為n是大於9的奇合數，所以可以不失一般性假設a≧3，b≧5，2不整除a跟b
利用除法原理
存在整數q1，r1，q2，r2滿足
n-1=aq1+r1，n-1=bq2+r2，0≦r1<a，0≦r2<b
先說目的，因為n^2=(a^2)(b^2)，因此我們只要在1、2、...、n-1之中有兩個a倍數跟兩個b倍數的整數，其(n-1)!就可以被n^2整除
=> n=aq1+(r1+1)=bq2+(r2+1)
因為n可被a跟b整除，所以r1+1≡0 (mod a)且r2+1≡0 (mod b)
=> r1=a-1，r2=b-1
=> n-1=aq1+(a-1)，n-1=bq2+(b-1)
=> q1=(n-a)/a，q2=(n-b)/b
=> q1=(n-a)/a=(ab-a)/a≧(5a-a)/a=4，因此n-1中至少有4個a的倍數----(*)
q2=(n-b)/b=(ab-b)/b≧(3b-b)/b=2，因此n-1中至少有2個b的倍數
所以可以得到(n^2)|(n-1)!
case 2：a=b
可以不失一般性假設a≧5
也是利用同case 1的過程，最後會得到(*)的結果，n-1除以a的商至少有4
所以(n^2)|(n-1)!