乘法逆元

lfcemy · 2019-01-24 20:41:54 · 个人记录

费马小定理 (Ferma's little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有a^{\left(p-1\right)}\equiv1\pmod{p}。

皮埃尔·德·费马于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求，但是这个要求实际上是不必要的。

1736年，欧拉出版了一本名为“一些与素数有关的定理的证明”(拉丁文：Theorematum\ Quorundam\ ad\ Numero\ PRIMOS\ Spectantium\ Demonstratio)”的论文中第一次提出证明，但从莱布尼茨未发表的手稿中发现他在1683年以前已经得到几乎是相同的证明。

有些学家独立制作相关的假说（有时也被错误地称为中国的假说），当成立 时，p是素数。这是费马小定理的一个特殊情况。然而，这一假说的前设是错的：例如，341，而341=11*31是一个伪素数。所有的伪素数都是此假说的反例。

如上所述，中国猜测仅有一半是正确的。符合中国猜测但不是素数的数被称为伪素数。

更极端的反例是卡迈克尔数： 假设a与561互质，则 a560被561除都余1。这样的数被称为卡迈克尔数，561是最小的卡迈克尔数。Korselt在1899年就给出了卡迈克尔数的等价定义，但直到1910年才由卡迈克尔（Robert Daniel Carmichael）发现第一个卡迈克尔数：561。1994年William\ Alford、Andrew\ Granville及Carl Pomerance证明了卡迈克尔数有无穷多个。

若a,b,c为任意3个整数,p为正整数，且\gcd(p,c)=1，则当a*c\equiv b*c\left(mod\ p\right)时，有a\equiv b\left(mod\ p\right)。

证明：