習題三

第一部分（3.1小節）

1.證明3定理2.設3定理2中的a＞0，那么整數被a除后所得的余數r₁是且僅是d，d+1，…，d+a-1這a個數中的一個.

2.設a＞0.證明：相鄰的a個整數中有且僅有一個被a整除.

3.分別寫出被-7，9，12除后的所有最小非負余數、最小正余數和絕對最小余數.

4.（i）若2|ab，則2|a，2|b至少有一個成立.

（ii）若7|ab，則7|a，7|b至少有一個成立.

（iii）若14|ab，試問：14|a或14|b必有一個成立嗎？

5.設a≠0，b_j=q_ja+s_j（1≤j≤n）.證明：b₁，…，b_n以任意方式作加、減、乘法運算后被a除后所得的最小非負余數等于s₁，…，s_n以同樣的方式作加、減、乘法運算后被a除后所得的最小非負余數.

6.證明：上題中的“最小非負余數”改為“絕對最小余數”、“最小正余數”或3定理2中的一般余數后，結論仍成立.

7.證明：對任意整數n，有

（i）6|n（n+1）（n+2）；（ii）8|n（n+1）（n+2）（n+3）；

（iii）24|n（n+1）（n+2）（n+3）；

（iv）若2｜/n，則8|n²-1及24|n（n²-1）；

（v）若2｜/n，3｜/n，則24|n²+23；

（vi）6|n³-n；（vii）30|n⁵-n；

8.分別求出n²，n³，n⁴，n⁵被3，4，8，10除后，可能取到的最小非負余數、最小正余數及絕對最小余數.

9.證明：（i）對任意的整數x，y，必有8｜/x²-y²-2；

（ii）若2｜/xy，則x²+y²≠n²；

（iii）若3｜/xy，則x²+y²≠n²；

（iv）若a²+b²=c²，則6|ab.

10.設a≥2.對任一整數j，記j₁mod a=｛n=ka+j：k∈Z｝.證明：

（i）j₁mod a=j₂mod a的充分必要條件是a|j₁-j₂.

（ii）當a｜/j₁-j₂時，集合j₁mod a和j₂mod a不相交.

（iii）設M是至少有兩個不同整數的Z的子集合.若M中任意兩數（可以相同）之差也屬于M，那么，一定存在一個正整數m，使得M=0mod m=mZ，即M是由所有m的倍數組成的集合.

11.在上題的符號下，求j分別滿足

（i）0mod3∩0mod5=j mod15；

（ii）1mod3∩1mod5=j mod15；

（iii）-1mod3∩-2mod5=j mod15.

12.在第10題的符號下，求s及j₁，…，j_s，使得

1mod3=j₁mod21∪…∪j_s mod21.

一般地，設a|b，j為給定整數，求s及j₁，…，j_s，使得

j mod a=j₁mod b∪…∪j_s mod b.

解釋本題的含意.

13.證明：（i）3k+1形式的奇數一定是6h+1形式；

（ii）3k-1形式的奇數必是6h-1形式.

14.證明：任一形如3k-1，4k-1，6k-1形式的正整數必有同樣形式的素因數.

15.證明：（i）形如4k-1的素數有無窮多個；

（ii）形如6k-1的素數有無窮多個.

16.（Ⅰ）設n=c_k·10^k+…+c₁·10+c₀.證明：

（i）2|n?2|c₀；

（ii）5|n?5|c₀；

（iii）3|n?3|（c_k+…+c₀）；

（iv）9|n?9|（c_k+…+c₀）；

（v）11|n?11|（c_k-c_k-1+…+（-1）^k·c₀）.

（Ⅱ）設n=c_k·（100）^k+…+c₁·（100）+c₀.證明：

（i）11|n?11|（c_k+…+c₀）；

（ii）101|n?n|（c_k-c_k-1+…+（-1）^kc₀）.

（Ⅲ）設n=c_k·（1000）^k+…+c₁·（1000）+c₀.證明：

