整数論入門 - d'space

---

整数論入門

整数と素数

0 および自然数および自然数を -1 倍して得られる数を整数と呼ぶ。

• Z = { ・・・, -2, -1, 0, 1, 2, ・・・}.

２つの整数 a, b について、b が a をわるとは、

• ある整数 c があって、a = b・c

とかけることをいう。このとき、

• b を a の約数
• a を b の倍数

と呼ぶ。

整数 p が約数として 1 と p しかもたないとき、それを素数と呼ぶ。

整数論の基本定理：

任意の整数 n は

• n = ± p₁^e₁ ・・・p_r^e_r

と素数の積に（並べ替えを除いて）ただ一通りにかける。

２つの整数 a, b の共通の約数（公約数）のうち最大のものを最大公約数と呼び、

• gcd(a, b)

とかく。

２つの整数 a, b について、その最大公約数 gcd(a,b) が 1 に等しいとき、a と b は互いに素であるという。

２つの整数 a, b の共通の正の倍数（公倍数）のうち最小のものを最小公倍数と呼び、

• lcm(a, b)

とかく。

最大公約数と最小公倍数の対は、もとの整数対の「再分配」を与える：

２つの整数 a, b について、

• 　a・b　=　gcd(a,b)・lcm(a,b)

合同式

正の整数 n と２つの整数a, bについて、a が n を法として b に合同であるとは

• n が (a - b) をわる

こと、すなわち、

• ある整数 c があって、a　=　b + c n

とかけることをいう。

a が n を法として b に合同であることを

• 　a ≡ b　 (mod n)

とかく。

合同式の性質１：

• a ≡ a'　(mod n) 、b ≡ b'　(mod n)

ならば

• a + b ≡ a' + b'　(mod n)
• a ・ b ≡ a' ・ b'　(mod n)

合同式の性質２：

gcd(a, n)　=　1 ならば

• a z ≡ a z'　(mod n)

と

• z ≡ z'　(mod n)

は同値（一方が成り立てば他方も成り立つ）である。

例（合同式）：

• 32 ≡ 2　(mod 15)　　　　　　　(1)
• 21 ≡ 6　(mod 15)　　　　　　　(2)

式(1), (2)の辺々を加えて

• 53 ≡ 8　(mod 15).

式(1), (2)の辺々かけると

• 672 ≡ 12　(mod 15).

式(1)の両辺を2でわると

• 16 ≡ 1　(mod 15).

式(2)の両辺を3でわっても

• 7 2　(mod 15).

ユークリッドの互除法

整数 a を整数 b でわった余りを a mod b とかく。

• gcd(a, b)　=　gcd(b, a mod b).

ユークリッドの互除法：

a ≧ b ≧ 0 なる２つの整数 a, b について、整数列 r₀, r₁, ・・・, r_l+1 を

• r₀ 　= 　a
• r₁ 　=　 b
• r₂ 　=　 r₀ mod r₁
• ・・・
• r_i+1 　=　 r_i-1 mod r_i
• ・・・
• r_l 　=　 r_l-2 mod r_l-1
• r_l+1 　=　 r_l-1 mod r_l 　=　 0

とすると、

• r_l 　=　 gcd(a, b)
• l 　≦　 log(b)/log(φ) + 1

が成り立つ。φ = (1+5^1/2)/2 ≒ 1.62 は黄金比。

例（ユークリッドの互除法）：
a = 100,　b = 35 の最大公約数をユークリッドの互除法で求める。

i	0	1	2	3	4
ri	100	35	30	5	0
qi	-	2	1	6	-

ここで、q_i 　=　 r_i-1 ÷ r_i .

0 になる直前は r₃ なので、

• gcd(100,35) 　=　 r₃ 　=　 5.

さらに、「逆数」を計算したければ、拡張ユークリッドの互除法が必要。

拡張ユークリッドの互除法：

a ≧ b ≧ 0 なる２つの整数 a, b について、整数列 r₀, r₁, ・・・, r_l+1と整数列 q₁, ・・・, q_l をユークリッドの互除法と同様に定める。さらに、整数列 s₀, ・・・, s_l+1と整数列 t₀, ・・・, t_l+1を以下のように定める。

• s₀ 　= 　1,　　t₀ 　= 　0
• s₁ 　= 　0,　　t₁ 　= 　1

i = 1, ・・・, l について

• s_i+1 　= 　s_i-1 - s_i q_i
• t_i+1 　= 　t_i-1 - t_i q_i

このとき、

• s_l a + t_l b = gcd(a, b)

となる。

注意
常に s_i a + t_i b = r_i となっている。

例（拡張ユークリッドの互除法）：
a = 100,　b = 35　の最大公約数を拡張ユークリッドの互除法で求める。

i	0	1	2	3	4
ri	100	35	30	5	0
qi	-	2	1	6	-
si	1	0	1	-1	7
ti	0	1	-2	3	20

0 になる直前は r₃ = 5 で、s₃ = -1,　t₃ = 3 なので、

• gcd(100,35) 　=　 5　 = 100 (-1) + 35 3.

例（逆数演算）：
16^-1 mod 25 を求める。
n = 25,　a = 16 に拡張ユークリッドの互除法を用いると

i	0	1	2	3	4	5	6
ri	25	16	9	7	2	1	0
qi	-	1	1	1	3	2	-
si	1	0	1	-1	2	-7	-
ti	0	1	-1	2	-3	11	-

よって、

• gcd(25,16) 　=　 1　 = (-7) 25 + 11 16.

とくに

• 16^-1 mod25 　≡ 　11.

オイラーの定理

正整数 n について、1 以上 (n-1) 以下の整数のうちで n と互いに素なものの個数をφ(n)とかく。φはオイラー関数と呼ばれる。

オイラー関数の性質：

• 素数 p に対し、φ(p^e) = p^e - p^e-1.
• n と m が互いに素ならば、φ(n・m) = φ(n)・φ(m).

オイラー関数は整数を「滅失」する：

オイラーの定理：

正整数 n について、nとは互いに素などんな整数 a についても

• 　a^φ(n) ≡ 1　 (mod n)

が成り立つ。

とくに, 素数を法とするときは

フェルマーの小定理：

素数pで割り切れないどんな整数 a についても

• 　a^p-1 ≡ 1　 (mod p)

が成り立つ。

n = p q が異なる素数p, qの積であるとき、pでもqでも割り切れない、どんな整数aについても

• 　a^(p-1)(q-1) ≡ 1　 (mod n)

となる。

例：
n = 5,　a = 2

• φ(5) = 4.
• 2 は 5 で割り切れない。
• 2⁴ ≡ 1 　(mod 5).

n = 15,　a = 7

• φ(15) = (5-1)・(3-1) = 8.
• 7 は 15 と互いに素。
• 7⁸ ≡ 1 　(mod 15)

素数テスト

ミラー・ラビンテスト：
入力: 3以上の奇数 n

• n - 1 = 2^k m （m: 奇数）となる k, m を求める。
• 1 以上 n-1 以下の整数 a をランダムに選択。
• gcd(n, a) > 1 ならば Reject。
• x ← a^m mod n
• x ≡ 1 (mod n) ならば、Accept。
• for j ∈ [0..(k-1)] :
  • x ≡ -1 (mod n) ならば、Accept。
  • そうでないならば、x ← x² mod n
• Reject.

n が素数のとき

• Pr[ ミラー・ラビンテスト(n) = Accept ] = 1.

n が合成数のとき

• Pr[ ミラー・ラビンテスト(n) = Reject ] ≧ 3/4.

実は、

Primes ∈ P.

上へ

---