习题三

第一部分（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］.