満たすような数aもあるかもしれない。満たすkを、pを法とするaの位数(order)と呼ぶ。これを次のように書く。†[定義]p:素数とする。なるgを、pの原始元(原始根・生成元)という。gをp-1乗して初めて1になるような元のことである。例:p=5原始元はp-1となる値aということなので、4(=p-1=5-1)となる値は2と3である(括弧の中の値が原始元と覚えておけばよい)。原始元は2,3ということになる。[系]p:素数とする。一般に、必ずしも素数でない正整数m、mと素なaに対して、次が成り立つ。これをオイラーの定理と呼ぶのであった。先ほどと同様に考えて、aを何乗かすると法mの世界で1になる。成り立つような最小の正整数kを、mに関するaの位数という。正整数mに対しても原始元が定義できる。満たすgを、mの原始元と呼ぶ。乗したときに1になるものが4の原始元である。明らかに1乗の時点で1になっているから原始元ではない。4)で一向に1に一致しない。ゆえに、4の原始元は3のみである。原始元は元の位数と密接な関係を持っている。[定理]奇素数pに関するaの位数q(=ordp(a))は、p-1の約数である。[考察][証明]背理法を用いる。p-1を割り切らないと仮定する。次のような計算ができる。r<qであるが、qの最小性(位数の定義)に反するので矛盾。法が素数べきのときに、原始元が存在することを示す。[定理]n=pe、pは奇素数、e≧1のとき、法nに関する原始元が存在する。[証明][1]e=1のとき、[定理]「pが素数のとき、法pに関する原始元が存在する」より、題意が成り立つ。[2]e>1のとき法pe-1に関する原始元が存在すると仮定して、法peに関する原始元が存在することを示す。満たす整数aが存在する。これは次のように展開できる。(∵オイラー関数の性質)よって、[定理]「nが自然数、aをnと互いに素な整数とする。このとき、次は同値である。[1][2]以下の2条件が成り立つ。mはsの倍数である」より、次が成り立つ。←(*)また、法peに関するaの位数をmとすると、次が成り立つ。