フェルマーの小定理を拡張してみよう
法の素数を２乗したらどうなるの？
ここから予想できること。
法が素数５の場合は４乗で１と合同 ⇒ mod（ｍ４，ｐ）≡１
法が素数ｐと素数ｑの積の場合は(ｐ－１)(ｑ－１)乗で１と合同 ⇒ mod（ｍ(ｐ－１)(ｑ－１)，ｐｑ）≡１
では法がｐ2の場合は何乗すればいいのだろう？
ｐの場合はｍ(=4)とｐ(=5)の互いに素な数をかけ合わせた ⇒１・２・３・４≡４・８・１２・１６(mod 5)
つまり、ｍ４・１・２・３・４≡１・２・３・４ だから、ｍ４≡１ (mod 5)
積の場合はｐｑ（互いに素な数）をかけ合わせた ⇒（ｐ－１）個と（ｑ－１）個をかけ合わせる。
（素な数をかけ合わせても素）
とすると、ｐ２の素な数の個数を数える⇒素でない数を引く⇒ｐ２個－ｐ個
（２５までの数で素でない数を数えてみよう）
この場合は２５－５＝２０となり、ｍ２０≡１ (mod ５２)となる。
一般的には、ｐn－ｐn-1＝ｐn・（ｐ－１）／ｐ と予想できる。
ちなみに、このことからオイラー関数φ（ｎ）の公式を求めることができる。