Fermatの小定理と冪の余り

方針：$p-1$ 個の余りについて、(1) どれも $0$ でないこと、(2) どの 2 つも等しくないことを示す。すると、$1$ から $p-1$ までの $p-1$ 個の数を $1$ 回ずつ使い切るしかない。
段 1（どの余りも $0$ でない）。$1\le k\le p-1$ とする。$ka$ を $p$ で割った余りが $0$、つまり $p$ が $ka$ を割るとすると、rem-cgflt-euclid により $p$ は $k$ か $a$ を割る。$1\le k\le p-1$ なので $p$ は $k$ を割らない（$k$ は $p$ より小さい正の数である）。$a$ は仮定により $p$ で割り切れない。どちらも起こらないので、$ka$ の余りは $0$ でない。
段 2（どの 2 つの余りも異なる）。$1\le i< j\le p-1$ とし、$ia$ と $ja$ の余りが等しいとする。余りが等しいことは合同と同じ（合同式の計算規則）なので $ia\equiv ja$、つまり $p$ は
$$ ja-ia=(j-i)a $$
を割る。rem-cgflt-euclid により $p$ は $j-i$ か $a$ を割る。しかし $0< j-i< p$ なので $p$ は $j-i$ を割らず、$a$ も割らない。これは矛盾なので、$ia$ と $ja$ の余りは異なる。
段 3（数える）。段 1 により、$p-1$ 個の余りはどれも $1,2,\dots,p-1$ のどれかである。段 2 により、それらはすべて異なる。$p-1$ 個の異なる数が、$p-1$ 個の数からなる集合 $\{1,2,\dots,p-1\}$ に入っているので、この集合のどの数もちょうど 1 回ずつ現れる。$\square$

方針：ex-cgflt-proof-demo と同じく、$a,2a,\dots,(p-1)a$ の積を 2 通りに計算し、$(p-1)!$ で約分する。
段 1（積を 1 通り目に計算する）。$a$ を $p-1$ 回、$1,2,\dots,p-1$ を 1 回ずつ掛けることになるので
$$ a\cdot2a\cdot3a\cdots(p-1)a=a^{p-1}\cdot\bigl(1\cdot2\cdots(p-1)\bigr)=a^{p-1}\,(p-1)! $$
である。
段 2（積を 2 通り目に計算する）。$ka$ を $p$ で割った余りを $r_k$ とすると $ka\equiv r_k\pmod p$ である（$k=1,\dots,p-1$）。積の規則をくり返し使うと
$$ a\cdot2a\cdots(p-1)a\equiv r_1r_2\cdots r_{p-1}\pmod p $$
である。lem-cgflt-perm により $r_1,r_2,\dots,r_{p-1}$ は $1,2,\dots,p-1$ の並べ替えなので、掛ける順番を変えれば $r_1r_2\cdots r_{p-1}=1\cdot2\cdots(p-1)=(p-1)!$ である。
段 3（2 つを比べる）。段 1 と段 2 から
$$ a^{p-1}\,(p-1)!\equiv(p-1)!\pmod p $$
である。
段 4（$(p-1)!$ は $p$ で割り切れない）。$1\le k\le p-1$ について「$p$ は $k!$ を割らない」を、$k$ についての帰納法で示す。$k=1$ では $1!=1$ なので、$p$ は割らない。$k-1$ で成り立つとして、$p$ が $k!=(k-1)!\cdot k$ を割ったとすると、rem-cgflt-euclid により $p$ は $(k-1)!$ か $k$ を割る。前者は帰納法の仮定に反し、後者は $1\le k< p$ に反する。よって $p$ は $k!$ を割らず、特に $(p-1)!$ を割らない。
段 5（約分する）。$p$ の正の約数は $1$ と $p$ だけで、段 4 により $p$ は $(p-1)!$ を割らないので、$\gcd\bigl((p-1)!,p\bigr)=1$ である。合同式の割り算と逆元 の約分の条件により、段 3 の両辺を $(p-1)!$ で約分でき、$a^{p-1}\equiv1\pmod p$ を得る。$\square$

方針：thm-cgflt-fermat が使える場合と使えない場合に分ける。
段 1（$p$ が $a$ を割らないとき）。thm-cgflt-fermat により $a^{p-1}\equiv1$ である。両辺に $a$ を掛けると、積の規則により $a^p=a^{p-1}\cdot a\equiv1\cdot a=a$ である。
段 2（$p$ が $a$ を割るとき）。$a\equiv0\pmod p$ なので、累乗の規則により $a^p\equiv0^p=0$ である。$a\equiv0$ でもあるので、$a^p\equiv0\equiv a$ である。$\square$

