内容发布更新时间 : 2024/4/28 21:28:22星期一 下面是文章的全部内容请认真阅读。

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