这篇是<<What Is Mathematics>>以及<<算法导论>>中数论, 同余内容的笔记.
1.一般概念
如果有两个整数a和b被5除有相同的余数, 我们称他们是”模5同余”的.
例如,
.这里2和7是模5同余的.
一般地说, 如果整数a和b用d除有相同的余数,即如果有一整数n使a – b = n * d成立(这里d是一固定整数),我们就说a和b是模d同余的.
关于同余的记号
a ≡ b ( mod d )
以下三个命题是等价的
- a和b是模d同余的
- 存在某个整数n,使a = b + n d
- d整除a-b
对于一个一般的关系式a=b,在形式上最重要的性质如下
- 恒有a = b
- 如果a = b,则b = a
- 如果a = b,b = c,则a = c
再有如果a=a’,b=b’则
- a + b = a’ + b’
- a – b = a’ – b’
- a * b = a’ * b’
当关系a = b用同余关系a ≡ b ( mod d )代替时, 这些性质仍然成立
- 恒有a≡a ( mod d )
- 如果a≡b ( mod d ), 则b ≡ a ( mod d )
- 如果a ≡ b( mod d ), 则b ≡ c( mod d ), 则a ≡ c ( mod d )
其次如果a ≡ a’ ( mod d ), b ≡ b’ ( mod d ), 则
- a + b ≡ a’ + b’ ( mod d )
- a – b ≡ a’ – b’ ( mod d )
- 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为素数
2.费马小定理
如果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 )
这就是费马小定理.
3.二次剩余
当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)。