（i）37|n?37|（c_k+…+c₀）；

（ii）7|n?7|（c_k-c_k-1+…+（-1）^k·c₀）；

（iii）13|n?13|（c_k-c_k-1+…+（-1）^kc₀）.

（Ⅳ）利用以上各個結果提出相應的整數被2，3，5，7，9，11，13，37，或101整除的判別法.利用這種檢查因數的方法，把1535625，1158066，82798848，81057226635000表示成素數的乘積.

17.設n=10l+c₀，m=l-2c₀.證明：7|n?7|m.利用此法判斷41283及第16題中的各數能否被7整除.

18.設h≥0是給定的整數，a≥2.證明：

（i）任一整數n，0≤n＜a^h+1，必可唯一地表示為

n=r_ha^h+…+r₁a+r₀，

其中0≤r_j≤a-1，0≤j≤h，且每一個這樣表出的n滿足0≤n＜a^h+1.

（ii）若a=3，則任一整數n，-（3^h+1-1）/2≤n≤（3^h+1-1）/2，必可唯一地表示為n=r_h·3^h+…+r₁·3+r₀，-1≤r_j≤1，0≤j≤h，且每一個這樣表出的n必滿足-（3^h+1-1）/2≤n≤（3^h+1-1）/2.此外，當n＞0時，第一個不為零的r_j=1，當n＜0時，第一個不為零的r_j=-1.

（iii）試求由表達式n=r_h·a^h+…+r₁·a+r₀（-a/2＜r_j≤a/2，0≤j≤h）表出的整數n的范圍.

（iv）試求由表達式n=r_h·a^h+…+r₁·a+r₀（-a/2≤r_j＜a/2，0≤j≤h）表出的整數n的范圍.

（v）當a為偶數，特別是a=2時，比較（iii），（iv）所表出的整數范圍的差別.

（vi）給定正整數列m₀，m₁，m₂，…，m_j≥2（j≥0）.證明：每個正整數n可唯一地表示為n=a₀+a₁m₀+a₂m₀m₁+…+a_km₀m₁…m_k-1，其中0≤a_j≤m_j-1（0≤j≤k），a_k＞0.

19.設n≠0.證明n必可唯一地表示為：

（i）n=2^k·m，2｜/m；（ii）n=3^k·m，3｜/m.

20.設k≥1.證明：

（i）若2^k≤n＜2^k+1，及1≤a≤n，a≠2^k，則2^k｜/a；

（ii）若3^k≤2n-1＜3^k+1，1≤l≤n，2l-1≠3^k，則3^k｜/2l-1.

21.證明：當n＞1時，1+1/2+…+1/n不是整數.

22.證明：當n＞1時，1+1/3+1/5+…+1/（2n-1）不是整數.

23.在任意給定的兩個以上的相鄰正整數中必有唯一的一個正整數a=2^r·m，2｜/m，使得2^r不能整除其他正整數.

24.設m，n是正整數.證明：不管如何選取“+”、“-”號，±1/m±1/（m+1）±…±1/（m+n）一定不是整數.

25.設n＞1.證明：n可表示為兩個或兩個以上的相鄰正整數之和的充分必要條件是n≠2^k.

26.設m＞n是正整數.證明：2ⁿ-1|2^m-1的充分必要條件是n|m.以任一正整數a＞2代替2結論仍然成立嗎？

27.設a，b是正整數，b＞2.證明：2^b-1｜/2^a+1.

28.設a≥2，m≥2，滿足ax+my=1，其中x，y為某兩個整數.證明：（i）一定存在正整數d≤a-1，使得a|m^d-1；

（ii）設d₀是滿足（i）的最小正整數d，那么a|m^h-1（h∈N）的充分必要條件是d₀|h.

29.求：（i）7|2^d-1的最小正整數d；

（ii）11|3^d-1的最小正整數d；

