29第8章
8.1

既約剰余類群とオイラー関数

既約剰余類群m を 2 以上の整数とし，α を法 m に関する剰余類，すなわち α ∈ Z/mZ とする． いま，a ∈ α とすると α = a + mZ である． a が法 m に関して可逆ならば，α に属するすべての整数は法 m に関して可逆となる． さらに，整数 b が m を法とする a の逆元ならば，剰余類 b + mZ に属するすべての整数は法 m に関する a の逆元である． 一方，a が法 m に関する零因子ならば，α に属するすべての整数は法 m に関する零因子である（これらのことを確かめてみよ）． したがって，法 m に関する “可逆”，“逆元”，“零因子” という概念は，どれも法 m に関する剰余類がもっている性質ととらえることができる． 次の定義は，このような考え方によって与えられたものである．
定義 8.1 m を 2 以上の整数とし，α ∈ Z/mZ を剰余類とする．整数 a は α = a+mZをみたすとする．
(1) a が法 m に関して可逆であるとき，α は可逆であるという．
(2) 整数 b が法 m に関する a の逆元であるとき，b の属する剰余類を α の逆元とよぶ．
(3) a が法 m に関する零因子であるとき，α は零因子であるという．
剰余類の逆元は，もし存在するならば一意的である． 実際，β, γ がともに α の逆元であるとすると，αβ = αγ = 1 だから，γ = 1γ = (αβ)γ = (βα)γ = β(αγ) = β1 = β.
そこで，剰余類 α の逆元を α−1 で表す（場合によっては 1/α と書くこともある）． たとえば，7 · 13 = 91 ≡ 1 (mod 15) なので，Z/15Z において 7, 13 はともに可逆であり互い−1−1に逆元，したがって 7 = 13 とか 13 = 7 と書くこともできる．
定義 8.2 m を 2 以上の整数とする． Z/mZ に属する可逆な剰余類全体からなる集×合を，法 m に関する既約剰余類群といい (Z/mZ) で表す;

(Z/mZ)× = { α ∈ Z/mZ | α は可逆 } .
この元を，法 m に関する既約剰余類ということがある．

30
定理 5.9 によって，次のように表わすこともできる．

(Z/mZ)× = { a + mZ | a ∈ Z, gcd(a, m) = 1 }= { a + mZ | a ∈ Z, a は m を法として可逆 }= { a + mZ | a ∈ Z, a は m を法として零因子でない } .
さらに，それぞれの a ∈ Z は 1 ≤ a < m の範囲に限定してもよい（どうしてかな？）．

例 8.3 Z/10Z = 0, 1, 2, · · · , 9 のうち，可逆な剰余類は 1, 3, 7, 9 であり，零因子は0, 2, 4, 5, 6, 8 である（確かめ〜）． とくに，既約剰余類群は (Z/10Z)× = 1, 3, 7, 9 となる． ここで，1, 3, 7, 9 のそれぞれの逆元が何かは……，計算してみ．
×法 m に関する既約剰余類群 (Z/mZ) は，『積について閉じていて，各元の逆元がその×中でとれる』という性質をもっている． これらの性質は (Z/mZ) が乗法に関して “群”であることを示しているのだが，詳しくは「代数 I」をお楽しみに．

8.2

オイラー関数

定義 8.4 自然数 m に対して，0 ≤ a < m である整数 a のうち m と互いに素なものの個数を φ(m) で表す． また，このようにして定まる自然数上の関数 φ をオイラー関数という．
すなわち，φ(m) = |{ a ∈ Z | 0 ≤ a < m, gcd(a, m) = 1 }| .
m ≥ 2 のときは，法 m に関する既約剰余類の個数が φ(m) に他ならない;
φ(m) = (Z/mZ)× .
×
たとえば，m = 10 のとき，(Z/10Z) = 1, 3, 7, 9 だから φ(10) = 4． 小さい m に対するオイラー関数の値は次の表のようになる (1 個間違いがある，どれでしょう？ もぉ，先生のいじわるぅ)．
mφ(m)11213242546276849610411101241312146158161017161861918この表からも見えるように，オイラー関数の値は非常に不規則だが，次節で示す定理 8.6の公式を用いれば，次のような不等式を導くことができる．
命題 8.5 自然数 m ≥ 2 に対して，m≤ φ(m) ≤ m − 1.
1 + log2 m

この命題から，φ(m) → ∞ (m → ∞) が導かれる． 右側の不等式は φ の定義から明らか
だが，左側の証明は少し面倒である（補遺参照）．

31

8.3

オイラー関数の積公式

