 | 「フェルマーの小定理」というキーワードで調べれば多分分かると思いますが、
自然数の素数qに対して、aをqと互いに素な整数とすると、
a^1, a^2, a^3, ・・・, a^(q-1)は全て法qで非合同で、特に
a^(q-1) ≡ 1 (mod q)
が成立するという定理です。
上記を使うとnを自然数としてa^n ≡ 1 (mod q)ならばnはq-1の倍数と言えます。
何故なら、nをq-1で割った商をs, 余りをr、但し0 ≦ r < q-1とすると、
a^n = a^{s(q-1)+r} = {(a^(q-1))^s}{a^r} ≡ {1^s}{a^r} = a^r (mod q)
もし、0 < r < q-1とすれば、q-1より小さい自然数rで、a^r ≡ 1 (mod q)となり、
フェルマーの小定理に反しますので、r = 0となることが必要です。
よって、n = s(q-1)となります。
|