Pythonで数学の勉強：初等整数論

# 初等整数論
### import

```py3
import sympy as sym
```

## 浮動小数の世界から整数の世界へ
整数のつもりで計算していたらいつの間にか浮動小数になっていた。
ありがちなバグである。
割り算、剰余算、天井と床を意識しよう。

```py3
print(20 // 8)
print(20 % 8)
print(sym.ceiling(1.4))
print(sym.floor(1.4))
print(sym.ceiling(-1.4))
print(sym.floor(-1.4))
```
```text
2
4
2
1
-1
-2
```
## 約数と倍数
$x$が**整数**で$n$を**正の整数**とすると、
$$x=nq+r\ (0\le r\lt n)$$
を満たす$q, r$がただ一つ定まる。
$q$を**商**、$r$を**剰余**という。
$r=0$のとき$x$は$n$で割り切れ、
$x$は$n$の**倍数**、$n$は$x$の**約数**であるという。

```py3
sym.divisors(138) # 約数のリストを返す
```
[1,2,3,6,23,46,69,138]

```py3
sym.divisor_count(138) # 約数の個数を返す
```
$8$

## 最小公倍数、最大公約数
**整数**$m, n$に対して$m$の倍数かつ$n$の倍数であるもののうち最小のものを最小公倍数といいLCM$(m, n)$と書く。
$m$の約数かつ$n$の約数であるもののうち最大のものを最大公約数といいGCM$(m, n)$と書く。
最大公約数を求めるアルゴリズムはユークリッドの互除法がある。
最小公倍数は最大公約数から簡単に求まる。

```py3
print(sym.lcm(96, 156))
print(sym.gcd(96, 156))
```
$1248$
$12$

* GCM$(m, n)=1$のとき、$m$と$n$は**互いに素**であるという。

オイラーの$\varphi$関数
n-1以下で互いに素なものの個数を$\varphi(n)$とする。

```py3
sym.totient(84783)
```
$55448$

## 素数

**※暗号理論の実務に使うような素数はここで挙げた関数で作ってはいけない。**

**整数p**に対して約数が**$1とp$**のみになるものを**素数**という。
素数でない整数を**合成数**という。
**1は素数にも合成数にも含まれない。**
素数はその定義から自分より小さい全ての数と互いに素になる。

#### n番目の素数を求める
内部的にはsym.sieve.expand()が呼ばれエラトステネスの篩いでリストを作っているようだ。

```py3
sym.prime(1) # インデックスは1から
```
$2$
篩いは重いので100000より上は試さないようにしよう。

#### x以上y以下の素数リスト

```py3
print([i for i in sym.primerange(100, 200)])
```
[101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]

#### 素数階乗

$n$番目の素数を$p_n$としたとき$\prod p_n=p_n＃$を**素数階乗**という。

```py3
sym.primorial(3) # 2*3*5
```
$30$

* $p_n＃+1$は自身が素数となるか$p_n+1$以上の素因数をもつ。

### 素因数分解の一意性

* 任意の自然数$n$は$n={p_1}^{e_1}{p_2}^{e_2}{p_3}^{e_3}\dots{p_k}^{e_k}$の形に一意に分解される。

```py3
sym.factorint(94235474582021029) # 素数とべきのリストが返ってくる。
```
{26083:1,3612907816663:1}

```py3
sym.primefactors(2**4 * 3**5 * 11**2 *37) # 素因数のリストが返ってくる。
```
[2,3,11,37]


### 素数のべき乗かどうか

```py3
sym.multiplicity(2, 64) # 2^nの形のときのみ0でない数が返ってくる。
```
$6$

## 素数にまつわる数
### メルセンヌ数
$$M_n=2^n-1$$

* $M_n$が素数ならば$n$は素数である。
* $M_n$が素数ならば$2^{p-1}(2^p-1)$は完全数(自身を除く約数の和が自身と等しい)となる。
* 偶数の完全数はこの形に限るが、奇数の完全数が存在しないことは証明されていない。
* メルセンヌ素数が見つかった素数の中では最大である理由はリュカ–レーマー・テストという効率的なアルゴリズムが存在するからである。

```py3
def Mn(n):
    return 2**n - 1
Mn(127)
```
$170141183460469231731687303715884105727$

### フェルマー数
$$F_n=2^{2^n}+1 $$

* $F_5$以降にフェルマー素数があるかどうかはわかっていない。
* 正$n$角形がコンパスと定規で作図可能な必要十分条件は$n=2^k$か異なるフェルマー数を使って$n=F_{n1}F_{n2}\dots2^k$の形であるとき。

```py3
def Fn(n):
    return 2**(2**n) + 1
sym.factorint(Fn(6))
```
{274177:1,67280421310721:1}

### レピュユニット
$$R_n=111\dots111 \ \ (1がn個並ぶ)$$

* $n=2, 19, 23, 317, 1031, \dots のときR_nが素数になる。$

```py3
def Rn(n):
    if n==1:
        return 1
    return Rn(n-1)*10+1
Rn(23)
```
11111111111111111111111

# 合同式
$m, nに対してpで割った余りが等しい時、mとnはpを法として合同という。$
$$m\equiv n\mod p$$

## 中国人剰余定理

$$
m_1, m_2, \dots, m_kがどの2つも互いに素のとき\\\\
\\begin{cases}
x &=& a_1 & \mod m_1\\\\
x &=& a_2 & \mod m_2\\\\
  & & \dots & \\\\
