下载文档原格式
510011 0010 1010 1101 0001 0100 1011第四章同余式、幂与费马小定理张志强智能信息处理研究中心 510011 0010 1010 1101 0001 0100 1011智能信息处理研究中心2同余式•如果m 整除a-b ，我们说a 与b 模m 同余，并记为a ≡b( mod m)–例如，5|(7-2), 6|(47-35)–我们有7 ≡2( mod 5), 47 ≡35 ( mod 6)•如果a除以m得余数r，则a与r模m同余，注意0≤r <m，因此任意一个整数均与0‾m-1之间的一个数模m同余。
数m叫做同余式的模。
510011 0010 1010 1101 0001 0100 1011智能信息处理研究中心3同余式的性质•具有相同模的同余式与通常的等式类似a 1 ≡b 1(mod m), a 2≡b 2(mod m)，则有a 1±a 2≡b 1±b 2(mod m), a 1a 2≡b 1b 2(mod m)•注意：用数除同余式并非总是可能的，即ac ≡bc(mod m)，则a ≡b(mod m)未必成立。
–例如，15*2 ≡20*2(mod 10)，但15≡20(mod 10)510011 0010 1010 1101 0001 0100 1011智能信息处理研究中心4同余式的性质•特别是–uv ≡0(mod m)，–但u ≡0(mod m)，且v ≡0(mod m)–例如6*4 ≡0(mod 12)，但6 ≡0(mod 12)，且4 ≡0(mod 12)•然而，当gcd(c,m)=1时，则可以从同余式ac ≡bc(mod m)两边消去c。
有兴趣的同学可以尝试着去证明一下这个结论。
510011 0010 1010 1101 0001 0100 1011智能信息处理研究中心5带未知数的同余式•如，x+12≡5(mod 8)，要求解出满足上述条件的x–我们可以按照一般的解方程方法处理，如两边同时减去12，得x ≡5-12 ≡-7(mod 8)，或者可用等价解x ≡1(mod 8)来表示–注意：-7与1对模8是相同的，因为他们的差被8整除–练习：解4x ≡3(mod 19)510011 0010 1010 1101 0001 0100 1011智能信息处理研究中心6带未知数的同余式•如果其他方法失效，存在一个通用方法“穷举法”。
m n 数论(四)（同余）严文兰1. 已知( x - y )( y - z )(z - x ) = x + y + z ，求证27 | x + y + z2. 证明11,111,1111,中无平方数。
3. 证明 2 + 2n 2 + 2(n + 1)2 + 32n +1 不能分成三个整数的平方和。
4. 设(1 + 2 )21 = a + b 2, a , b ∈ Z ，求(b , 27) 。
5. 求最小正整数n ，使得 x 3 + x 3 + + x 3 = 20022002 有整数解。
1 2 n6. 求( + 5)2000 的十进制表示中小数点前第一位数字和小数点后第一位数字。
7. 对每个正整数k ，存在无理数α > 1 ，使k | [α n ](n = 1, 2, ) 。
8. 已知a = a = 1, a = 3, a = a + 2a + a ，求证：对任意m ∈ Z + ，存在n ∈ Z + 使1 2 3 n n -1 n -2 n -3得m | a n 。
3l 3m 3n 9. 设三角形的三边长为整数l , m , n , l > m > n > 0 ，已知{ } = { } = { }，其中 {x } = x - [x ]，求这种三角形周长的最小值．104 104 10410. 设 k , l 是给定的两个正整数，证明：有无穷多个正整数m ≥ k ，使得C k 与l 互素。
11. 已知 p 为素数，证明C p ≡ n[ ](mod p ) 。
p12. 求方程 ( x + y )( xy + 1) = 2z 的正整数解。
13. 证明：存在无穷多个正整数n ，使得n 2 + 1 无平方因子。
22n +1 n练习1. 已知(a , m ) = 1 ，证明同余方程ax ≡ b (mod m ) 在模m 下有唯一解。
2. 对任意 n , k ∈ Z + , f (n , k ) = 2n 3k + 4n k +10 都不能分解成若干(≥ 2) 个连续自然数之积。
