【同余】-定义&计算&应用

2019-04-14 17:17发布

站内文章 / 模拟电子
14922 0 1611

同余符号

两个整数a，b，若它们除以正整数m所得的余数相等，则称a，b对于模m同余 记作a equiv b pmod{m} 读作a同余于b模m，或读作a与b关于模m同余。 比如26 equiv 14 pmod{12}。 同余于的符号是同余相等符号 ≡。统一码值为 U+2261。但因为方便理由，人们有时会把它(误)写为普通等号 (=)。

性质

整除性

a equiv b pmod{m} Rightarrow ccdot m=a-b, c in mathbb{Z} (即是说 a 和 b 之差是 m 的倍数)
换句话说，a equiv b pmod{m} Rightarrow m mid(a-b)[1]

传递性

left. egin{matrix}a equiv b pmod{m} \b equiv c pmod{m}end{matrix} ight} Rightarrow a equiv c pmod{m}

保持基本运算

left. egin{matrix}a equiv b pmod{m} \c equiv dpmod{m}end{matrix} ight} Rightarrow left{ egin{matrix} a pm c equiv b pm d pmod{m} \ ac equiv bd pmod{m} end{matrix} ight.
这性质更可进一步引申成为这样：
a equiv b pmod{m} Rightarrow egin{cases} an equiv bn pmod{m}, forall n in mathbb{Z} \ a^n equiv b^n pmod{m}, forall n in mathbb{N}^0end{cases}

除法原理

a equiv b pmod{cn} Rightarrow a equiv b pmod n
left. egin{matrix} a equiv b pmod{m} \ n|m end{matrix} ight} Rightarrow a equiv b pmod n[1]
left. egin{matrix} ac equiv bc pmod{m} \ (c, m) = 1 end{matrix} ight} Rightarrow a equiv b pmod m[2] left. egin{matrix} a equiv b pmod{m_1} \ a equiv b pmod{m_2} \ vdots \ a equiv b pmod{m_n} \ (n ge 2) end{matrix} ight} Rightarrow a equiv b pmod{[m_1,m_2,cdots,m_n]}[3]

例子

  • 求自然数a的个位数字，就是求a与哪一个数对于模10同余。
  • 10equiv 1 ( extrm{mod } 3), 10^{n}equiv 1 ( extrm{mod } 3), 10001equiv 10^{4}+1equiv 1+1 ( extrm{mod } 3)。

参考链接： 同余：http://zh.wikipedia.org/wiki/%E5%90%8C%E9%A4%98点击打开链接 同余关系：http://zh.wikipedia.org/wiki/%E5%90%8C%E9%A4%98%E9%97%9C%E4%BF%82点击打开链接

热门文章