フェルマーの小定理
$ pが素数で$ \text{gcd}(a, p) = 1のとき、$ a^{\phi(p)}\equiv a^{p-1} \equiv 1 \;\text{mod}\; p https://scrapbox.io/files/6679585aa96837001c77f2aa.jpeg
すごく簡単に示せてオイラーの定理に感謝が止まらない momeemt.icon フェルマーの小定理の変形
$ pが素数のとき、どのような$ aに対しても$ x \equiv 1\;\text{mod}\;(p-1)なら、$ a^x \equiv a \;\text{mod}\; p.
証明
https://scrapbox.io/files/667961ac2c62ba001cc33a65.jpeg
フェルマーの小定理を満たす数が素数であるとは言えない