「フェルマーの小定理」を理解しようとしたら、
二項定理などが必要となっていたので、順に解いていきます。
二項定理
$_nC_r$の組み合わせを使って表すのが一般的な感じもしますが
階乗の形で表してみます。
(x+y)^n = \sum_{r=0}^{n} \frac{n!}{r!(n-r)!} x^{n-r}y^r
証明（二項定理）
帰納法を使って証明します。
$n$の時正しいと仮定します。
\begin{align*}
(x+y)(x+y)^n &= (x+y)\left( \sum_{r=0}^{n} \frac{n!}{r!(n-r)!} x^{n-r}y^r \right) \\
&= \sum_{r=0}^{n} \frac{n!}{r!(n-r)!} x^{n+1-r}y^r + \sum_{r=0}^{n} \frac{n!}{r!(n-r)!} x^{n-r}y^{r+1} \\
&=\left(x^{n+1}+\sum_{r=1}^{n} \frac{n!}{r!(n-r)!} x^{n+1-r}y^r \right)+ \left(\sum_{r=0}^{n-1} \frac{n!}{r!(n-r)!} x^{n-r}y^{r+1} + y^{n+1} \right) \\
& r + 1 = t \\
&=x^{n+1}+\sum_{r=1}^{n} \frac{n!}{r!(n-r)!} x^{n+1-r}y^r + \sum_{t=1}^{n} \frac{n!}{(t-1)!(n-t+1)!} x^{n-t+1}y^r + y^{n+1} \\
&=x^{n+1}+\sum_{r=1}^{n} \left( \frac{n!}{r!(n-r)!} + \frac{n!}{(r-1)!(n+1-r)!} \right) x^{n+1-r}y^r + y^{n+1} \\
&=x^{n+1}+\sum_{r=1}^{n} \left( \frac{(n+1-r)n!}{r!(n+1-r)!} + \frac{r \cdot n!}{r!(n+1-r)!} \right) x^{n+1-r}y^r + y^{n+1} \\
&=x^{n+1}+\sum_{r=1}^{n} \left( \frac{(n+1)!}{r!(n+1-r)!} \right) x^{n+1-r}y^r + y^{n+1} \\
&=\frac{(n+1)!}{0!(n-0+1)!}x^{n+1}+\sum_{r=1}^{n} \left( \frac{(n+1)!}{r!(n+1-r)!} \right) x^{n+1-r}y^r + \frac{(n+1)!}{(n+1)!(n-(n+1)+1)!}y^{n+1} \\
&=\sum_{r=0}^{n+1} \frac{(n+1)!}{r!(n+1-r)!} x^{n+1-r}y^r \\
\end{align*}
これにより、$n+1$でも成り立つ事が示せました。
(x+y)^{n+1}=\sum_{r=0}^{n+1} \frac{(n+1)!}{r!(n+1-r)!} x^{n+1-r}y^r \\
$n=1$の時は成り立ちます。
\begin{align*}
(x+y)^1 &= \sum_{r=0}^{1} \frac{n!}{r!(n-r)!} x^{n-r}y^r \\
x+y &= \frac{1!}{0!(1-0)!} x^{1-0}y^0 +\frac{1!}{1!(1-1)!} x^{1-1}y^1 \\
x+y &= x + y \\
\end{align*}
したがって、二項定理は成り立ちます。
(x+y)^n = \sum_{r=0}^{n} \frac{n!}{r!(n-r)!} x^{n-r}y^r
### 参考
nCrは整数
先ほどは、階乗の形で表した、$_nC_r$が整数である事を求めます。
_nC_r=\frac{n!}{r!(n-r)!}
証明
帰納法を使って証明します。
$n$の時正しいと仮定します。
$n+1$を考えてみます。
\begin{align*}
\frac{n+1!}{r!(n+1-r)!}&=\frac{n+1!}{r!(n+1-r)!} \\
&=\frac{(n+1)n!}{(n+1-r)r!(n-r)!} \\
&=\frac{n+1}{n+1-r}\cdot\frac{n!}{r!(n-r)!} \\
&= \left( 1 + \frac{r}{n+1-r} \right) \frac{n!}{r!(n-r)!} \\
&= \left( 1 + \frac{r}{n+1-r} \right) \frac{n!}{r!(n-r)!} \\
&= \frac{n!}{r!(n-r)!} + \frac{r\cdot n!}{(n+1-r))r!(n-r)!} \\
&= \frac{n!}{r!(n-r)!} + \frac{n!}{(r-1)!(n-(r-1))!} \\
\end{align*}
整数＋整数は整数なので、$r>0$の時$n+1$でも整数となります。
$r=0$の時も整数です。
\begin{align*}
\frac{n!}{0!(n-0)!}=\frac{n!}{n!}=1
\end{align*}
$n=1$の時も整数です。
\begin{align*}
& n = 1 \quad \frac{1!}{r!(1-r)!} \\
& r = 0 \quad \frac{1!}{0!(1-0)!}=\frac{1!}{1!}=1 \\
& r = 1 \quad \frac{1!}{1!(1-1)!}=\frac{1!}{1!}=1 \\
\end{align*}
したがって、$_nC_r$は整数となります。
_nC_r=\frac{n!}{r!(n-r)!} \in \mathbb{Z} \\
### 参考
pCrはpが素数かつ0<r<pであれば、pで割り切れる
$\ p$が素数かつ$0<r<p$であれば、$_pC_r\ $は$p$で割り切れる。
_pC_r\pmod{p}=\frac{p!}{r!(p-r)!} \pmod{p} = 0\\
証明
$\ _pC_r$が整数である事は証明済みです。
\frac{p \cdot (p-1)!}{r!(p-r)!} \\
最初の$\ p$は素数ですが、$0<r<p$であれば分母に$p$未満の数しか存在しない為
$\ p$が分子に残るので、$\ p$の乗算を残した整数となります。
したがって、素数$\ p$で割り切る事が出来ます。
フェルマーの小定理
$\ p$は素数、$a$は$\ p$の倍数でない整数のとき
a^{p-1} \equiv 1\pmod {p}
証明
二項定理より、以下の式が成り立ちます。
\begin{align*}
(a+1)^p &= \sum_{r=0}^{p} \frac{p!}{r!(p-r)!} a^{p-r}1^r \\
&= a^p+\sum_{r=1}^{p-1} \frac{p!}{r!(p-r)!} a^{p-r}1^r + 1^p
\end{align*}
$\ _pC_r$は$\ p$が素数かつ$0<r<p$であれば、$\ p$で割り切れることから
以下の式が成り立ちます。
\begin{align*}
(a+1)^p &\equiv a^p + 1 \pmod{p} \\
\end{align*}
ここで、以下の式が正しい事を、帰納法で証明します。
a^{p} \equiv a\pmod {p}\qquad
$k$の時、上記の式が成り立つとします。
\begin{align*}
k^p &\equiv k &\pmod{p} \\
(k+1)^p &\equiv k^p + 1 &\pmod{p} \\
&\equiv k + 1 &\pmod{p} \\
\end{align*}
$k+1$でも成り立ちます。
$a=1$の時も成り立ちます。
1^p = 1 \pmod{p} \\
したがって、以下の式が成り立ちます。
\begin{align*}
a^{p} &\equiv a &\pmod {p} \\
a^{p-1} &\equiv 1 &\pmod {p}
\end{align*}
### 参考
Quadratic residue
フェルマーの小定理から、素数$p$が奇素数の時以下の式が成り立ちます。
a^{\frac{p-1}{2}} = \pm{1} \pmod{p} \\
証明
フェルマーの小定理から以下の式が成り立ちます。
a^{p-1} \equiv 1\pmod {p}
したがって、以下の式が成り立ちます。
\begin{align*}
& a^{p-1} = 1 & \pmod {p} \\
& a^{p-1} -1 =0 & \pmod {p} \\
& (a^{\frac{p-1}{2}} -1)(a^{\frac{p-1}{2}} +1) =0 & \pmod {p} \\
& a^{\frac{p-1}{2}} =\pm{1} & \pmod {p} \\
\end{align*}
二次剰余（Quadratic residue）
楕円曲線（elliptic curve）で、$x$から$y$を求める場合があります。
またsecp256k1の場合、素数$p$は、$\ p \bmod 4 = 3$を満たすので
以下の式が成り立ちます。
\begin{align*}
& y^2=x^3+7 & \pmod{p}\\
& \pm{y}=(x^3+7)^{\frac{p+1}{4}} & \pmod{p}
\end{align*}
証明
以下の式が成り立ちます。
\begin{align*}
& y^2 = c & \pmod{p}\\
& (y^2)^{\frac{p+1}{4}} = c^{\frac{p+1}{4}} & \pmod{p}\\
& y^{\frac{p+1}{2}} = c^{\frac{p+1}{4}} & \pmod{p}\\
& y^{\frac{p-1}{2} + 1} = c^{\frac{p+1}{4}} & \pmod{p}\\
& y^{\frac{p-1}{2}}\cdot y^1 = c^{\frac{p+1}{4}} & \pmod{p}\\
& \pm{y} = c^{\frac{p+1}{4}} & \pmod{p}\\
\end{align*}
さいごに
内容は、高等学校数学レベルですが再度追いかけてみると案外忘れてる・・・