- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
例1 解二次同余式x 2 19(mod 31). 例2 求解同余式x 2(mod 311).
2
12
1 、p 3为素数，求证8 p 2 1不能为素数。 2、问123451234 的最后两位数？ 3、用同余的方法证明：是否存在五个连续自然数， 将得前四个数的平方和等于第五个数的平方。
4、解同余式方程 (1)589x 1026(mod 817),(2)17 x 229(mod1540) 5、求20!的标3 0, 1, 代入同余式
(1 4t3 )2 57 (mod 24 ).
57 12 得 t3 1 (mod 2) 8
t3 1 2t4
7
故 x = (1 4(1 2t4 )) (5 8t4 )是适合 x 2 57 (mod 24 ) 的一切整数.
(2)
1
即(1)有解 (2)有解, 且(1)的解数是(2)的各式解数 的乘积.
因此, 合数模的同余式归结为讨论模为奇素数幂p 的二次同余式 x 2 a (mod p ), 0, ( p, a ) 1 以及模为2 的二次同余式 x 2 a (mod 2 ), 0, (2, a ) 1 有解的条件及解的个数. (4) (3)
2 2
4）求解同余式x 65(mod 43904)的解；
10
利用jacobi符号说明下列同余式中哪一个可能的。 1）x 2 3878(mod 3989) 2) x 2 1305(mod1459)
11
定理a 如果p 4n 1, x a(mod p)有解，且
2
(a , p) 1, 则其全部解为x a n (mod p).
2
定理1 设 p是奇素数, 则 x a (mod p )有解
2 1
a 1(即a为模 p的平方剩余), 且有解时, p 2 x1 a (mod p )的解数是2.
推论 设 p是奇素数, a是与 p互素的整数, 则同
2 余式 x1 a (mod p )的解数是
a T 1 p
3
再讨论模为2 的二次同余式 x 2 a (mod 2 ), 0, (2, a ) 1 有解的条件及解的个数. 当 1时, 同余式即 x 2 a (mod 2), (2, a ) 1 显然此同余式有解,且解的个数为1.
4
定理2 设 1,则(4)有解的必要条件是 (i) 当 2时, a 1 (mod 4); (ii) 当 3时, a 1 (mod 8).
(i) 当 0,1时, 解数是2 ;
k
(ii) 当 2时,解数是2k 1 ; (iii) 当 3时,解数是2k 2 .
6
例1 求解同余式 x 57 (mod64).
2
解 因64 2 , 6 3, 57 1 (mod8),
6
故同余式有四解.
因 x 2 57 (mod 23 )的解可表为
13
6、有布7丈5尺，裁剪成大人和小孩的衣料，大人 一件衣服用布7尺2寸，小孩一件衣服用布3尺， 问各裁剪多少件衣服恰好把布用尽。 7、求2013
19852004
被7除余数是几？
8、求同余式 (1)x2 2(mod 67),(2)x2 2(mod 37) 的解数。
14
再由 (5 8t4 ) 57 (mod 2 )
2 5
得 t4 0 (mod 2) t4 2t5 故 x = (5 16t5 ) 是适合
x 57 (mod 2 )
2 5
的一切整数.
再由 (5 16t5 ) 57 (mod2 )
2 6
8
t5 1 (mod 2) t5 1 2t6
故x = (5 16(1 2t6 )) (21 32t6 )是适合 x 57 (mod 2 )
2 6
的一切整数.
因此 x 21, 53 (mod 64) 是所求的四个解.
9
练习 1）求解同余式x 2 17(mod 64)的解； 2）求解同余式x 2 24(mod125)的解； 3）求解同余式x 41(mod 43904)的解；
4.7 合数模的情形
先在讨论模为合数m的二次同余式 x 2 a (mod m), 有解的条件及解的个数. ( a, m ) 1 (1)
当m = 2 p1 p2
1
2
pk 时, 同余式等价于同余式组
k
x 2 a (mod 2 ) 2 1 x a (mod p 1 ) k x 2 a (mod pk )
若上述条件成立, 则(4)有解, 且当 2时, 解数是2; 当 3时, 解数是4.
5
定理3 同余式 x a (mod m ); m 2 p1 p2
2
1
2
pk ,(a , m ) 1
k
有解的必要条件是 : 当 2时, a 1 (mod 4); 当 3时, a 1 (mod 8) a 且 1, i 1, 2, , k . pi 若上述条件成立时,则同余式有解,且