方針：大きい方の指数を「小さい方＋$(p-1)$ の倍数」と書き、Fermat の小定理で $a^{p-1}$ を $1$ に置き換える。
段 1（書き直す）。$k$ と $l$ の役割を入れ替えてもよいので、$k\ge l$ とする。$k-l$ は $p-1$ の倍数で $0$ 以上なので、$k-l=(p-1)m$（$m$ は $0$ 以上の整数）と書ける。よって
$$ a^k=a^{l+(p-1)m}=a^l\cdot\left(a^{p-1}\right)^m $$
である。
段 2（置き換える）。thm-cgflt-fermat により $a^{p-1}\equiv1$ である。累乗の規則（合同式の計算規則）により $\left(a^{p-1}\right)^m\equiv1^m=1$ である（$m=0$ のときは両辺とも $1$ である）。積の規則により
$$ a^k=a^l\cdot\left(a^{p-1}\right)^m\equiv a^l\cdot1=a^l\pmod p $$
である。
段 3（後半）。$k$ を $p-1$ で割って $k=(p-1)q+r$（$0\le r< p-1$）とすると、$k-r=(p-1)q$ なので $k\equiv r\pmod{p-1}$ であり、前半により $a^k\equiv a^r$ である。$\square$

方針：指数法則で $a\cdot a^{p-2}$ を $a^{p-1}$ にまとめる。
$p\ge2$ なので $p-2\ge0$ であり、$a\cdot a^{p-2}=a^{1+(p-2)}=a^{p-1}$ である。thm-cgflt-fermat により $a^{p-1}\equiv1\pmod p$ なので、$a\cdot a^{p-2}\equiv1\pmod p$ である。$\square$

方針：答は $1$ だけであることを示す。$2$ 以上の整数は素数で割り切れるので、「どの素数 $p$ も、ある項 $a_n$ を割る」ことを示せばよい。$p\ge5$ では $n=p-2$ を選び、Fermat の小定理を使う。
段 1（$1$ は条件を満たす）。$1$ と任意の整数の最大公約数は $1$ なので、$1$ はすべての項と互いに素である。
段 2（何を示せばよいか）。$m\ge2$ とし、$p$ を $m$ の素因数の 1 つとする。ある項 $a_n$ が $p$ で割り切れれば、$p$ は $m$ と $a_n$ の公約数なので、$m$ はその項と互いに素でない。よって「どの素数 $p$ についても、$p$ で割り切れる項がある」ことを示せば、$m\ge2$ はどれも条件を満たさないことが分かる。
段 3（$p=2,3$）。$a_2=4+9+36-1=48=2^4\cdot3$ は $2$ でも $3$ でも割り切れる。
段 4（$p\ge5$ で $6a_{p-2}$ を計算する）。$p\ge5$ なので $p-2\ge3$ であり、$a_{p-2}$ は数列の項である。$2,3,6$ はどれも $p$ で割り切れないので、thm-cgflt-fermat により
$$ 2^{p-1}\equiv1,\qquad 3^{p-1}\equiv1,\qquad 6^{p-1}\equiv1\pmod p $$
である。$6=3\cdot2=2\cdot3$ を使って $6a_{p-2}$ を書き直すと
$$ \begin{aligned} 6a_{p-2}&=6\cdot2^{p-2}+6\cdot3^{p-2}+6\cdot6^{p-2}-6\\ &=3\cdot2^{p-1}+2\cdot3^{p-1}+6^{p-1}-6\\ &\equiv3\cdot1+2\cdot1+1-6=0\pmod p \end{aligned} $$
となる。
段 5（$6$ を約分する）。$p\ge5$ は素数なので $6=2\cdot3$ を割らず、$\gcd(6,p)=1$ である。合同式の割り算と逆元 の約分の条件により、$6a_{p-2}\equiv6\cdot0$ から $a_{p-2}\equiv0\pmod p$ である。つまり $p$ は $a_{p-2}$ を割る。
段 2〜段 5 から、$2$ 以上の整数はどれかの項と互いに素でない。答は $1$ だけである。たとえば $p=5$ では $a_3=250=5\cdot50$、$p=7$ では $a_5=8050=7\cdot1150$ である。$\square$