同余

Posted by

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

1.一般概念

如果有两个整数a和b被5除有相同的余数, 我们称他们是”模5同余”的.

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

一般地说, 如果整数a和b用d除有相同的余数,即如果有一整数n使a – b = n * d成立(这里d是一固定整数),我们就说a和b是模d同余的.

关于同余的记号

a ≡ b ( mod d )

以下三个命题是等价的

  1. a和b是模d同余的
  2. 存在某个整数n,使a = b + n d
  3. d整除a-b

对于一个一般的关系式a=b,在形式上最重要的性质如下

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

再有如果a=a’,b=b’则

  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 )

......

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

z = a[0] + a[1] * 10 + a[2] * 10 ^ 2 + ... + a[n] * 10 ^ n

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

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

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

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

z - t = a[1] * 11 + a[2] * ( 10 ^ 2 - 1  ) + a[3] * ( 10 ^ 3 + 1 ) + a[4] * ( 10 ^ 4 - 1 )

而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 }1 ( mod  p )

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

举一些例子:

10 ^ 61 ( mod 7 ), 10 ^ 21 ( mod 3 ), 10 ^ 101 ( mod 11 ).

以及 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)。

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注