t ? 3z = 41
得 x = t ? 2u
y = u u?Z， t = 41 ? 3v
z = v v?Z，
消去t得 x = 41 ? 3v ? 2u
y = u
z = v u，v?Z。
由此得原方程的全部正整数解为
(x, y, z) = (41 ? 3v ? 2u, u, v)，u > 0，v > 0，41 ? 3v ? 2u > 0。
2、有一队士兵，若三人一组，则余1人；若五人一组，则缺2人；若十一人一组，则余3人。已知这队士兵不超过170人，问这队士兵有几人？
解：设士兵有x人，由题意得x ? 1 (mod 3)，x ? ?2 (mod 5)，x ? 3 (mod 11)。
在孙子定理中，取 m1 = 3， m2 = 5， m3 = 11，m = 3?5?11 = 165，
M1 = 55，M2 = 33，M3 = 15， M1? = 1，M2? = 2，M3? = 3，
则 x ? 1?55?1 ? （-2）?33?2 ? 3?15?3 ? 58 (mod 165)， 因此所求的整数x = 52 + 165t，t?Z。
由于这队士兵不超过170人，所以这队士兵有58人。
23、判断同余方程x?286(mod443)是否有解?
解：286=2×143，433是质数，(143，443)=1
奇数143不是质数，但可用判定雅可比符号计算的勒让德符号
?286??2??143?????????(?1)?443??243??443?
4432?12?(?1)143?1443?1?22?443??14??2??7????????????143??143??143??143??(?1)143?18?(?1)7?1143?1?223??1??143??????????1 ∴原方程有解。 ??
?7??3??7?四、证明题
1、设(a, m) = 1，d0是使a d ? 1 (mod m)成立的最小正整数，则
(ⅰ) d0??(m)；
j
(ⅱ)对于任意的i，j，0 ? i, j ? d0 ? 1，i ? j，有a i??a (mod m)。 （1）
证明：(ⅰ) 由Euler定理，d0 ? ?(m)，因此，由带余数除法，有
?(m) = qd0 ? r，q?Z，q > 0，0 ? r < d0。
因此，由上式及d0的定义，利用欧拉定理得到
qd?r1 ?a?(m)?a0?ar(mod m)，
即整数r满足 a r ? 1 (mod m)，0 ? r < d0 。 由d0的定义可知必是r = 0，即d0??(m)。
(ⅱ) 若式(1)不成立，则存在i，j，0 ? i, j ? d0 ? 1，i ? j，使a i ? a j (mod
m)。
不妨设i > j。因为(a, m) = 1，所以 ai ? j ? 0 (mod m)，0 < i ? j < d0。 这与d0的定义矛盾，所以式(1)必成立。
2、证明：设a，b，c，m是正整数，m > 1，(b, m) = 1，并且
b a ? 1 (mod m)，b c ? 1 (mod m) （1）
记d = (a, c)，则bd ? 1 (mod m)。
证明：由裴蜀恒等式知，存在整数x，y，使得ax ? cy = d，显然xy < 0。
若x > 0，y < 0，由式(1)知：1 ? b ax = b db ?cy = b d(b c) ?y ? b d (mod m)。 若x < 0，y > 0，由式(1)知：1 ? b cy = b db ?ax = b d(ba) ?x ? b d (mod m)。
3、设p是素数，p?bn ? 1，n?N，则下面的两个结论中至少有一个成立：
(ⅰ) p?bd ? 1对于n的某个因数d < n成立； (ⅱ) p ? 1 ( mod n )。
|n，p > 2，则(ⅱ)中的mod n可以改为mod 2n。 若2?证明：记d = (n, p ? 1)，由b n ? 1，b p ? 1 ? 1 (mod p)，及第2题有
b d ? 1 (mod p)。
若d < n，则结论(ⅰ)得证。
若d = n，则n?p ? 1，即p ? 1 (mod n)，这就是结论(ⅱ)。
|n，p > 2，则p ?1 (mod 2)。由此及结论(ⅱ)，并利用同余的基本若2?
性质，
得到p ? 1 (mod 2n)。
初等数论练习题八
一、单项选择题
1、设n > 1，则n为素数是(n ? 1)! ? ?1 (mod n)的（ C ）。 A.必要但非充分条件 B.充分但非必要条件 C.充要条件 D.既非充分又非必要条件 2、小于545的正整数中，15的倍数的个数是（ C ）
A.34 B.35 C.36 D.37 3、500!的标准分解式中7的幂指数是（ D ）
A.79 B.80 C.81 D.82 4、以下各组数中，成为模10的简化剩余系的是（ D ）
A.1,9,－3,－1 B.1,－1,7,9 C.5,7,11,13 D.－1,1,－3,3 5、设n是正整数，下列选项为既约分数的是（ A ） A.
3n?1n?12n?1n?1 B. C. D. 5n?25n?23n?12n?1二、填空题
1、σ（120）=360。 2、7355的个位数字是3。
3、同余方程3x≡5(mod14)的解是x≡11(mod14)。 4、（
17）=1。 235、［-2］＝-2。 6、如果一个正整数具有6个正因数，问这个正整数最小是12。 7、同余方程x3+x2-x-1≡0(mod 5)的解是x≡±1(mod5)。 三、计算题
1、已知563是素数，判定方程x2 ? 429 (mod 563)是否有解。
?429?解：把??看成Jacobi符号,我们有
563??
?429????(?1)563??429?1563?1.22?563??563??134??2??67???????????????(?1)429429429429429??????????4292?18?67?-）??429???67???????(?1)?429?67?1429?1.22?429??429??27?????????????(?1)?67??67??67?27?167?1.22?67??67?
??????27??27??13?????(?1)?27?27?113?1.22?27??1???????1， ?13??13?故方程x2 ? 429 (mod 563)有解。
2、求出模23的所有的二次剩余和二次非剩余。 解：模23的所有的二次剩余为
x?1,2,3,4,6,8,9,12,13,16,18 (mod 23)； 模23的所有的二次非剩余为
x?5,7,10,11,14,15,17,19,20,21,22 (mod 23)。
3、试求出所有正整数n ，使得1n＋2n＋3n＋4n 能被5整除。
解：若n为奇数，则1n＋2n＋3n＋4n?1n＋2n＋（-2）n＋（-1）n ? 0 (mod 5)； 若n=2m，m∈Z，则1n＋2n＋3n＋4n?12m＋22m＋（-2）2m＋（-1）2m
?2+2×22m =2+2×4m =2+2×(-1)m(mod 5)；
当m为奇数时，1n＋2n＋3n＋4n?0(mod 5)； 当m为偶数时，1n＋2n＋3n＋4n?4(mod 5)。
|n时，5∣1＋2＋3＋4。 故当4?n
n
n
n
四、证明题
1、证明：若质数p>2，则2P-1的质因数一定是2pk+1形。
证明：设q是2p-1的质因数，由于2p-1为奇数，∴ q≠2，（2，q）=1。
由条件q|2p-1,即2p≡1（mod q）。
设h是使得2x≡1（mod q）成立最小正整数，若1 2、设（m,n）=1,证明：m ?(n) +n ?(m) ≡1 (mod mn)。 ?(m) 证明：因为（m,n）=1，所以由欧拉定理知： n ≡1 (mod m)，m ?(n) ≡1 (mod n) 于是 m ?(n) +n ?(m) ≡1 (mod m)， m ?(n) ?(n) +n ?(m) ≡1 (mod n)。 又因为（m,n）=1，所以 m+n ?(m) ≡1 (mod mn)。 注：此题也可这样表述：若两个正整数a,b互质，则存在正整数m,n，使得 am+bn≡1(mod ab)。 ap?bp3、设（a,b）=1,a+b≠0,p为一个奇质数，证明：(a?b,)?1或p。 a?bap?bp 说明：事实上，设(a?b,)?d，只需证明：d | p 即可。 a?b证明：由a+b≡0(mod a+b)，即a≡-b (mod a+b)，知a≡(-b) (mod a+b)。 其 中 0 ? kk k?p-1。 a?mb)。 o又 dap?bp?ap?1?ap?2b???abp?2?bp?1?bp?1?bp?1???bp?1?pbp?1(a?bp-1 ap?bp令(a?b,。 又（a,b）=1，d |（a+b）知（d,b）=1。 )?d，则d | pb a?b（否则设（d,b）=d′＞1，立即得到d′︱a和d′︱b，这与（a,b）=1矛盾。） 于是（d ，b p-1 ）=1。故d | p，即 d =1或p。 初等数论练习题九 一、单项选择题 1、以下Legendre符号等于-1的30被-1是( D ) 3?A. ??? ?11?4??5??6?B. ??? C. ?? D. ?? ?11??11??11?2、100至500的正整数中，能被17整除的个数是( B ) A. 23 B. 24 C. 25 D. 26 |500！3、设 3?|500!，但3??1?，则α=( C ) A. 245 B.246 C.247 D. 248 4、以下数组中，成为模7的完全剩余系的是( C ) A. －14，－4，0，5，15，18，19 B. 7，10，14，19，25，32，40