专题_同余

lzk05_lzk0530

数学上，两个整数除以同一个整数，若得相同余数，则二整数同余（英文：Modular arithmetic；德文：Kongruenz）。同余理论常被用于数论中。最先引用同余的概念与符号者为德国数学家高斯。

两个整数a，b，若它们除以整数m所得的余数相等，则称a，b对于模m同余

记作 a ≡ b (mod m)

读作a同余于b模m，或读作a与b关于模m同余。

比如 24 ≡ 13(mod 11)

1 反身性 a ≡ a (mod m)
2 对称性 若a ≡ b 则b ≡ a (mod m)
3 传递性 如果a ≡ b (mod m)，b ≡ c (mod m),那么a ≡ c (mod m)
4 线性运算 如果a ≡ b (mod m)，c ≡ d (mod m),那么a + c ≡ b + d (mod m)，a - c ≡ b - d (mod m)，a * c ≡ b * d (mod m)
5 除法  若ac ≡ bc (mod m) c!=0 则 a≡ b (mod m/(c,m))  其中(c,m)表示c,m的最大公约数
            特殊地 (c,m)=1 则a ≡ b (mod m)
6 乘方 如果a ≡ b (mod m)，那么a^n ≡ b^n (mod m)
7 若a ≡ b (mod m)，n|m,则 a ≡ b (mod n)
8 若a ≡ b (mod mi） i=1,2...n 则 a ≡ b (mod [m1,m2,...mn]) 其中[m1,m2,...mn]表示m1,m2,...mn的最小公倍数
9 费马小定理 若p为质数，则a^p ≡ a (mod p)  即a^(p-1) ≡ 1 (mod p)
另：求自然数a的个位数字，就是求a与哪一个数对于模10同余

[ 本帖最后由 lzk05_lzk0530 于 2008-4-5 09:13 编辑 ]

lzk05_lzk0530

写在前面的话：同余的性质实际上可以用已知的推导未知的，在此不再赘述，希望各位数学爱好者们能够自己探索。
相关习题
1.求2^（999） 次幂的最后两位数（初中生可做）
2.求证3^(1980)+4^(1981)能够被5整除（初中生可做）
3.求83^(50)除以8的余数（初中生可做）
4.数7^(355)的末四位数字是（初中生可做）
5.数10^(10)^(10)^(10）被77 除, 所得的余数是（高中生可做，初中生选做）
6.求具有如下性质的质数P的
最大值:存在1，2，……，p的两个排列（可以相同）a1，a2……ap和b1，b2……bp
使得a1*b1，a2*b2……ap*bp除以p所得余数各不相同9选做，有较大难度）

lzk05_lzk0530

1：考虑2^999除以100的余数
因为2^12=4096≡ -4(mod100)
所以2^999=(2^12)^83 *2^3≡ (-4)^83*2^3(mod100)
又4^6=2^12=4096≡ -4(mod100)
所以4^83=(4^6)^13*4^5≡-4^13*4^5≡-4^18≡-(4^6)^3≡-(-4)^3≡64(mod100)
所以2^999≡(-4)^83*2^3≡(-64)*2^3≡-2^9≡-512≡88(mod100)

lzk05_lzk0530

2.证明:3≡-2(mod5),3^2≡-1(mod5),4≡-1(mod5)
3^1980≡9^990≡(-1)^990(mod5),4^1981≡(-1)^1981(mod5)
3^1980+4^1981≡(-1)^990+(-1)^1981≡0(mod5)
命题得证

lzk05_lzk0530

3.高中解法：
83^50=(80+3)^50=80^50+C(1,50)*80^49*3^1+……C(49,50)*80^1*3^49+3^50
=8M+3^50(M属于Z）
3^50=9^25=(8+1)^25=8^25+C(1,25)*8^24+……C(24,25)*8^1+1=8N+1(N属于Z）
所以83^50除以8余数为1
注：二项式定理

lzk05_lzk0530

4：本题即求7^355除以10^4 所得的余数.
7^355 = 7 ×49^177 = 7 ×49 ×(50 - 1)^( 2 ×88)
= 7 ×49 ×(2 400 + 1)^ 88
≡7 ×49 ×( 1 + 2 400*C(1,88) )
≡343 ×[1 + 2 400 ×(100 - 12) ]
≡343 ×(1 - 2 400 ×12) ≡343 - 343 ×12 ×2 400
≡343 - 43 ×12 ×2 400 ≡343 - 103 200 ×12
≡343 - 3 200 ×12 ≡343 - 38 400
≡343 - 8 400 ≡- 8 057 ≡1 943 (mod 10^4 ) .
因此,7^355的末四位数字是1 943.

lzk05_lzk0530

5:令x =.10^(10)^(10)^(10）
注意到77=7*11，显然，x=（11-1）^(10)^(10)^(10）≡（-1）^(10)^(10)^(10）≡1
（mod11） （1）
因7与10互质，由费马小定理，得10^6≡1（mod7）
下面求(10)^(10)^(10）除以6的余数r（其中0小于等于r小于等于5）
注意到6=2*3，显然r≡0（mod2），且r≡(10)^(10)^(10）≡(3^2+1）^（10)^(10）≡1
（mod3）
于是,逐一代入r = 0 ,2 ,4 检验知,只有r = 4.
令(10)^(10)^(10）=6k+4（k属于正整数）
则x≡10^（6k+4)≡10^（6k）*10^4≡10^4≡3^4≡9^2≡2^2≡4(mod7） （2）
由（1）得x=11y+1（y属于整数）代入（2）得
11y+1≡4（mod7)，即11y≡3（mod7）
亦即-3y≡3（mod7）
故y ≡- 1 (mod 7) .
令y = 7 z + 6( z ∈Z) ,则x = 11 (7z + 6) + 1 = 77z + 67.
故x 被77 除所得的余数是67.

lzk05_lzk0530

6：先证明一个引理
引理(威尔逊定理) 对任何质数p，有
(p-1)! ≡- 1(mod p)． ①
引理的证明：当p=2、3时，式①显然成立．
当p>3时，我们证明：对任何2≤k≤p-2，必
存在k1 (2≤k1≤p-2，k 1≠k)，使kk1≡1（modp）
实际上，对2≤k≤p-2，，有(k，P)=1，从而，k，2k，…… ，pk 构成模p的完系．
于是必存在k1，（1≤k1≤p）使kk1≡1（modp）
显然k1不等于p，否则kk1≡0（modp），矛盾
此外，如果k1=1则由kk1≡1（modp）P)，得k≡l(mod p）
与2≤k≤p-2矛盾，如果k1=p-1，则由k（p-1)≡l（modp）得-k≡1（modp），亦与2≤k≤p-2矛盾，若k1=k由kk1≡1（modp）得k^2≡1（modp）
所以（k+1）（k-1）能被p整除但1≤k-1<k+1≤p-1<p，矛盾，因此2≤k1≤p-2，且k1不等于k。
由此可知，乘积2×3×…… ×(p-2)的各个因数
可以配成（p-3)/2对，，每对中两个数的积模p的余数为1，从而2*3*……（p-2)≡1（modp）。所以（p-1）！≡1*（p-1)≡-1（modp）