冪の余りの周期と元の位数

方針：余りは $n$ 通りしかないので、累乗を $n+1$ 個並べると同じ余りが 2 回出る。そこから $a$ の累乗を約分して $1$ を作る。
段 1（同じ余りを見つける）。$a^1,a^2,\dots,a^{n+1}$ の $n+1$ 個を $n$ で割った余りは、$0,1,\dots,n-1$ の $n$ 通りのどれかである。個数の方が多いので、余りが等しい 2 つがある（鳩の巣原理）。それを $a^i$ と $a^j$（$1\le i< j\le n+1$）とすると、$a^j\equiv a^i\pmod n$ である。
段 2（約分する）。$\gcd(a,n)=1$ なので、合同式の割り算と逆元 により $a$ は逆元 $a'$ をもつ（$aa'\equiv1$）。段 1 の式の両辺に $a'$ を $i$ 回掛けると、左辺は $a^j(a')^i=a^{j-i}(aa')^i\equiv a^{j-i}$、右辺は $a^i(a')^i=(aa')^i\equiv1$ になる。よって $a^{j-i}\equiv1\pmod n$ であり、$d=j-i$ は正の整数である。$\square$

方針：指数 $k$ を $d$ で割った余りに注目する。$d$ が「最小」であることを使って、余りが $0$ でなければならないことを示す。
段 1（1 の「ならば」）。$d$ が $k$ を割るとき、$k=dm$ と書くと、累乗の規則により $a^k=(a^d)^m\equiv1^m=1$ である。
段 2（1 の「そのときに限る」）。$a^k\equiv1$ とする。$k$ を $d$ で割って $k=dq+r$（$0\le r< d$）とすると
$$ a^k=(a^d)^q\cdot a^r\equiv1^q\cdot a^r=a^r\pmod n $$
なので $a^r\equiv1$ である。もし $r\ge1$ なら、$r$ は $a^r\equiv1$ を満たす正の整数で $d$ より小さく、$d$ が最小であることに反する。よって $r=0$ であり、$d$ は $k$ を割る。
段 3（2）。$k\ge l$ としてよい。$a$ は逆元 $a'$ をもつので、$a^k\equiv a^l$ の両辺に $a'$ を $l$ 回掛けると $a^{k-l}\equiv1$ になる。逆に $a^{k-l}\equiv1$ なら両辺に $a^l$ を掛けて $a^k\equiv a^l$ である。よって $a^k\equiv a^l$ と $a^{k-l}\equiv1$ は同値であり、1 によってこれは「$d$ が $k-l$ を割る」、つまり $k\equiv l\pmod d$ と同値である。
段 4（3）。$0\le i< j\le d-1$ で $a^i\equiv a^j$ とすると、2 により $d$ は $j-i$ を割る。しかし $0< j-i< d$ なので、これは起こらない。$\square$

方針：合同式の割り算と逆元 の「逆元をもつ $\iff$ 最大公約数が $1$」を使い、$r$ が逆元をもつことを示す。
段 1。$x,y$ は $n$ と互いに素なので、逆元 $x',y'$ をもつ（$xx'\equiv1$、$yy'\equiv1$）。
段 2。積の規則により $r\cdot(y'x')\equiv(xy)(y'x')=x(yy')x'\equiv x\cdot1\cdot x'=xx'\equiv1\pmod n$ である。よって $r$ は逆元 $y'x'$ をもち、$\gcd(r,n)=1$ である。
段 3。$r=0$ なら $r\cdot(y'x')=0$ で、$0\equiv1\pmod n$ となるが、$n\ge2$ なのでこれは起こらない。よって $1\le r\le n-1$ であり、$r\in U_n$ である。$\square$

方針：ex-cgord-cosets13 と同じく、$U_n$ を $d=\operatorname{ord}_n(a)$ 個ずつの組に分ける。組がどれも $d$ 個からなり、重ならず、全体を覆うことを示せば、$\varphi(n)$ は $d$ の倍数になる。
段 0 は準備である。$a$ を $1$ 以上 $n-1$ 以下の数に取り替え、組を作るもとになる集合 $H$ を定める。
段 0-1（$a$ と余り $r$ は同じ指数で $1$ と合同になる）。$a$ を $n$ で割って $a=nq+r$（$0\le r< n$）とすると、$a-r=nq$ なので $a\equiv r\pmod n$ である。合同式の計算規則 の累乗の規則により、すべての正の整数 $k$ について $a^k\equiv r^k\pmod n$ である。よって $a^k\equiv1$ と $r^k\equiv1$ は同じ $k$ で成り立つ（対称律と推移律）。
段 0-2（$r$ は $U_n$ に入り、位数は $a$ と同じ）。$\gcd(a,n)=1$ なので、合同式の割り算と逆元 により $a$ は逆元 $a'$ をもつ（$aa'\equiv1$）。$r\equiv a$ の両辺に $a'$ を掛けると、積の規則により $ra'\equiv aa'\equiv1$ なので、$a'$ は $r$ の逆元でもある。合同式の割り算と逆元 の「逆元をもつ $\iff$ 最大公約数が $1$」により $\gcd(r,n)=1$ である。$r=0$ なら $\gcd(0,n)=n\ge2$ となってしまうので $r\ne0$ であり、$1\le r\le n-1$ である。よって $r\in U_n$ である。$\gcd(r,n)=1$ なので $r$ の位数が定義でき、段 0-1 により $r^k\equiv1$ となる $k$ は $a^k\equiv1$ となる $k$ と同じなので、その最小値である $r$ の位数は $a$ の位数に等しい。したがって、$a$ を $r$ に取り替えても定理の主張は変わらないので、以下 $a\in U_n$ とする。
段 0-3（$H$ を作る）。$m=0,1,2,\dots$ について、$a^m$ を $n$ で割った余りを $h_m$ と書く（$a^0=1$ なので $h_0=1$）。$H=\{h_0,h_1,\dots,h_{d-1}\}$ とおく。thm-cgord-exponent の 3 により $h_0,\dots,h_{d-1}$ はすべて異なるので、$H$ はちょうど $d$ 個の数からなる。
段 0-4（$H$ は $U_n$ に含まれる）。すべての $m\ge0$ について $h_m\in U_n$ であることを、$m$ についての帰納法で示す。$m=0$ では、$h_0=1$ は $1$ 以上 $n-1$ 以下（$n\ge2$ だから）で $\gcd(1,n)=1$ なので、$h_0\in U_n$ である。次に $h_{m-1}\in U_n$ とする。$a^{m-1}\equiv h_{m-1}$ に積の規則を使うと $a^m=a^{m-1}\cdot a\equiv h_{m-1}\cdot a\pmod n$ である。合同な数は $n$ で割った余りが等しい（合同式の計算規則）ので、$h_m$ は「$h_{m-1}$ と $a$ の積を $n$ で割った余り」に等しい。$h_{m-1}$ と $a$ はどちらも $U_n$ に入るので、lem-cgord-closed により $h_m\in U_n$ である。特に $H\subset U_n$ である。
段 0-5（どの累乗の余りも $H$ に入る）。$m\ge0$ を $d$ で割った余りを $m'$ とする（$0\le m'\le d-1$）。$m\equiv m'\pmod d$ なので、thm-cgord-exponent の 2 により $a^m\equiv a^{m'}$ であり、$h_m=h_{m'}\in H$ である。
段 0-6（組を定める）。$x\in U_n$ に対し、$H$ の各数に $x$ を掛けて $n$ で割った余りの集合を $xH$ とする。
段 1（$xH$ は $U_n$ に含まれ、ちょうど $d$ 個）。lem-cgord-closed により $xH\subset U_n$ である。$h,h'\in H$ で $xh\equiv xh'$ なら、$\gcd(x,n)=1$ なので約分して（合同式の割り算と逆元）$h\equiv h'$、$H$ の数は $n$ 未満なので $h=h'$ である。よって $H$ の異なる数は $xH$ の異なる数に移り、$xH$ はちょうど $d$ 個の数からなる。
段 2（どの数もどれかの組に入る）。$1\in H$ なので、$x=x\cdot1$ は $xH$ に入る。
段 3（共通の数があれば同じ組）。$xH$ と $yH$ に共通の数があるとし、$xa^i\equiv ya^j$（$0\le i,j\le d-1$）とする。両辺に $a^{d-i}$ を掛けると、$a^d\equiv1$ により
$$ x\equiv xa^d=xa^i\cdot a^{d-i}\equiv ya^j\cdot a^{d-i}=ya^{j+d-i}\pmod n $$
である。すると $xH$ の任意の数 $xa^k$ について $xa^k\equiv ya^{j+d-i+k}$ であり、段 0-5 により $a^{j+d-i+k}$ の余りは $H$ に入るので、$xa^k$ の余りは $yH$ に入る。よって $xH\subset yH$ である。段 1 により両方とも $d$ 個なので、$xH=yH$ である。
段 4（数える）。段 2 により $U_n$ のどの数もどれかの組に入り、段 3 により異なる組は重ならない。段 1 によりどの組もちょうど $d$ 個である。組の数を $t$ とすると $\varphi(n)=td$ であり、$d$ は $\varphi(n)$ を割る。$\square$

方針：thm-cgord-lagrange と thm-cgord-exponent の 1 を組み合わせる。
thm-cgord-lagrange により $\operatorname{ord}_n(a)$ は $\varphi(n)$ を割る。thm-cgord-exponent の 1 により $a^{\varphi(n)}\equiv1$ である。$n=p$ が素数なら、$1$ から $p-1$ までのどの数も $p$ と互いに素なので $\varphi(p)=p-1$ である。$\square$

方針：答は $(1,p)$（$p$ は任意の素数）、$(2,2)$、$(3,3)$ である。$n\ge2$、$p$ が奇数のときは、$n$ の最小の素因数 $q$ を法とする $p-1$ の位数を調べて $q=p$ を導き、$n=p$ に絞る。最後に二項展開で $p$ を決める。
段 1（$n=1$）。$n^{p-1}=1$ はどの整数も割るので、$(1,p)$ はすべての素数 $p$ について条件を満たす。以下 $n\ge2$ とする。
段 2（$p=2$）。$n\le4$ で、条件は「$n^1$ が $1^n+1=2$ を割る」なので $n=2$ である。$(2,2)$ は条件を満たす。以下 $p$ は奇数の素数とする。
段 3（$n$ は奇数）。$p-1$ は偶数なので $(p-1)^n$ は偶数、$(p-1)^n+1$ は奇数である。奇数を割る数は奇数なので、$n^{p-1}$ は奇数であり、$n$ も奇数である。
段 4（最小の素因数 $q$）。$n\ge3$ は奇数なので、$n$ の最小の素因数 $q$ は $3$ 以上の素数である。$c:=p-1$ とおく。$q$ は $n$ を割り、$n$ は $n^{p-1}$ を割り、$n^{p-1}$ は $c^n+1$ を割るので、$q$ は $c^n+1$ を割る。つまり
$$ c^n\equiv-1\pmod q $$
である。もし $q$ が $c$ を割れば $c^n\equiv0$ で、$0\equiv-1$、つまり $q$ が $1$ を割ることになり、起こらない。よって $\gcd(c,q)=1$ である。上の式の両辺を 2 乗すると $c^{2n}\equiv1\pmod q$ である。
段 5（位数が割る数）。$d:=\operatorname{ord}_q(c)$ とする。段 4 と thm-cgord-exponent の 1 により $d$ は $2n$ を割る。$q$ は素数なので、cor-cgord-euler と thm-cgord-exponent の 1 により $d$ は $q-1$ も割る。
段 6（$d$ は $2$ を割る）。$d$ と $n$ の公約数 $e$ を考える。$e>1$ なら $e$ の素因数 $r$ があり、$r$ は $n$ を割るので $r\ge q$（$q$ が最小の素因数だから）、また $r$ は $d$ を通して $q-1$ を割るので $r\le q-1$ となり、矛盾する。よって $\gcd(d,n)=1$ である。合同式の割り算と逆元 の Bézout の等式により $du+nv=1$ となる整数 $u,v$ があり、両辺に $2$ を掛けると $2=d\cdot2u+2n\cdot v$ である。$d$ は $d\cdot2u$ と $2n$ を割るので $2$ を割る。よって $d=1$ か $d=2$ であり、どちらでも $c^2\equiv1\pmod q$ である。
段 7（$q=p$）。$n$ は奇数なので $n-1$ は偶数であり、
$$ c^n=\left(c^2\right)^{\frac{n-1}2}\cdot c\equiv1\cdot c=c\pmod q $$
である。段 4 と合わせて $c\equiv-1$、つまり $q$ は $c+1=p$ を割る。$p$ は素数で $q\ge3$ なので $q=p$ である。
段 8（$n=p$）。段 7 により $p$ は $n$ を割るので、$n$ は $p$ の倍数である。$n\le2p$ なので $n=p$ か $n=2p$ であり、段 3 により $n$ は奇数なので $n=p$ である。
段 9（$p$ を決める）。条件は「$p^{p-1}$ が $(p-1)^p+1$ を割る」になる。二項定理で展開すると
$$ (p-1)^p=\sum_{k=0}^{p}\binom pk p^k(-1)^{p-k} $$
である。$k=0$ の項は $(-1)^p=-1$（$p$ は奇数）、$k=1$ の項は $p\cdot p\cdot(-1)^{p-1}=p^2$、$k=2$ の項は $\binom p2p^2(-1)^{p-2}=-p^3\cdot\frac{p-1}2$ で、$\frac{p-1}2$ は整数なので $p^3$ の倍数である。$k\ge3$ の項も $p^k$ を含むので $p^3$ の倍数である。よって
$$ (p-1)^p+1=p^2+(p^3\text{ の倍数}) $$
であり、$(p-1)^p+1$ は $p^2$ で割り切れるが $p^3$ では割り切れない。$p^{p-1}$ で割り切れるためには $p-1\le2$ が必要であり、奇数の素数 $p$ では $p=3$ である。実際 $(n,p)=(3,3)$ では $2^3+1=9=3^2$ で、条件を満たす。
段 1〜段 9 から、答は $(1,p)$（$p$ は任意の素数）、$(2,2)$、$(3,3)$ である。$\square$