同余

这篇是<<What Is Mathematics>>以及<<算法导论>>中数论, 同余内容的笔记．

１．一般概念

如果有两个整数ａ和ｂ被５除有相同的余数， 我们称他们是”模5同余”的．

例如, ．这里2和7是模5同余的.

一般地说，　如果整数ａ和ｂ用ｄ除有相同的余数，即如果有一整数ｎ使a – b = n * d成立（这里ｄ是一固定整数），我们就说ａ和ｂ是模ｄ同余的．

关于同余的记号

a ≡ b ( mod d )

以下三个命题是等价的

1. ａ和ｂ是模ｄ同余的
2. 存在某个整数ｎ，使a = b + n d
3. ｄ整除ａ－ｂ

对于一个一般的关系式ａ＝ｂ，在形式上最重要的性质如下

1. 恒有a = b
2. 如果a = b，则b = a
3. 如果a = b，b = c，则a = c

再有如果ａ＝ａ’，ｂ＝ｂ’则

1. a + b = a’ + b’
2. a – b = a’ – b’
3. a * b = a’ * b’

当关系a = b用同余关系a ≡ b ( mod d )代替时, 这些性质仍然成立

1. 恒有a≡a ( mod d )
2. 如果a≡b ( mod d ), 则b ≡ a ( mod d )
3. 如果a ≡ b( mod d ), 则b ≡ c( mod d ), 则a ≡ c ( mod d )

其次如果a ≡ a’ ( mod d ), b ≡ b’ ( mod d ), 则

1. a + b ≡ a’ + b’ ( mod d )
2. a – b ≡ a’ – b’ ( mod d )
3. a * b ≡ a’ * b’ ( mod d )

关于后三个命题的证明

a = a’ + r * d, b = b’ + s * d

a + b = a’ + b’ + ( r + s ) * d

a – b = a’ – b’ + ( r – s ) * d

a * b = a’ * b’ + ( a’ * s + b’ * r + s * r * d ) * d

关于a * b ≡ a’ * b’ ( mod d )这条性质，我们可以的得到一个应用

由于　10 ≡ -1 ( mod 11 )

连续地用同余式乘它自己，得到

10 ^ 2 ≡ ( -1 ) * ( -1 ) = 1 ( mod 11 )

10 ^ 3 ≡ -1 ( mod 11 )

10 ^ 4 ≡ 1 ( mod 11 )

．．．．．．

这表面对于任何一个十进制整数

（　这里 a[0], a[1]的写法用来分别表示个位, 十位并以此类推．）

被11除后的余数，与它的数码交替变号求和

t = a[0] – a[1] + a[2] – a[3] + …

被11除后的余数是一样的，因为

…

而11, 10 ^ 2 – 1, 10 ^ 3 + 1…所有这些数每一个和0都是模11同余的，因此z – t也是这样，所以z被除与t被11除有相同的余数．那么一个数能被11整除的条件是它的数码交替变号之和能被11整除．

例如3 – 1 + 6 – 2 + 8 – 1 + 9 = 22, 数z = 3162819能被11整除

找一个被3或9整除的规律更加简单了.10 ≡ 1 ( mod 3 或 9 ) , 10 ^ n ≡ 1 ( mod 3 或 9 ).即一个整数z的所有数码之和能被3或9整除，那么整数z就能被3或9整除．

再对于模7同余．

10 ≡ 3, 10 ^ 2 ≡ 2, 10 ^ 3 ≡ 6, 10 ^ 4 ≡ 4, 10 ^ 5 ≡ 5, 10 ^ 6 ≡ 1……

然后就都是循环了，因此整数z被7整除的条件是表达式

r = a[0] + a[1] * 3 + a[2] * 2 + a[3] * 6 + a[4] * 4 + a[5] * 5 + a[6] * 1 + …

r 能被7整除

对于整数的普遍规律: 仅当a = 0或b = 0时，a * b = 0.推广可以得到

(7) 仅当a ≡ 0 或 b ≡ 0( mod d )时，有a * b ≡ 0 ( mod d ), 并且d为素数

２．费马小定理

如果p是任意一个不能整除整数a的素数,则

≡

这意味着a的( p – 1 )次幂被p除后余1

举一些例子:

≡ , ≡ , ≡ .

以及 2 ^ 12 ≡ ( mod 13 ), 5 ^ 10 ≡ 1 ( mod 11 )

我们可以利用同余式乘法性质来验证这两个式子

