[問題]整除問題(2)

[問題]整除問題(2)

galaxylee 於 星期三 九月 14, 2005 12:08 am


令m,n為任意一對整數,1≦n≦m,d=gcd(m,n)--m,n的最大公因數,C(m,n)=m!/[n!(m-n)!],
證明:d*C(m,n)/m 是一個整數。
(91年全國高中數學能力競試屏東區)

galaxylee
副教授
副教授
 
文章: 555
註冊時間: 2005-07-18

chanjunhong 於 星期五 九月 16, 2005 12:34 pm


想到了,其實不會很難
theorem1:
C(m,n)都是整數  for all m ,n。
可用連續k個整數相乘,都是k的倍數 ,及數學歸納法證明。

theorem2:
C(m,n)=C(m-1,n-1)*m/n。
展開可知

theorem3:
d=(m,n)則存在兩整數s,t使得sm+tn=d
忘了,請自行翻書

so,start:
因為d=(m,n),所以存在兩整數s,t使得sm+tn=d
d/m=(sm+tn)/m=s+t*(n/m),
so d*C(m,n)={s+t*(n/m)}*C(m,n)
                  =s*C(m,n)+t*(n/m)*C(m,n)
                  =s*C(m,n)+t*(n/m)*(m/n)*C(m-1,n-1)
                  =s*C(m,n)+t*C(m-1,n-1) 是整數(整數乘法的封閉性)QED

建議:有人想試階層的標準分解證嗎?(這是我想到的第二個證法)
想法上是可以證,但是有點難敘述。

chanjunhong
實習生
實習生
 
文章: 93
註冊時間: 2005-07-25






代數學