同余的应用举例 例1已知2001年的国庆节是星期一,求2010年的国庆 节是星期几? 分析:一星期有7天,要求2010年的国庆节是星期几, 就要求从2001年到2010年的国庆节的总天数被7除的 余数就行了。但在计算中,如果我们能充分利用同余 性质,就可以不必算出这个总天数。 解:2001年国庆节到2010年国庆节之间共有2个闰年 7个平年,即有“366×2+365×7”天。 366×2≡2×2三4(mod7), 365×7三1×7三0(mod7) ∴366×2+365×7≡2×2+1×7三4+0三4(mod7) 答:2010年的国庆节是星期五
同余的应用举例 例1 已知2001年的国庆节是星期一，求2010年的国庆 节是星期几？ 分析： 一星期有7天，要求2010年的国庆节是星期几， 就要求从2001年到2010年的国庆节的总天数被7除的 余数就行了。但在计算中，如果我们能充分利用同余 性质，就可以不必算出这个总天数。 解： 2001年国庆节到2010年国庆节之间共有2个闰年 7个平年，即有“366×2+365×7”天。 ∵ 366×2≡2×2≡4（mod 7）， 365×7≡1×7≡0（mod 7）， ∴366×2+365×7≡2×2+1×7≡4+0≡4（mod 7） 答：2010年的国庆节是星期五
同余的应用举例 例2判定21991+1、2198+1是否为质数。 分析:期望找到正整数m,使2191+1=0(modm), 21913-1(modm) 解:因为2三-1(mod3),所以, 2+1(-1)+1(-1)+1=0(mod3) 从而,21991为合数 因为4三-1(mod5),所以, 2 1998 +1=499}1≡(-1)9+1≡(-1)+1=0mod5) 从而,21981为合数
同余的应用举例 例2 判定2 1991 + 1 、 2 1998 + 1 是否为质数。 分析： 期望找到正整数m ,使 2 1991 + 1 ≡0 (mod m) , 即 2 1991 ≡- 1 (mod m) . 解： 因为2 ≡- 1 (mod 3) ,所以, 2 1991 + 1 ≡ (-1)1991 + 1≡ (- 1) + 1 = 0 (mod 3) . 从而, 2 1991 + 1 为合数. 因为4 ≡- 1 (mod 5) ,所以, 2 1998 + 1 =4999+ 1 ≡ (-1)999 + 1 ≡ (-1)+ 1 = 0 (mod 5) . 从而, 2 1998 + 1 为合数
2.0同余式定义和基本性质 定理3若ac= bc(mod m),(c,m)=d,则 a≡b(mod(m/d) 证明因为m|ca-b),于是(m/d)|(a-b)(c/d),又因为 (c,m)=d,则有(c/d,m/d)=1,因此(m(d)|(a-b),即: a≡bmod(m/d) o显然,由本定理可得如下推论. 推论若ac=b(modm),(c,m)=1,则: a=b(mod m)
2.0同余式定义和基本性质 定理 3 若ac=bc(mod m), (c,m)=d, 则 a b(mod (m/d)) 证明 因为m|c(a-b), 于是(m/d)|((a-b)(c/d)), 又因为 (c,m)=d, 则有((c/d, m/d)=1, 因此 (m/d)|(a-b), 即: a b(mod (m/d)). 显然, 由本定理可得如下推论. 推论 若 ac=bc(mod m), (c,m)=1,则: ab(mod m)
2.0同余式定义和基本性质 定理4 ①若a=b(modm),且d|m,则:a= b(mod m) ③若a=b(modm),则(a,m)=(b,m). ③a=b(modm;),(1≤i≤n),ifa=b(mod m1m2,…,mn1) 证明只给出③的证明,①和②读者完成 ③必要性由①知是成立的充分性:若a≡b(mod 1),1≤in,则:m|(ab),1si≤n,即(ab)是 m1,m2,mn的公倍数,从而也是[m1,m2,mn 的倍数,因此: a=b(mod m,m,,, m,D
2.0同余式定义和基本性质 定理4 ① 若ab(mod m), 且d|m, 则: ab(mod m). ③ 若ab(mod m), 则 (a,m)=(b,m). ③ ab(mod mi ), (1≤i≤n), iff ab (mod [m1 ,m2 ,…,mn ]). 证明 只给出③的证明, ①和②读者完成. ③必要性:由①知,是成立的. 充分性: 若a b(mod mi ), 1≤i≤n, 则: mi|(a-b), 1≤i≤n, 即(a-b)是 m1 ,m2 ,…,mn的公倍数, 从而也是[m1 ,m2 ,…,mn ] 的倍数, 因此: ab (mod [m1 ,m2 ,…,mn ])
2.0同余式定义和基本性质 o下面证明一个重要定理,从应用和理论来说都有非常 大的意义.尤其在理论上,它完全解决了判断给定的数 是否为素数的问题 定理(威尔逊定理) p为素数if(p-)!=-1(modp)
2.0同余式定义和基本性质 下面证明一个重要定理, 从应用和理论来说都有非常 大的意义. 尤其在理论上,它完全解决了判断给定的数 是否为素数的问题. 定理 (威尔逊定理) p为素数 iff (p-l)!-1(mod p)