x &=& a_k & \mod m_k
\\end{cases}\\\\
を満たすxがm_1m_2\dots m_kを法として一意に定まる。
$$

**(問)** 3で割ると1余る、5で割ると4余る、11で割ると6余る、17で割り切れる最小の数を求めよ。

```py3
from sympy.ntheory.modular import crt, solve_congruence
crt([3, 5, 11, 17], [1, 4, 6, 0])
```
$(2074, 2805)$ # 2074+2805k が題意を満たす。

```py3
print(2074%3)
print(2074%5)
print(2074%11)
print(2074%17)
```
$1$
$4$
$6$
$0$

## フェルマーの小定理
$$xが素数pの倍数でないならば、\\\\x^{p-1}\equiv 1 \mod p$$
フェルマーの小定理はオイラーの$\varphi(a)$関数を用いて一般化される。
## オイラーの定理
$$xとaが互いに素ならば、\\\\x^{\varphi(a)}\equiv 1 \mod a$$

## 剰余環
整数全体$\mathcal{Z}$をmod $n$で合同なもの同士を1つにまとめて$n$個の集合に分割する。

* $\mathcal{Z}/n\mathcal{Z}は環をなす。$
* pが素数のとき、かつそのときに限って$\mathcal{Z}/p\mathcal{Z}は体となる。$

例えば$n=6$なら2と3が零因子になってしまう。

## 素体

$pによる剰余環を素体と呼び、\mathcal{F}_pと書く。$
暗号理論ではしばしば巨大な素体が用いられる。

# 位数と原始根
## 位数(order)
整数$n$と互いに素な数$a$に対して、
$a^e\equiv 1 \mod n$を満たす最小の正整数$e$を
法$n$に関する$a$の**位数**という。
オイラーの定理より$e$は必ず存在して
$$e={\rm ord}_n(a)と書く。$$

```py3
sym.n_order(64, 97) # ord_97(64)
```
$8$

* $nとaは互いに素とする。a^x\equiv 1 \ \ (\rm mod \  n)ならば{\rm ord}{\scriptsize n}(a)はxの約数である。$
* 位数$e={\rm ord}{\scriptsize n}(a), f={\rm ord}{\scriptsize n}(a)が互いに素のとき、{\rm ord}{\scriptsize n}(ab)=ef$

## 原始根

法$n$と素である整数$a$は
$${\rm ord}{\scriptsize n}(a)=\varphi(n)$$
であるとき$n$に関する**原始根**(primitive root)という。
原始根であることと**生成元**(n乗で全ての元を生成する)であることは同値である。

$3^0=1, 3^1=3, 3^2=2, 3^3=6, 3^4=4, 3^5=5, 3^6=1 \ \ {\rm mod} 7$
$4^0=1, 4^1=4, 4^2=2, 4^3=1 \ \ {\rm mod} 7$
$3は7の原始根だが4は7の原始根でない。$

```py3
print(sym.is_primitive_root(3, 7))
print(sym.is_primitive_root(4, 7))
```
True
False

* 原始根が存在しないことがある。(8の原始根は存在しない)
* $p$が素数ならば$p$に対する原始根が存在する。
* 原始根が存在するのは2,4,奇素数pのべき、奇素数pのべきの2倍のときのみである。

```py3
sym.primitive_root(97) # 97に対する原始根を求める
```
$5$

$p$を奇素数とする。

* $p$の原始根の個数は$\varphi(p-1)$である。
* $a$が$p$に関する原始根ならば$a$または$a+p$は法$p^2$に対する原始根である。
* $a$が$p^2$に関する原始根ならば$a$は法$p^e(e\ge2)$に対する原始根である。

# 平方剰余
$aとpを互いに素とする。$
$$x^2\equiv a \ \ {\rm mod}\ p$$
が解を持つとき**平方剰余**であるといい、そうでないとき**平方非剰余**であるという。
$1^2=1, 2^2=4, 3^2=2, 4^2=2, 5^2=4, 6^2=1 \ \ {\rm mod}\ 7$
$1, 2, 4は7の平方剰余で3, 5, 6は平方非剰余。$
ルジャンドルの記号を使うと$(\frac{1}{7})=1, (\frac{3}{7})=-1となる。$

```py3
sym.legendre_symbol(3, 7) # ルジャンドルの記号
```
$-1$

```py3
sym.quadratic_residues(7) # 7の平方剰余のリストを生成
```
[0, 1, 2, 4]

平方剰余であれば、それはすなわち平方根が存在するということ。

```py3
sym.sqrt_mod(2, 7) # 平方根を求める
```
$3$

$3^2\equiv2 \ {\rm mod}\ 7$

$$p, qを異なる奇素数とするとき、\\\\
(\frac{p}{q})(\frac{q}{p})=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\\\\
(\frac{-1}{p})=(-1)^{\frac{p-1}{2}}\\\\
(\frac{2}{p})=(-1)^{\frac{p^2-1}{8}}$$

## 離散対数

$$a^x\equiv b \ \ {\rm mod}\ p$$

$a^xからbを求めることは容易だが、a, bからxを求めることは困難である。$
$\log{a}を求めることに相当して、これを離散対数問題という。$
エルガマル暗号は素体上の離散対数問題を安全性の根拠としており、
楕円曲線暗号は楕円曲線上の離散対数問題を安全性の根拠にしている。

# n進数分解

任意の進数に分解できる。

```py3
sym.ntheory.factor_.digits(126 * 127**8 + 16 * 127**2 + 7 * 127 + 95, 127)
```
[127,126,0,0,0,0,0,16,7,95]