第9章初等整数論

第 9 章初等整数論
9.1
9.1.1
オイラーの関数
定義
定義 9.1 n を自然数とする。{ 1, 2, · · · , n } のうち、n と互いに素になる数の個数を φ(n) で表す。この φ をオイ
ラーの関数という。
例 : φ(1) = 1 である。（例終）
例 : φ(12) を求める。1、2、· · · 、12 のうち、12 と互いに素なものは、
1,
5,
7,
11,
なので、φ(12) = 4。（例終）
9.1.2
オイラーの公式
次に φ(n) を具体的に求めるための公式を与える。
定理 9.2 （オイラーの公式）自然数 n の素因数分解を
n=
k
∏
pai i
i=1
とすると、
φ(n) = n
)
k (
∏
1
1−
pi
i=1
定理の使い方と、証明のひとつの方法の考え方を例を使って説明しておく。次節で、剰余類を使った別の証明を紹介する。
例 : φ(12) = 4 だったが、確かに
(
)(
)
1
1
1 2
12 1 −
1−
= 12 × × = 4
2
3
2 3
となっている。どうしてこうなるかをもう少し突っ込んで考えてみる。12 の素因数分解は
12 = 22 × 3
だったが、このときの 12 までの 2、3 の倍数の個数は、
12
=4
3
12
= 6,
2
41
個ある。このうち、重複して引きすぎているものは 2 × 3 の倍数だから
12
=2
2×3
よって、φ(12) は、
φ(12) = 12 −
(
)(
)
12 12
12
1
1
−
+
= 12 1 −
1−
2
3
2×3
2
3
となるので、定理が成立していることがわかる。（例終）
例 : φ(60) は、
)(
)(
)
(
1
1
1
1−
1−
=8
60 1 −
2
3
5
である。もう一度、前の例と同じように確認してみると、1、· · · 、60 のうち、60 と互いに素でないものは、2、3、5 の
倍数のいずれかで、それらの個数はそれぞれ、
60
,
2
60
,
3
60
5
である。これらを 60 から引き、それぞれの公倍数の個数
60
,
2×3
60
,
2×5
60
3×5
を足すと、それらは、2、3、5 の３つの数の公倍数の個数
60
2×3×5
だけ足しすぎているので、それを引く。すなわち、
60 60 60
60
60
60
60
−
−
+
+
,+
−
=
2
3
5
2×3 2×5 3×5 2×3×5
(
)
1 1 1
1
1
1
1
= 60 1 − − − +
+
+
−
=
2 3 5 2×3 2×5 3×5 2×3×5
(
)(
)(
)
1
1
1
= 60 1 −
1−
1−
2
3
5
60 −
となっている。（例終）
問題 : オイラーの公式を用いて、φ(30)、φ(42) を求めよ。
9.1.3
オイラーの公式の証明 (1)
有限集合 X とその部分集合 A1 、· · · 、Ar に対し、I = {i1 , · · · , is } ⊆ {1, · · · , r} とし、
{
Ai1 ∩ Ai2 ∩ · · · ∩ Ais (I ̸= ϕ)
def.
AI :=
X
(I = ϕ)
とすると1
∑
|X\(A1 ∪ A2 ∪ · · · Ar )| =
(−1)|I| |AI |
I⊆{1,··· ,r}
がなりたつ。X = {1, · · · , n}、Ai := (pi の倍数の集合) とすると、
φ(n) = n +
∑
|I| ∏
(−1)
i∈I
I⊆{1,··· ,n}
がいえる。（証明終）
1ϕ
n
は空集合。オイラーの関数の φ とは別。
42
pi
=n
k (
∏
i=1
1
1−
pi
)
9.2
9.2.1
オイラーの定理
オイラーの定理
定理 9.3 （オイラーの定理）自然数 n、整数 a に対して、
(a, n) = 1
aφ(n) ≡ 1
=⇒
(mod n)
がいえる。ただし、φ(n) はオイラーの関数
例 : オイラーの公式より、
(
1
φ(6) = 6 1 −
2
)(
1
1−
3
)
=2
であるから、6 と互いに素な a に関し、a2 ≡ 1 (mod 6) が成立するはずである。いくつかの数で調べてみると、確かに
52 = 25 ≡ 1
72 = 49 ≡ 1 (mod 6)
(mod 6)
112 = 121 ≡ 1
132 = 169 ≡ 1
(mod 6)
(mod 6)
となっている。（例終）
9.2.2
フェルマーの小定理
オイラーの定理の特殊な場合を用いると、素数 p を法とする場合に関して次が成り立つ。
定理 9.4 （フェルマーの小定理）p を素数、a を整数とするとき、
ap ≡ a
(mod p).
(9.1)
が成り立つ
（証明） p が素数だから、a が p の倍数でないならば、gcd (a, p) = 1 である。このとき、オイラーの定理より、
ap−1 ≡ 1 (mod p)
(9.2)
a が p の倍数のときは、
ap ≡ 0, (mod p),
a ≡ 0, (mod p),
だから、ap ≡ a (mod n) がいえる。（証明終）
9.2.3
応用 (1) - 余りを求める。
オイラーの定理を用いると、大きい数を割ったときの余りが楽に求まる場合がある。
例 : 7100 を 12 で割り算したときのあまりを求める。gcd (7, 12) = 1 であるから、オイラーの定理が使える。φ(12) = 4
であるから、
74 ≡ 1 (mod 12)
43
となるので、
7100 = (74 )25 ≡ 1
(mod 12)
となり、余りは 1 となる。（例終）
問題 : (1) 17200 を 24 で割った余りを求めよ。
(2) 231000 を 60 で割った余りを求めよ。
応用 (2) - １次合同式
9.2.4
オイラーの定理を用いると、特殊な場合の一次合同式の解の公式が得られる。
系 9.5 自然数 n、整数 a、b に対し、gcd (a, n) = 1 ならば、一次合同式
ax ≡ b
(mod n)
(9.3)
は n を法としてただ一つの解を持ち、それは、
x = aφ(n)−1 b
で与えられる。
（証明）まず、gcd (a, n) = 1 なので、命題 6.7 により、 (9.3) は n を法としてただ一つの解を持つ。一方、x = aφ(n)−1 b
を (9.3) の左辺に代入すると、オイラーの定理より、
ax = a · aφ(n)−1 b = aφ(n) b ≡ b
(mod b)
となり、(9.3) を満たす。よって、これが (9.3) のただ一つの解。（証明終）
例 : １次合同式
13x ≡ 1 (mod 8)
について考える。gcd (13, 8) = 1 なので、解の公式が使える。オイラーの公式より、
(
)
1
φ(8) = 8 1 −
=4
2
だから、
x = 134−1 1 = 133 ≡ 53 = (25) · 5 ≡ 1 · 5 = 5
(mod 8)
となる。（例終）
問題 : 次の一次不等式を解け。
(1) 5x ≡ 3 (mod 26)
9.3
9.3.1
(2)
7x ≡ 2 (mod 18)
(3)
11x ≡ 7 (mod 24)
オイラーの公式、オイラーの定理の証明
既約剰余類
定理 9.6 自然数 n、整数 a に対して、n を法とする剰余類 C(a) について、次の (i)、(ii) は同値。
(i) C(a) の中に n と互いに素となる整数 b が存在する。
(ii) C(a) に属する任意の整数 c は n と互いに素。
44
（証明） (i) ⇐ (ii) : 明らか。
(i) ⇒ (ii) : gcd (b, n) = 1 となる b ∈ C(a) があるとき、任意の c ∈ C(a) が gcd (c, n) = 1 を満たすことをいう。命題
7.4 より、
b = a + hn,
c = a + kn
(h, k : 整数)
と表せるが、命題 4.2 より、
gcd (c, n) = gcd (a + kn, n) = gcd (a, n) = gcd (a + hn, n) = gcd (b, n)
一方、仮定 (i) より gcd (b, n) = 1 なので、以上を合わせると gcd (c, n) = 1。（証明終）
定義 9.7 (i) 命題 9.6 の同値な命題を満たす剰余類 C(a) を n を法とする規約剰余類という。
(ii) 各既約剰余類の中からもれなく一つずつ取り出した代表元からなる集合を n を法とする既約剰余系という。
例 : 12 を法としたときの既約剰余類は全部で C(1)、C(5)、C(7)、C(11) の４つ。既約剰余系のひとつとして {1, 5, 7, 11}
がとれる。（例終）
注 : 既約剰余系の取り方は一通りとは限らない。例えば、12 を法とした既約剰余系として、{13, 5, 7, 11} や、{1, 5, −5, −1}
などもとることができる。
命題 9.8 自然数 n に対し、
(i) n を法とする規約剰余類は φ(n) 個。
(ii) n を法とする既約剰余系は φ(n) 個の整数からなる。
（証明） (i) n を法とする剰余類 C(a) に対し、命題 7.1 (1) より a は C(a) に属しているので、命題 9.6 から C(a) は
規約剰余類 ⇔ gcd(a, n) = 1。したがって、n を法とする剰余類
{C(1), C(2), · · · , C(n − 1), C(n) = C(0)}
のうち、規約剰余類の個数は {1, 2, · · · , n} の中の、n と互いに素となる数の個数、すなわち φ(n) 個となる。
(ii) (i) より明らか。（証明終）
9.3.2
オイラーの公式の証明 (2)
命題 9.9 p が素数のとき、自然数 e に対し、φ(p) = p − 1、φ(pe ) = pe − pe−1 。
（証明） p は素数であるから、p 未満のすべての数と互いに素になる。よって、φ(p) = p − 1。次に、{1, 2, · · · , pe } の
うち、pe と互いに素でない数は、p の倍数の個数、すなわち pe−1 個。よって、φ(n) = pe − pe−1 。（証明終）
オイラー関数の重要な性質として、次に注意する。
定理 9.10 自然数 a、b に対し、gcd(a, b) = 1
=⇒
φ(ab) = φ(a)φ(b) がなりたつ。
注 : 上の定理のような性質がなりたつことを乗法的という。
45
（証明） a を法とする既約剰余系を
{a1 , · · · , am },
b を法とする既約剰余系を
{b1 , · · · , bn }
とすると、m = φ(a)、n = φ(b) である。以後、φ(ab) = mn であることを示す。そのために、ab の mn 個の既約剰余
系を定める。mn 個の連立一次合同式
{
x ≡ ai
x ≡ bj
(mod a)
(mod b)
は、定理 8.1 （中国式剰余定理）を用いると、ab を法としてただひとつの解 x = cij を持つ。このとき、{cij } が既約剰
余系をなすことを示す。そのためには、
(1) cij （i = 1, · · · , m、j = 1, · · · , n）が ab を法として互いに合同ではないこと
(2) cij が ab を法とする既約剰余系の一部をなすこと
(3) cij が ab を法とする既約剰余系を尽くすこと
を示せばよい。
(1) : もし、cij ≡ ckl (mod ab) ならば、
ai ≡ cij ≡ ckl ≡ ak
bj ≡ cij ≡ ckl ≡ bl
(mod a),
(mod b)
となり、i = k 、j = l がいえることになり、
cij ≡ ckl
(mod ab)
=⇒
cij = ckl
となってしまう。
(2) : cij ≡ ai (mod a) より、cij は a を法とする既約剰余類 C(ai ) に含まれるので、命題 9.6 より、cij と a は互いに
素。同様に cij と b も互いに素。これと系 3.5 より cij と ab は互いに素になる。つまり、各 cij は ab を法とする既約
剰余類の代表元となる。cij たちは、同じ剰余類には属さないので、これらは ab を法とするある既約剰余系となる。
(3) : ab と互いに素である整数 c は、必ずある cij と ab を法として合同であることをいえばよい。もし、c が ab と互い
に素であるとすると、a、b のそれぞれと互いに素である。ゆえに、C(c) は、a を法とする既約剰余類のひとつなので、
c ≡ ai
(mod a)
c ≡ bj
(mod b)
となる i がただひとつ存在する。全く同様に、
となる j がただひとつ存在する。したがって、c は、連立合同式
{
x ≡ ai (mod a)
x ≡ bj
(mod b)
の解である。一方、この合同式の解は ab を法として x = cij のみだったので、cij ≡ c (mod ab) となる。（証明終）
命題 9.9 と定理 9.10 より、オイラーの公式は直ちに求まる。
オイラーの公式（定理 9.2）の証明 : 命題 9.9 と定理 9.10 より、
)} ∏
)
)
(
k
k
k (
k
k (
k {
∏
∏
∏
∏
∏
1
1
1
ei−1
ei
ei
ei
ei
φ(n) =
φ(pi ) =
=
pi ×
=n
1−
(pi − pi ) =
1−
pi 1 −
pi
pi
pi
i=1
i=1
i=1
i=1
がいえる。（証明終）
46
i=1
i=1
9.3.3
オイラーの定理の証明
オイラーの定理（定理 9.3）の証明 : n を法とする規約剰余類を一つとり、
{x1 , · · · , xm }
とする。φ(n) = m である。このとき、
{ax1 , · · · , axm }
も規約剰余類になることを示す。これには、
(1) gcd (axi , n) = 1 が全ての i について成立すること。
(2) axi たちが、n を法として互いに素であること。
をいえばよい。
(1) : 各 xi について (xi , n) = 1 であり、仮定より、gcd (a, n) = 1 なので、系 3.5 より、a、xi の積も n と互いに素。
(2) : もし、axi ≡ axj (mod n) が i ̸= j について成り立つとすると、gcd (a, n) = 1 なので、この両辺を a で割ること
ができるから xi ≡ xj (mod n) となってしまい、矛盾することから言える。
以上より、剰余系 {ax1 , · · · , axm } は、それぞれ、{x1 , · · · , xm } のいずれかひとつずつと合同なので、それらの積は n
を法として合同となる。よって、
am x1 · · · xm ≡ x1 · · · xm
(mod n)
がいえる。各 xi に対し gcd (xi , n) = 1 だったから、それらはこの合同式で割ってゆくことができて、
am ≡ 1
(mod n)
が成立する。（証明終）
47

Download Report