習題二

第一部分（2.1與2.2小節）

1.（i）若a|b且c|d，則ac|bd；

（ii）若a|b₁，…，a|b_k，則對任意整數x₁，…，x_k，有

a|b₁x₁+…+b_kx_k.

2.若x²+ax+b=0有整數根x₀≠0，則x₀|b.一般地，若

xⁿ+a_n-1x^n-1+…+a₀=0

有整數根x₀≠0，則x₀|a₀.

3.判斷以下方程有無整數根，若有整數根則求出所有這種根：

（i）x²+x+1=0；（ii）x²-5x-4=0；

（iii）x⁴+6x³-3x²+7x-6=0；

（iv）x³-x²-4x+4=0.

4.有一種盒子能裝3斤糖，另一種能裝6斤糖.假定每個盒子必須裝滿，試問：能用這兩種盒子來裝完100斤糖嗎？

5.若5|n且17|n，則85|n.

6.若2|n，5|n及7|n，則70|n.

7.設n≠1.證明：（n-1）²n^k-1的充分必要條件是（n-1）|k.

8.求以下各數的全部素除數、正除數以及把它們表為素數的乘積：1234，2345，34560，111111.

9.證明：

（i）設n≥1.2ⁿ+1是素數的必要條件是n=2^k.

（ii）2ⁿ-1是素數的必要條件是n為素數.

舉出幾個這兩種形式的素數.

10.證明：對任給的正整數K，必有K個連續正整數都是合數.

11.證明：奇數一定能表為兩平方數之差.

12.設奇數n＞1.證明：n是素數的充分必要條件是n不能表為三個或三個以上的相鄰正整數之和.

13.設p是正整數n的最小素因數.證明：若p＞n^1/3，則n/p是素數.

14.設p₁≤p₂≤p₃是素數，n是正整數.若p₁p₂p₃|n，則

p₁≤n^1/3，p₂≤（n/2）^1/2.

15.利用Eratosthenes篩法求出300以內的全部素數.

16.利用第14題，提出一種類似于Eratosthenes篩法的方法，來求出所有不超過100且至多是兩個素數乘積的正整數.

17.設n≥0，F_n=2²ⁿ+1（它稱為Fermat數）；再設m≠n.證明：若d＞1，且dF_n，則d｜/F_m.由此推出素數有無窮多個.

18.設F_n同上題.證明：F_n+1=F_n…F₀+2.

19.設A₁=2，A_n+1=A²_n-A_n+1（n≥1）.再設n≠m.證明：若d|A_n，d＞1，則d｜//A_m.由此推出素數有無窮多個.

20.設A_n同上題.證明：A_n+1=A_n…A₁+1.

21.設n≥3.證明：n！-1的素因數＞n.由此推出素數有無窮多個.并求最小的n使n！-1不是素數.

22.設整系數多項式P（x）=a_nxⁿ+a_n-1x^n-1+…+a₀，a_n≠0.證明：必有無窮多個整數值x，使得P（x）是合數.

23.證明：n²+n+41當n=0，1，2，…，39時都是素數.

24.設k≥3.求出所有這樣的正整數集合｛a₁，…，a_k｝，使得

（i）a₁，…，a_k是兩兩不同的正整數；

（ii）從中任意取出三個數，它們的和可被這三個數中的任一個整除.

25.設q≠0，±1.若對任意的a，b，由q|ab可推出q|a或q|b至少有一個成立，則q一定是不可約數.

26.設a，b，n滿足a|bn，ax+by=1，x，y是兩個整數.證明：a|n.

27.設m＞1，m|（m-1）！+1.證明m是素數.

28.假若素數只有有限個p₁，…，p_s.證明：對任意正整數N必有

由此推出素數有無窮多個.

第二部分（2.3小節）

1.求以下數組的全體公約數，并由此求出它們的最大公約數：

（i）72，-60；（ii）-120，28；（iii）168，-180，495.

2.給出四個整數，它們的最大公約數是1，但任何三個數都不既約.

3.證明：（i）（a，b，c）≤（a，b），［a，b，c］≥［a，b］；

（ii）若a|b，則［a，c］≤［b，c］，（a，c）≤（b，c）；

（iii）（a，b）≤（a+b，a-b）；

（iv）（a，b）≤（ax+by，au+bv），其中x，y，u，v是任意整數.

4.若（a，b）=1，c|a+b，則（c，a）=（c，b）=1.

5.設n≥1.證明：（n！+1，（n+1）！+1）=1.

6.求最大公約數

（i）（2t+1，2t-1）；（ii）（2n，2（n+1））；

（iii）（kn，k（n+2））；（iv）（n-1，n²+n+1）.

7.設a，b是正整數.證明：若［a，b］=（a，b），則a=b.

8.證明：若（a，4）=（b，4）=2，則（a+b，4）=4.

9.設整數a，b，c，d滿足ad-bc=±1.證明：若u=am+bn，v=cm+dn，則（m，n）=（u，v）.

10.設a，b是正整數，且有整數x，y使得ax+by=1.證明：

（i）［a，b］=ab；（ii）（ac，b）=（c，b）.

11.若2｜/b，則（2^ka，b）=（a，b）.

12.設g，l是給定的正整數.證明：

（i）存在整數x，y，使得（x，y）=g，［x，y］=l的充分必要條件是g|l；

（ii）存在正整數x，y，使得（x，y）=g，xy=l的充分必要條件是g²|l.

13.求滿足（a，b）=10，［a，b］=100的全部正整數組a，b.

14.求滿足［a，b，c］=10的全部正整數組a，b，c.

15.求滿足（a，b，c）=10，［a，b，c］=100的全部正整數組a，b，c.

16.求以下數組的最小公倍數：（i）198，252；（ii）482，1689.

17.設a，b是正整數，那么a，2a，3a，…中第一個被b整除的數就是［a，b］.如何把這方法推廣來求［a₁，…，a_k］？

18.設n≥1.以φ（n）記正整數1，2，…，n中與n既約的數的個數.證明：

（i）φ（1）=φ（2）=1；

（ii）當n≥3時，2|φ（n）；

（iii）當n=p為素數時，φ（p）=p-1.

可以做IMO的題（見附錄四）：［1.1］，［9.6］，［11.1］，［12.4］，［16.6］，［18.4］，［19.3］，［21.1］，［25.6］，［26.4］，［28.6］，［32.2］，［32.3］，［33.1］，［33.6］，［34.1］，［35.4］，［37.1］，［38.6］，［39.6］，［42.4］.