习题四

第一部分（4.1小节）

1.设p是素数，（a，p²）=p，（b，p³）=p².求

（ab，p⁴），（a+b，p⁴）.

2.设p是素数，（a，b）=p.求（a²，b），（a³，b），（a²，b³）所可能取的值.

3.判断以下结论是否成立，对的给出证明，错的举出反例：

（i）若（a，b）=（a，c），则［a，b］=［a，c］；

（ii）若（a，b）=（a，c），则（a，b，c）=（a，b）；

（iii）若d|a，d|a²+b²，则d|b；

（iv）若a⁴|b³，则a|b；

（v）若a²|b³，则a|b；

（vi）若a²|b²，则a|b；

（vii）ab|［a²，b²］；

（viii）［a²，ab，b²］=［a²，b²］；

（ix）（a²，ab，b²）=（a²，b²）；

（x）（a，b，c）=（（a，b），（a，c））；

（xi）若d|a²+1，则d|a⁴+1；

（xii）若d|a²-1，则d|a⁴-1.

5.（i）设整系数多项式P（x）=xⁿ+a_n-1x^n-1+…+a₀，a₀≠0.若P（x）有有理根x₀，则x₀必是整数，且x₀|a₀.

（ii）证明：x⁵+3x⁴+2x+1没有有理根.

6.设θ=rπ，r是有理数.证明：除了cosθ=0，±1/2，±1外，cosθ一定是无理数，即除了θ=kπ，kπ±π/3，kπ+π/2外，cosθ一定是无理数，k为任意整数（提示：对任给正整数n，必有首项系数为1的整系数多项式f_n（x），使2cos nα=f_n（2cosα），α为任意实数）.

7.设n是正整数，n|ab，n｜/a，n｜/b.再设a=d（a，ab/n）.证明：d|n，1＜d＜n.解释这题的意义.

8.设（a，b）=1.证明：

（i）（d，ab）=（d，a）（d，b）；

（ii）d是ab的正除数的充分必要条件是d可表示为d₁d₂，这里d₁是a的正除数，d₂是b的正除数，且这种表示法唯一.

9.证明：

［a₁，a₂，a₃，…，a_n］=［［a₁，a₂］，a₃，…，a_n］=［［a₁，…，a_r］，［a_r+1，…，a_n］］.

10.设a，b，c是正整数.证明：

（i）［a，b，c］（ab，bc，ca）=（a，b，c）［ab，bc，ca］

=（a，b，c）［a，b，c］［（a，b），（b，c），（c，a）］=abc；

（ii）［a，b，c］=abc的充分必要条件是（a，b）=（b，c）=（c，a）=1.

11.证明：（a/（a，c），b/（b，a），c/（c，b））=1.

12.证明：（a，b，c）（ab，bc，ca）=（a，b）（b，c）（c，a）.

13.证明：（a，［b，c］）=［（a，b），（a，c）］.

14.证明：［a，（b，c）］=（［a，b］，［a，c］）.

15.证明：（i）（［a，b］，［b，c］，［c，a］）=［（a，b），（b，c），（c，a）］；

（ii）（a，b）（b，c）（c，a）［a，b，c］²=［a，b］［b，c］［c，a］（a，b，c）².

16.证明：

（i）若（13，ab）=1，则13|a¹²-b¹²；

（ii）若（91，ab）=1，则91|a¹²-b¹²；

（iii）对任意的n，有2730|n¹³-n.

17.设p₁，…，p_n是n个两两不同的素数.再设A_r是其中任意取定的r个素数的乘积.证明：任一p_j（1≤j≤n）都不能整除

p₁…p_n/A_r+A_r；

由此推出素数有无穷多个.

18.设p是素数，p｜/a.证明：对任给的正整数k，有

（i）φ（p^k）=（p-1）p^k-1，φ（n）由2习题二第二部分第18题给出；

21.设m＞1.证明：m｜/2^m-1.

22.设f（x）=a_nxⁿ+…+a₀，g（x）=b_mx^m+…+b₀.证明：

（i）若它们是整系数多项式及h（x）=f（x）g（x）=c_m+nx^m+n+…+c₀，那么有

（a_n，…，a₀）（b_m，…，b₀）=（c_m+n，…，c₀）.

特别地，当（a_n，…，a₀）=（b_m，…，b₀）=1时，必有（c_m+n，…，c₀）=1.全体系数既约的整系数多项式称为本原多原式.

23.设a，b，m是正整数，（a，b）=1.证明：在算术数列

a+kb（k=0，1，2，…）

中，必有无穷多个数和m既约.

24.设a＞b＞0，n＞1.证明：aⁿ-bⁿ｜/aⁿ+bⁿ.

25.设a＞b≥1，n＞1.证明：

（（aⁿ-bⁿ）/（a-b），a-b）=（n（a，b）^n-1，a-b）.

26.（i）若n|2ⁿ-2，n一定是素数吗？考虑n=341.具有这种性质的数称为伪素数.

