初等整数論

import

import sympy as sym

浮動小数の世界から整数の世界へ

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

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))

約数と倍数

$x$が整数で$n$を正の整数とすると、
$$x=nq+r\ (0\le r\lt n)$$
を満たす$q, r$がただ一つ定まる。
$q$を商、$r$を剰余という。
$r=0$のとき$x$は$n$で割り切れ、
$x$は$n$の倍数、$n$は$x$の約数であるという。

sym.divisors(138) # 約数のリストを返す

[1,2,3,6,23,46,69,138]

sym.divisor_count(138) # 約数の個数を返す

$8$

最小公倍数、最大公約数

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

print(sym.lcm(96, 156))
print(sym.gcd(96, 156))

$1248$
$12$

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

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

sym.totient(84783)

$55448$

素数

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

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

n番目の素数を求める

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

sym.prime(1) # インデックスは1から

$2$
篩いは重いので100000より上は試さないようにしよう。

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

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＃$を素数階乗という。

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}$の形に一意に分解される。

sym.factorint(94235474582021029) # 素数とべきのリストが返ってくる。

{26083:1,3612907816663:1}

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

[2,3,11,37]

素数のべき乗かどうか

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

$6$

素数にまつわる数

メルセンヌ数

$$M_n=2^n-1$$

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

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$の形であるとき。

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が素数になる。$

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で割り切れる最小の数を求めよ。

from sympy.ntheory.modular import crt, solve_congruence
crt([3, 5, 11, 17], [1, 4, 6, 0])

$(2074, 2805)$ # 2074+2805k が題意を満たす。

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)と書く。$$

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の原始根でない。$

print(sym.is_primitive_root(3, 7))
print(sym.is_primitive_root(4, 7))

True
False

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

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となる。$

sym.legendre_symbol(3, 7) # ルジャンドルの記号

$-1$

sym.quadratic_residues(7) # 7の平方剰余のリストを生成

[0, 1, 2, 4]

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

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進数分解

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

sym.ntheory.factor_.digits(126 * 127**8 + 16 * 127**2 + 7 * 127 + 95, 127)

[127,126,0,0,0,0,0,16,7,95]

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