同余定理
正整数$m$, 若整数$a$, $b$满足$a-b$能够被$m$整除, 即$(a-b)/m$得到整数
则称整数$a$与$b$对模$m$同余, 记作
$a≡b(mod$ $m)$
对模$m$同余是整数的一个等价关系
$a≡b(mod$ $m)$ 等价 $a\%m = b\%m$
例如, $26≡2(mod 12)$
$a≡b(mod$ $m)$ 等价 $a^{p}≡b^{p} (mod$ $m)$
费马小定理定义
若 $p$ 为质数, 则$a^{p}≡a(mod$ $p)$, 即 $a^{p-1}≡1(mod$ $p)$
费马小定理通常用来检验一个数是否是素数, 是素数的必要非充分条件
满足费马小定理检验的数未必是素数, 这种合数叫做卡迈克尔数($Carmichael Number$)
最小卡迈克尔数是$561$
对于质数 $p$
-
$n$ $mod$ $m = 0$, 则$\varphi(n \times p) = \varphi(n) \times p$
-
$n$ $mod$ $m \ne 0$, 则$\varphi(n \times p) = \varphi(n) \times (p-1)$