2 ^ 4 = 16 ≡ 3 ( mod 13 ),                            5 ^ 2 ≡ 3 ( mod 11 )

2 ^ 8 ≡ 9 ≡ -4 ( mod 13 ),                           5 ^ 4 ≡ 9 ≡ -2 ( mod 11 )

2 ^ 8 ≡ 9 ≡ -4 ( mod 13 ),                           5 ^ 4 ≡ 9 ≡ -2 ( mod 11 )

2 ^ 12 ≡ -4 * 3 = 12 ≡ 1 ( mod 13 ),         5 ^ 8 ≡ 4 ( mod 11 )

                                                                               5 ^ 10 ≡ 3 * 4 = 12 ≡ 1 ( mod 11 )

 

为了证明费马定理,考虑a的倍数:

m_1 = a,

m_2 = 2 * a,

m_3 = 3 * a,

… …

m_( p – 1 ) = ( p – 1 ) * a

这些数中任意两个都不能模p同余，否则存在一对整数r,s, 满足1 <= r < s <= ( p – 1 )，使p成为

m_s – m_r = ( s – r ) * a 的一个因子．但由规律(7)知这是不可能的，因为s – r是小于p的，所以p不是 s – r的因子，而假设p又不是a的因子，同样地，这些数中没有一个能和0同余，因此数m_1, m_2, m_3……m_(p-1)必须相应地同余于数1, 2, 3, …, ( p – 1 ).故得出

m_1 * m_2 * m_3 …… m( p – 1 ) = 1 * 2 * 3 …… ( p – 1 ) * a ^( p – 1 ) ≡ 1 * 2 * 3 ……( p – 1 ) ( mod p )

记K = m_1 * m_2 * m_3 …… m( p – 1 )，原式就变成

K * ( a ^ ( p – 1 ) – 1 ) ≡ 0 ( mod p )

但因为K的因子没有能被p整除的，所以K不能被p整除，因而由规律( 7 )可知，a ^ ( p – 1 ) 必须被p整除,即

a ^ ( p – 1 ) – 1 ≡ 0 ( mod p )

这就是费马小定理．

３．二次剩余

当p为奇数时，有p = 2 * p’ + 1则：

a ^ ( p – 1 ) – 1 = a ^ ( 2 * p’ ) – 1 = ( a ^ p’ – 1 ) * ( a ^ p’ + 1 ) ≡ 0 ( mod p )

这说明或者( a ^ p’ – 1 )或者( a ^ p’ + 1 )必须被p整除，所以对于任一素数p > 2和任一不被p整除的数a有：

或有a ^ ( ( p – 1 ) / 2 ) ≡ 1, 或有 a ^ ( ( p – 1 ) / 2 ) ≡ -1 ( mod p ).

近代数论出现后，数学家就很感兴趣地去寻找什么样的数a使第一种情形成立，什么样的数a使第二种情形成立.假设a与某个数x的平方是模p同余的，即：

a ≡ x ^ 2 ( mod p )

则a ^ ( ( p – 1 ) / 2 ) ≡ x ^ ( p – 1 )，而它按照费马定理是模p同余于1的．

一个数a，如果不是p的倍数且模p同余于某个数的平方，则称a为p的二次剩余．

而一个不是p的倍数的数b，不同余于任何数的平方，称它为p的非二次剩余．

每一个p的二次剩余a满足同余式a ^ ( ( p – 1 ) / 2 ) ≡ 1 ( mod p )，不难证明对每一个非二次剩余b，有同余式b ^ ( ( p – 1 ) / 2 ) ≡ -1 ( mod p )．更进一步，在数1, 2, 3, ……, p – 1中恰有( p – 1 ) / 2个二次剩余和( p – 1 ) / 2个非二次剩余．

对于两个不同素数p和q：

如果乘积( p – 1 ) / 2 * ( q – 1 ) / 2是偶数，则q是p的二次剩余必须而且只须p是q的二次剩余．

在乘积( p – 1 ) / 2 * ( q – 1 ) / 2 是奇数时，这情形相反，p是q的剩余必须而且只须q是p的非剩余．

这也就是二次互反律．

对于二次互反律的举例：

偶数情况:：取p=5，q=11，由于 乘积是偶数，则 ，11是二次剩余(mod 5)；并且，5是二次剩余(mod 11)。

奇数情况：取p=7，q=11，由于 乘积是奇数， ，11是二次剩余(mod 7)；但是 ，7是非二次剩余(mod 11)。