（ii）若n|2ⁿ-2，则m|2^m-2，这里m=2ⁿ-1.

（iii）设n=161038，验证n|2ⁿ-2.

27.（i）一个合数n称为绝对伪素数，如果对任意整数a必有n|aⁿ-a.证明：561是绝对伪素数，但341不是.

（ii）设m≥1.若q₁=6m+1，q₂=12m+1，q₃=18m+1均为素数，则n=q₁q₂q₃是绝对伪素数.举出几个这样的m.

28.证明：存在无穷多个n，使n|2ⁿ+1.

29.证明：（i）若n|2ⁿ+2，n-1|2ⁿ+1，则m|2^m+2，m-1|2^m+1，这里m=2ⁿ+2；

（ii）存在无穷多个n，使n|2ⁿ+2.

30.证明：存在无穷多个合数n，使对任意整数a有

n|a^n-1-a.

31.设m≥2，（a，m）=1.再设存在正整数d使得m|a^d+1，并记使它成立的最小的d为δ^-_m（a）.此外，把例1，4及5中的δ_m（a）记为δ⁺_m（a）.证明：

（i）若m|a^h-1或m|a^h+1，则必有δ^-_m（a）|h；

（ii）当m=2时，δ⁺₂（a）=δ^-₂（a）=1；

（iii）当m＞2时，δ⁺_m（a）=2δ^-_m（a）；

（iv）当m＞2时，m|a^h+1的充分必要条件是h=qδ^-_m（a），q为奇数.

32.（i）对任意正整数k，必有3^k|2^3k-1+1，3^k+1｜/2^3k-1+1.

（ii）设k，s是正整数.证明：3^k|2^s+1的充分必要条件是

2｜/s，3^k-1|s.

第二部分（4.2小节）

1.证明：从定理8的（ii）成立可推出定理8的（i）成立.

2.设n，a，b，c是正整数，（b，c）=1.证明：若c|n！，则

c|a（a+b）（a+2b）…（a+（n-1）b）.

3.设a₁＜a₂＜a₃＜…是一个无穷正整数列.证明：在这个数列中一定存在两个数a_s，a_t，使得有无穷多个a_n可表示为

a_n=xa_s+ya_t，

其中x，y是整数.

4.4例8中，当（n，k）=d＞1时，若按条件（i），（ii）对集合M中的每个数涂一种颜色，问M中的数最多可涂上几种颜色.

5.证明：13|a²-7b²的充分必要条件是13|a，13|b.

6.设1≤a＜b，（a，b）=1.证明：

（i）既约分数a/b是十进位的纯循环小数的充分必要条件是（b，10）=1；

（ii）若a/b是纯循环小数，最小的循环节为t₀（即

是十进位纯循环小数表示，而对比t₀小的正整数t，a/b不可能表示为循环节为t的纯循环小数），则t₀恰好是使b|10^d-1成立的最小正整数d.

7.设1≤a＜b，（a，b）=1.证明：

（i）b可唯一地表示为2^α5^βb₁，（b₁，10）=1；

（ii）当α=β=0时，a/b是纯循环小数，即上题所讨论的情形；

（iii）当b₁=1时，a/b是有限小数；

第三部分（4.3小节）

1.用辗转相除法求以下数组的最大公约数，并把它表为这些数的整系数线性组合：（i）15，21，-35；（ii）210，-330，1155.

2.设a＞1.证明：

（i）（a^m-1，aⁿ-1）=a^（m，n）-1；

（ii）（a^m-（-1）^{m/（m，n）}，aⁿ-（-1）^{n/（m，n）}）=a^（m，n）+1；

3.设a＞b≥1，（a，b）=1.证明：

（a^m-b^m，aⁿ-bⁿ）=a^（m，n）-b^（m，n）.

4.设m，n是正整数，满足mn|m²+n²+1.证明：

m²+n²+1=3mn.

5.详细写出按第三个途径建立最大公约数理论.

6.本题要给出由直接确定4式（2）中的x_1，0，…，x_k，0来求出最大公约数g=（a₁，…，a_k）的算法.（i）选定一组整数x_1，1，…，x_k，1，使得正整数a₁x_1，1+…+a_kx_k，1=g₁尽量地小.若g₁|a_j，1≤j≤k，则g₁=g就是最大公约数（为什么）.可取x_j，0=x_j，1（1≤j≤k）.若不然，（ii）必有某个j使g₁｜/a_j.证明：可取到整数x₁，2，…，x_k，2，使得正整数a₁x_1，2+…+a_kx_k，2=g₂＜g₁.（iii）对g₂重复作讨论（i）和（ii），进而证明经有限步后就可定出x_j，0（1≤j≤k）满足4式（2）.（iv）用此法来做第1题.

可以做IMO的题（见附录四）：［37.6］，［40.4］，［41.5］，［42.6］，［43.3］，［43.4］.