乗法的位数
乗法的位数
前々ページの定理2 (9)
から、$a^e\equiv 1\Mod{n}$ となる整数 $e$ 全体は
倍数と約数: 定理3
の条件を満足するので、
次のことがわかる。
$$a^g\equiv 1\Mod{n}$$
となる最小の正の整数 $g$ をとると、
$$a^e\equiv 1\Mod{n}\Longleftrightarrow g\mid e$$
が成り立つ。この整数 $g$ を $n$ を法とする $a$ の乗法的位数 (multiplicative order) あるいは単に位数という。$\ord_n(a)$ とかく場合もあるが、この記号は
付値
をあらわす場合もあるので注意が必要である。
Fermatの小定理 および Eulerの定理 より、次のことがすぐにわかる。
$n$ を法とする $a$ の位数は $\varphi(n)$ を割り切る。
このことから、次のような定理を示すことができる。
$n$ が整数で $p$ が $n^2+1$ の素因数ならば、$p=2$ または $p\equiv 1\Mod{4}$.
$n^2+1\equiv 0\Mod{p}$ ならば
$$n^4-1\equiv (n^2+1)(n^2-1)\equiv 0\Mod{p}$$
となる。よって $p$ を法とする $n$ の位数は $4$ の約数である。$n^2-1\equiv 0\Mod{p}$ ならば
$p\mid (n^2+1)-(n^2-1)=2$ より、$p=2$ である。よって $p$ が奇数ならば $p$ を法とする $n$ の位数は $4$ に一致するので
定理1
より $4$ は $p-1$ を割り切る。
$4n+1$ の形の素数は無数に存在する。
実数 $X>0$ を任意にとり、$P$ を $X$ より小さいすべての素数の積とする。$P^2+1$ の素因数 $q$ をひとつとる。
$q$ は $P$ を割り切らない。実際 $q\mid P$ ならば $q\mid 1=(P^2+1)-P^2$ となり、矛盾する。
一方 $P$ は $2$ で割り切れるから、$q$ は奇数なので、
定理4.2
より $q\equiv 1\Mod{4}$ となる。
よって $q$ は $X$ より大きい $4n+1$ の形の素数である。$X$ は任意にとれるから $4n+1$ の形の素数は無限に多く存在する。
$x^n\equiv 1\Mod{p}\Longleftrightarrow$ $x\Mod{p}$ の位数が $\gcd(n, p-1)$ を割り切る
$\Longleftrightarrow x^{\gcd(n, p-1)}\equiv 1\Mod{p}$.
$x^n\equiv 1\Mod{p}$ ならば $x$ の位数は $n$ の約数、かつ位数が $p-1$ の約数でもあるので
倍数と約数:命題3
より位数は $\gcd(n, p-1)$ の約数となるので
$$x^{\gcd(n, p-1)}\equiv 1\Mod{p}$$
となる。
このことは $x^n\equiv 1\Mod{p}$ ならば、
Bezoutの補題
より $an+b(p-1)=\gcd(n, p-1)$ となる $a, b$ がとれるので
$$x^{\gcd(n, p-1)}\equiv x^{an}x^{b(p-1)}\equiv 1\Mod{p}$$
となることからもわかる。
逆に $x^{\gcd(n, p-1)}\equiv 1\Mod{p}$ ならば明らかに $x^n\equiv 1\Mod{p}$ となる。
参考文献
