由于这队士兵不超过170人，所以这队士兵有58人。
23、判断同余方程x?286(mod443)是否有解?
解：286=2×143，433是质数，(143，443)=1
奇数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)，这就是结论(ⅱ)。
若2?|n，p > 2，则p ?1 (mod 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?22n?15n?23n?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)?429??429??429??429??429?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，则2-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 P 2、设（m,n）=1,证明：m ?(n) +n ?(m) ≡1 (mod mn)。 ?(m) 证明：因为（m,n）=1，所以由欧拉定理知： n 于是 m ?(n) ≡1 (mod m)，m ?(n) ≡1 (mod 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)。 ppa?b其中0≤k≤p-1。又?ap?1?ap?2b???abp?2?bp?1?bp?1?bp?1???bp?1?pbp?1m(oda?bkk a?b)。 p-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?B. ??? C. ?11??5??? D. ?11??6??? ?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 C. －4，－2，8，13，32，35，135 D. －3，3，－4，4，－5，5，0 5、设n是正整数，则以下各式中一定成立的是( B ) A. (n+1，3n＋1)=1 C.（2n，n＋1）=1 二、填空题 1、25736被50除的余数是1。 2、同余方程3x≡5(mod16) 的解是x≡7(mod16)。 3、不定方程9x－12y=15的通解是x = -1 + 4t，y = -2 +3t，t?Z。 4、??323?? =1。 41??B.（2n－1，2n＋1）=1 D.（2n＋1，n－1）=1 5、实数的小数部分记为{x} ，则 {－}＝0.75。 6、为使3n与4n＋1 的最大公因数达到最大可能值，整数n应满足条件n=3k+2，k∈Z。 7、如果一个正整数具有35个正因数，问这个正整数最小是26×34=5184。 三、计算题 1、解不定方程9x＋24y－5z=1000。 解：解 因（9，24）=3，（3，-5）=1知原方程有解。原方程化为 9x ? 24y = 3t， 即 3x ? 8y = t， (1) 3t -5z = 1000 3t -5z = 1000， (2) 54?t?5u解(2)得 ?， u?Z， z??200?3u??x??u?8v再解3x ? 8y =5u得到 ?， u，v?Z。 y?u?3v??x??u?8v?故 ?y?u?3v， u, v?Z。 ?z??200?3u?2、设A = {x1, x2, ?, xm}是模m的一个完全系，以{x}表示x的小数部分，若(a, m) = 1，求 ax?b{?m}。 ii?1m