（iii）2^d被7除后所可能取到的最小非負余數，絕對最小余數；

（iv）3^d被11除后所可能取到的最小非負余數，絕對最小余數.

30.證明：對任意正整數d，

（i）13｜/3^d，3^d+1，3^d±2，3^d+3，3^d-4，3^d±5，3^d±6；

（ii）13｜/4^d，4^d±2，4^d±5，4^d±6.

31.證明：不存在整數k使得：（i）x²+2y²=8k+5，8k+7；

（ii）x²-2y²=8k+3，8k+5；（iii）x²+y²+z²=8k+7；

（iv）x³+y³+z³=9k±4；（v）x³+2y³+4z³=9k³，k≠0.

32.設奇數a＞2，a|2^d-1的最小正整數d=d₀.證明：2^d被a除后，所可能取到的不同的最小非負余數有d₀個.

第二部分（3.2小節）

1.用3定理4的輾轉相除法求以下數組的最大公約數，并把它表為這些數的整系數線性組合：

（i）1819，3587；（ii）2947，3997；（iii）-1109，4999.

2.設v₀，v₁是給定的兩個整數，v₁≠0，v₁｜/v₀.我們一定可以重復應用3式（3″）形式的帶余數除法得到下面h+1個等式：

這種算法也稱為輾轉相除法或Euclid除法.

3.在第2題的條件和符號下，證明：

（i）|v_h+1|=（v₀，v₁）；

（ii）d|v₀且d|v₁的充分必要條件是d|v_h+1；

（iii）存在整數x₀，x₁，使得v_h+1=x₀v₀+x₁v₁.

4.利用第2題給出的輾轉相除法來做第1題的（i），（ii），及（iii）.比較用這兩種輾轉相除法來做這三個小題時，所做的帶余數除法的次數k+1和h+1的大小.

5.在3定理4的條件和符號下，令

P_-1=1，P₀=q₀，P_j=q_jP_j-1+P_j-2，Q_-1=0，Q₀=1，Q_j=q_jQ_j-1+Q_j-2，j=1，2，…，k-1，

那么，我們有

（-1）^ju_j=Q_j-2u₀-P_j-2u₁，j=1，2，…，k+1.

6.用相應于第2題的輾轉相除法來推出類似于第5題的結論.

7.設3定理4中的u₀＞u₁＞1；再設b₀=1，b₁=2及

b_j+1=b_j+b_j-1，j=1，2，….

那么，在3定理4的符號下有u₁≥b_k.進而證明：

k+1≤2（ln u₁）/ln2.

試解釋這結果的意義.

8.在第2題中設v₀＞v₁＞1；再設c₀=1，c₁=2及

c_j+1=2c_j+c_j-1，j=1，2，….

那么，有v₁≥c_h.進而證明：

（i）h≤（ln v₁）/ln2；

（ii）當v₁≥32時，h+1≤（ln v）/ln2.

9.設a＞b＞1，k是在3定理4中取u₀=a，u₁=b時所得到的，h是在第2題中取v₀=a，v₁=b時所得到的.證明：h≤k.

10（注：本題需要利用4例1的結論，請學過這部分內容后再做.）.設p是奇素數，q是2^p-1的素因數.證明：q=2kp+1.

11（注：本題需要利用4例1的結論，請學過這部分內容后再做.）.利用上題求2¹¹-1，2²³-1的素因數分解式.

12.當p為素數時，M_p=2^p-1形式的數稱為Mersenne數.把這種數用二進位來表示，利用3定理4的輾轉相除法（出現的數均用二進位表示）來直接證明：所有的Mersenne數兩兩互素.

可以做IMO的題（見附錄四）：［2.1］，［4.1］，［6.1］，［10.2］，［10.6］，［12.2］，［13.3］，［16.3］，［17.2］，［19.5］，［23.4］，［24.5］，［27.1］，［29.3］，［29.6］，［35.3］，［37.3］，［39.4］.