フェルマーの小定理
$ p
が素数で
$ a
が任意の自然数のとき
$ a^p≡a\mod p
である
特に
$ p
が素数で
$ a
が
$ p
と互いに素な自然数のとき
$ a^{p-1}≡1\mod p
である
$ n < p
であれば
$ n^{p}\mod p = n
合同式 ≡
$ a≡b\mod n
は
$ a
と
$ b
を
$ n
で割った余りが等しいという意味
つまり
$ a\mod n=b\mod n
https://mathtrain.jp/fermat_petit