フェルマーの小定理

「フェルマーの小定理」を理解しようとしたら、
二項定理などが必要となっていたので、順に解いていきます。

[フェルマーの小定理 - Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86)

---

## 二項定理
$_nC_r$の組み合わせを使って表すのが一般的な感じもしますが
[階乗](https://ja.wikipedia.org/wiki/%E9%9A%8E%E4%B9%97)の形で表してみます。

```math
(x+y)^n = \sum_{r=0}^{n} \frac{n!}{r!(n-r)!} x^{n-r}y^r 
```

### 証明（二項定理）

帰納法を使って証明します。
$n$の時正しいと仮定します。

```math
\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$でも成り立つ事が示せました。

```math
(x+y)^{n+1}=\sum_{r=0}^{n+1} \frac{(n+1)!}{r!(n+1-r)!} x^{n+1-r}y^r \\
```

$n=1$の時は成り立ちます。

```math
\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*}
```
したがって、二項定理は成り立ちます。

```math
(x+y)^n = \sum_{r=0}^{n} \frac{n!}{r!(n-r)!} x^{n-r}y^r 
```
###　参考

https://mathtrain.jp/nikouteiri

http://www.mathlion.jp/article/ar104.html

---

## nCrは整数
先ほどは、[階乗](https://ja.wikipedia.org/wiki/%E9%9A%8E%E4%B9%97)の形で表した、$_nC_r$が**整数**である事を求めます。

```math
_nC_r=\frac{n!}{r!(n-r)!}
```

### 証明

帰納法を使って証明します。
$n$の時正しいと仮定します。
$n+1$を考えてみます。

```math
\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$の時も整数です。

```math
\begin{align*}
\frac{n!}{0!(n-0)!}=\frac{n!}{n!}=1
\end{align*}
```

$n=1$の時も整数です。

```math
\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$は整数となります。

```math
_nC_r=\frac{n!}{r!(n-r)!} \in \mathbb{Z} \\
```

###　参考

https://mathtrain.jp/n_production

---

## pCrはpが素数かつ0<r<pであれば、pで割り切れる

$\ p$が素数かつ$0<r<p$であれば、$_pC_r\ $は$p$で割り切れる。

```math
_pC_r\pmod{p}=\frac{p!}{r!(p-r)!} \pmod{p} = 0\\
```

### 証明

$\ _pC_r$が整数である事は証明済みです。

```math
\frac{p \cdot (p-1)!}{r!(p-r)!} \\
```
最初の$\ p$は素数ですが、$0<r<p$であれば分母に$p$未満の数しか存在しない為
$\ p$が分子に残るので、$\ p$の乗算を残した整数となります。
したがって、素数$\ p$で割り切る事が出来ます。

---

## フェルマーの小定理

$\ p$は素数、$a$は$\ p$の倍数でない整数のとき

```math
a^{p-1} \equiv 1\pmod {p}
```

### 証明

二項定理より、以下の式が成り立ちます。

```math
\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$で割り切れることから
以下の式が成り立ちます。

```math
\begin{align*}
(a+1)^p &\equiv a^p + 1 \pmod{p} \\ 
\end{align*}
```
ここで、以下の式が正しい事を、帰納法で証明します。

```math
a^{p} \equiv a\pmod {p}\qquad 
```

$k$の時、上記の式が成り立つとします。

```math
\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$の時も成り立ちます。

```math
1^p = 1 \pmod{p} \\
```

したがって、以下の式が成り立ちます。

```math
\begin{align*}
a^{p} &\equiv a &\pmod {p} \\
a^{p-1} &\equiv 1 &\pmod {p}
\end{align*}
```

###　参考

[フェルマーの小定理 - Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86)

---

## Quadratic residue

フェルマーの小定理から、素数$p$が奇素数の時以下の式が成り立ちます。

```math
a^{\frac{p-1}{2}} = \pm{1} \pmod{p} \\
```
### 証明

フェルマーの小定理から以下の式が成り立ちます。

```math
a^{p-1} \equiv 1\pmod {p}
```
したがって、以下の式が成り立ちます。

```math
\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$を満たすので
以下の式が成り立ちます。

```math
\begin{align*}
& y^2=x^3+7 & \pmod{p}\\
& \pm{y}=(x^3+7)^{\frac{p+1}{4}} & \pmod{p}
\end{align*}
```

### 証明

以下の式が成り立ちます。

```math
\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*}
```
---

## さいごに

内容は、高等学校数学レベルですが再度追いかけてみると案外忘れてる・・・


---