位数とは、aとnを1以上の整数、aとnが互いに素であるとした場合、以下の合同関係が成り立つ最小のkのことです。
a^[k]] ≡ 1 (___mod__ n)
このとき、kは、nの法におけるaの位数と表現されます。
例えば、7の法における2の位数を求めてみます。まず、合同関係は、以下です。
2^[k]] ≡ 1 (___mod__ 7)
k=1の場合、余りは2です。k=2の場合、余りは4です。よって、これらは合同関係は成り立ちません。
k=3の場合、余りは1です。よって、合同関係が成り立ち、7の法における2の位数は、3となります。
a^[m]] ≡ 1 (___mod__ n)が成り立つ場合、この合同関係の位数がkであれば、mは、kの倍数です。もしくは、kは、mの約数とも言えます。
mをkで割った.商.をq、余りをrとしたとします。すると、a^[m]]は、以下のように書き換えられます。このとき、kは、nを法とするaの位数とします。
a^[m]]=a^[kq+r]]
指数法則を利用して変形します。
=(a^[k]])^[q]]a^[r]]
kは、nを法とするaの位数なので、a^[k]]をnで割った場合、.商.をb、余りを1とすれば、a^[k]]は、nb+1と置けます。
=(nb+1)^[q]]a^[r]]
上記をnで割って、余りを求めると、nbが消えて、1^[q]]a^[r]]となります。さらに、1^[q]]=1なので、余りは、a^[r]]となります。
よって、a^[m]] ≡ 1 (___mod__ n)は、a^[r]] ≡ 1 (___mod__ n)と書き換えられます。
rは余りなので、0＜＝r＜kですが、kは位数なので、a^[r]] ≡ 1 (___mod__ n)が成り立つのは、r=0のときのみです。なので、mをkで割った余りは0です。
mがkの倍数であることを証明できました。