次の定理によって，どんなに大きな m についても，その素因数分解さえわかればオイラー関数の値 φ(m) を正確に計算できる．
rYe定理 8.6 自然数 m の素因数分解が m =pj j (pj は相異る素数で ej > 0) ならば，
j=1

r r YY1ejej −1.
φ(m) =pj − pj=m1−pj
j=1j=1
たとえば，126225 = 33 · 52 · 11 · 17 だから

φ(126225) = (27 − 9)(25 − 5)(11 − 1)(17 − 1) = 57600と計算される． この定理は，以下の 2 つの補題から導くことがキミならできるはずだ．
補題 8.7 素数のべき pe (e > 0) に対して φ(pe ) = pe − pe−1 ．
証明 φ の定義を見れば，pe と互いに素なもんの個数を数えればええやん． ある整数が peと互いに素っちゅうことは，そいつが p で割り切れないことと同じや． そやから，φ(pe )の値は，0 ≤ a < pe をみたす整数 a 全部の個数 pe から，p の倍数の個数を引けばええんとちゃう？ ほんでもって，p の倍数は a = jp, 0 ≤ j < pe−1 で表される pe−1 個で全部やから，φ(pe ) = pe − pe−1 が答えっちゅうわけや．
□補題 8.8 互いに素な自然数 m, n に対して φ(mn) = φ(m)φ(n)．
証明 まず，m, n は互いに素な整数なので，前章，定理 7.6 より，写像

F : Z/mnZ −→ (Z/mZ) × (Z/nZ) ,a + mnZ 7→ (a + mZ, a + nZ)

は全単射であることに注意しておく． いま，整数 a が mn と互いに素ならば，a は m ともn とも互いに素になることは明らかである． したがって，F を既約剰余類群 (Z/mnZ)×に制限することにより，写像

G : (Z/mnZ)× −→ (Z/mZ)× × (Z/nZ)×が定まる． F が単射なので G も単射であるが，以下において G は全射でもあることを確かめよう． これにより，元の個数を比べて φ(mn) = φ(m)φ(n) となって証明が完了す
××る． そこで，全射性を示すために，ξ ∈ (Z/mZ) × (Z/nZ) を任意にとって，

ξ = (a + mZ, b + nZ),gcd(a, m) = gcd(b, n) = 1のように a, b ∈ Z で表せば，中国の剰余定理 (定理 6.5) より，

x ≡ a (mod m),x≡b(mod n)32をみたす x ∈ Z が存在する（ここんとこ，F が全射であることを使ってもよい）． このとき，gcd(a, m) = gcd(b, n) = 1 から，gcd(x, mn) = 1 が簡単に確かめられる． よって
x + mnZ ∈ (Z/mnZ)× かつ G(x + mnZ) = ξ であり，全射であることが示された． □上の証明もそのアイデアの出所であった定理 7.6 の証明も，一見，同じことをやっているように見える． しかし，上の証明では，２つの集合の間に単射があるときに，その写像の全射性から集合の元の個数が等しいことを導いているのに対し，定理 7.6 の証明では，逆に元の個数が等しいことから全射性を導いている． これらに違いに注目して二つの証明のストーリーを味わえるようになれば，キミも立派な数学科学生というわけだにゃん．

8.4

オイラー関数の和公式

自然数 m とその正の約数 d に対して，0 以上 m 未満の整数で，m との最大公約数がd であるもの全体の集合を A(m, d) で表す;

A(m, d) = { a ∈ Z | 0 ≤ a < m, gcd(a, m) = d } .
とくに，|A(m, 1)| = φ(m)，|A(m, m)| = |{0}| = 1 である． また，0 以上 m 未満の m個の整数は m との最大公約数によって類別されるから，[A(m, d) = {0, 1, 2, . . . , m − 1}d|m

したがってX|A(m, d)| = md|mが成り立っている（m の正の約数 d 全体についての和をとる）．いま，a ∈ A(m, d) に対して a/d は，集合 mm
B = b ∈ Z 0 ≤ b < , gcd b,=1ddに属する． すなわち，写像 A(m, d) → B, a 7→ a/d が定義できるが，この写像が全単射であることを確かめるのは難しくない（実際，B → A(m, d), b 7→ bd が逆写像となっている）． よって |A(m, d)| = |B|． 一方，φ の定義から B の元の個数は φ(m/d) だから，|A(m, d)| = φ(m/d) が導かれる． さらに，d が m の正の約数全体を動くとき m/dも正の約数全体を動くから，上の総和の式と合わせて次の定理を得る．
定理 8.9 自然数 m に対して，

Xφ(d) = m.

d|mたとえば，m = 15 とすると，φ(1) + φ(3) + φ(5) + φ(15) = 1 + 2 + 4 + 8 = 15 となる．