既約剰余類群と原始根 - epii's physics notes

$n$ を法として掛け算を行うことを考えます。 例えば $n = 10$ のとき $3 \times 7 = 21 \equiv 1 \mod 10$ といった具合に、計算結果に対して $\mod n$ をとることにします。 このときある自然数 $a$ の冪乗が $n$ 未満のほぼ全て[1]の自然数を埋め尽くすとき、このような $a$ を $n$ の原始根であるといいます。 たとえば $n = 7$ とすると $a = 3$ は次の表のようにこの条件を満たします。