證明正整數等差數列必有某項是73的倍數(公差非73的倍數)

Question

有一等差數列，首項和公差都是正整數，且公差不是73的倍數，試證該數列必有某項是73的倍數。例如：首項是5，公差是13，則第68項是73的倍數；首項是1，公差是5，則第30項是73的倍數；首項是3348，公差是13227，則第33項是73的倍數。

Answer 1

只要公差跟73互質，這性質就一定會成立
因為73為質數，且公差不是73的倍數
所以公差跟73會互質，
所以該數列在前73項中，必有某項是73的倍數。

說明如下：
令公差＝d，首項為a
∵(d,73)＝1
∴[d,73]＝73d
∴d÷73、2d÷73、3d÷73、...、73d÷73的餘數兩兩不相等
因為恰有73種餘數
餘數由0～72必各出現一次
∴(a+d)÷73、(a+2d)÷73、(a+3d)÷73、...、(a+73d)÷73的餘數
仍滿足0～72必各出現一次
其中餘數為0那一項即為73的倍數

Answer 2

在高一數學中有講到一定理，方程式ax + by = c，設a , b , c皆為整數，若且唯若x , y有整數解，則( a , b ) | c。

有一等差數列，首項和公差都是正整數，且公差不是73的倍數，試證該數列必有某項是73的倍數。

Pf:
設此數列首項為a，公差為d，線性方程式73x－ dy＝a，
由已知公差不是73的倍數，且73為質數，所以(73 , d) = 1 | a，
則x , y有整數解，又此線性斜率為正，所以x , y有正整數解，
即73x = a + dy，即該數列必有某項是73的倍數。

Answer 3

先用代號表示吧(因為懶~~:P)
第n項=首項+n*公差= A + n R
目前只有想到 用歸納的
(1. )A為73的倍數,那就是第73項,

除此之外
設A=73q+a, R=73p+r
R不為73倍數,所以r不等於零
a=0即是(1.)之狀況
只需要再考慮a=1~72,r=1~72 因為74之後就如同重復前面的情況

考慮a+nr是否至少存在一個n,使得(a+nr)為73之倍數,
其中a,n,r皆正整數
且0 => n=(73k-a)/r 在上述條件內是否至少存在一個n
考慮k=1
(2.)r=1時,當n=73-a時,(a+nr)為73之倍數
嚴謹一點了話,再寫個71行分別確定r=2~72 都至少有對應的一個a(a=1~72),使得n存在(n為正整數)

因為至少有n=1 即 73-a=r