1
初等整数論1. 群論の復習
群の定義：結合法則，単位元の存在，逆元の存在 基本的な例：Q,Z,Z/mZ
群の位数：元の個数
元 g の位数：g が生成する巡回群の位数
ラグランジェの定理：元の位数は群の位数の約数．
Z/mZ の元は，混同がないと考えられる場合は整数で表記する．
2. Z/mZ の乗法群
(Z/mZ)×={n∈Z/mZ; (n, m) = 1} は自然なかけ算に関して可換群になる．
3. 証明： 演算が可換であること，結合法則および単位元の存在は自明．a∈(Z/mZ)× の逆元の存在は，ax≡1 mod m の解の存在と同値であり，「代数系」で解説した１ 次合同式の解の構成を参照．
4. 演習
(1) (Z/12Z)× の要素を列挙し，群表をつくれ．
(2) 42x≡24 mod 51 を解け．
(3) 7x≡2 mod 11 を解け．
(4) (Z/60Z)× における，7 の逆元を求めよ．
5. オイラー関数
自然数 m∈N に対して
ϕ(m) = #{n∈Z; 1≤n≤m, (n, m) = 1} で定まる関数をオイラー関数という．
6. 演習
(1) n≤100 に対して ϕ(n)を計算せよ．
(2) p, q を互いに異なる素数とするとき ϕ(pq) = (p−1)(q−1)であることを示せ．
(3) pを素数とするとき ϕ(p2) を求めよ．
7. オイラーの定理
(a, m) = 1 であるとき，
aϕ(m) ≡1 modm
がなりたつ．とくに m を素数とするとフェルマーの小定理．
8. 証明： (Z/mZ)× の要素を並べた集合を{x1, x2,· · · , xϕ(m)} とする．このとき {ax1, ax2,· · · , axϕ(m)} は，集合として {x1, x2,· · · , xϕ(m)} と一致し，とくに各要 素をすべてかければ
aϕ(m)x1x2· · ·xϕ(m)≡x1x2· · ·xϕ(m) mod m
が成りたつ．さらに (x1x2· · ·xϕ(m), m) = 1 なので，定理の等式がえられる．
9. 多項式の解の個数
定理： pを素数とし，f(x)を整数係数の n次多項式とするとき，f(x)≡0 mod p の解の個数は高々 n 個である．
10. 証明： 次数n に関する帰納法による．まず，n = 1のときは容易．f(x)≡0 mod p が解α を持つとき，f(x)≡(x−α)g(x) mod p であり，さらに pは素数なので，
f の α 以外の解はすべてg(x)≡0 mod p の解．したがって帰納法が働く．
11. 乗法群は巡回群
定理： p を素数とするとき，(Z/pZ)× ≅Z/(p−1)Z
12. 証明：(Z/pZ)× は位数 p−1の可換群である．そこでa∈(Z/pZ)× を位数が最大の 元とし，その位数を m とする．m < p−1 と仮定して矛盾を導く．
1, a, a2,· · · , am−1 は，xm −1≡ 0 mod p の m 個の解であり，この方程式の解は これらで尽きる．したがって b̸=ak (k= 0,1,· · · , m−1)となるZ/pZの元の位数 n(≥2) は，m の約数ではない．このとき a と b は Z/mZ×ZnZ と同型な部分群 を生成する．一方，アーベル群の基本定理により
Z/mZ×Z/nZ ≅ Z/(m, n)Z×Z/ mn (m, n)Z
右辺は，(Z/pZ)× が位数mn/(m, n)> m の元をもつことを示す．これは矛盾．
13. 演習
(1) x2 −1≡0 mod 12 の解をすべて求めよ．
(2) (Z/pZ)×≅Z/(p−1)Z の生成元になる元を，p= 7,11,13の場合に列挙せよ．
(3) (Z/12Z)× ≅Z/2Z×Z/2Z を示せ．
14. 包除の原理
#(A1∪ · · · ∪An) =∑
i#Ai−∑
i<j#(Ai ∩Aj) +· · · 15. 演習
(1) ϕ(120), ϕ(180) を計算せよ．
(2) (a, b) = 1 のとき ϕ(ab) =ϕ(a)ϕ(b) を示せ．
(3) Pn を {1,2,· · · , n} の順列の集合とする．Qn = #{σ ∈ Pn|σ(j) ̸=j} とする とき lim
n→∞
Qn
n! = 1
e であることを示せ．
16. メビウス関数
自然数 n の素因数分解が n=pe11pe22· · ·pekk で与えられるとき，
µ(n) =
1 n= 1のとき
(−1)k e1 =e2 =· · ·=ek = 1のとき
0 その他
で定まる N 上の関数µ をメビウス関数という．
17. 整数論的関数の性質
自然数 n の素因数分解が n=pe11pe22· · ·pekk で与えられるとき，
(1) （オイラー関数の値）
ϕ(n) = n∏
j
(1− 1
pj) =∑
d|n
µ(d)n d (2) （メビウス関数の値の和）n >1であれば
∑
d|n
µ(d) = 0
(3) （メビウス反転公式）f, g を N上で定義された関数とすると，
∑
d|n
f(d) = g(n) ⇔ f(n) =∑
d|n
µ (n
d )
g(d)
(4) （オイラー関数の値の和） ∑
d|n
ϕ(d) = n
18. 証明：(1) ϕ(n)の値は n から n と共通因子をもつ n 以下の自然数の個数を引いた 数．一方，Aj を pj を因子にもつn 以下の自然数の集合とすると
#(Aj1 ∩Aj2 ∩ · · · ∩Ajl) = n pj1pj2· · ·pjl
なので，包除の原理より ϕ(n) =n−∑
i
n
pi +∑
i<j
n
pipj − · · ·+ (−1)k ∑
pj1<pj2<···<pjk
n pj1pj2· · ·pjk
となる．これを因数分解すればよい．
(2) n >1 なので，
∑
d|n
µ(d) =µ(1) +∑
i
µ(pi) +∑
i<j
µ(pipj) +· · ·+µ(p1p2· · ·pk)
= 1−k+ (k
2 )
− · · ·+ (−1)k
= (1−1)k = 0
(3) 左側の g(n) の式を右側のf(n) の式に代入すると，
∑
d|n
µ (n
d )
g(d) =∑
d|n
∑
e|d
µ (n
d )
f(e)
右辺の和の項をf(e)でくくり直す．eは dの約数．したがって nの約数を動き，固 定された e, n の下で d は e|d|n をみたすように動く．このとき n/d は n/e の約数 となるから
=∑
e|n
f(e)
∑
c|ne
µ(c)
一方(2) より，n/e >1のときはかっこの中が0になるので，f(n)µ(1)だけが残り，
f(n)がえられる．逆は演習．
(4) は
ϕ(n) =n−∑
i
n
pi +∑
i<j
n
pipj − · · ·+ (−1)k ∑
pj1<pj2<···<pjk
n pj1pj2· · ·pjk
=∑
d|n
µ(d)n
d =∑
d|n
µ (n
d )
d
ゆえにメビウスの反転公式から結果がえられる．
19. 演習
(1) ∑
d|n
∑
k|d
µ(k)g(d/k) を簡単にせよ．
(2) つぎの性質をみたす関数σ(n) を求めよ．
g(n) =
∑n k=0
f(k) ⇐⇒ f(n) =
∑n k=0
σ(k)g(n−k)
(3)
¯¯¯¯
¯¯¯¯
¯
(1,1) (2,1) · · · (n,1) (2,1) (2,2) · · · (n,2) . . . . (n,1) (n,2) · · · (n, n)
¯¯¯¯
¯¯¯¯
¯
=ϕ(1)ϕ(2)· · ·ϕ(n) を示せ．
(4) ∏
1≤k≤n/2,(n,k)=1
cos2kπ
n を求めよ．
(5) m 種類の異なる色のビーズで長さ n のネックレスを作るとする．回転で移り 合うものは同じと見なし，鏡映により対応するものは区別するとき，その作り 方の個数は ∑
e|n
1 e
∑
d|e
µ(d)me/d あるいは 1 n
∑
d|n
ϕ(d)mn/d で表されること を示せ．とくにこれら2式は同じ数を表す．
(6) 前問の等号の一般化として ∑
d|n
1 d
∑
e|d
µ(e)f(d/e) = 1 n
∑
d|n
ϕ(d)f(n/d) を示せ．
(7) Λ : N→R が ∑
d|nΛ(d) = logn をみたすとき Λ(n) =
{ logp n =pe のとき
0 その他
20. 2次合同式
ax2+bx+c≡0 mod p は解けるか？
21. 演習
(1) x2+x−1≡0 mod p を，p= 2,3,5,7,11のときに解け（解がないことがあ りうる）．
(2) x2+x−2≡0 mod p を解け．
22. 解の導き方
複素数体上では，係数で割る（係数のかけ算に関する逆元をかける）という操作を 用いて平方完成させ，解の公式を導いた．m が合成数の場合は，かけ算に関する逆
元がないことがありうる．この問題を避けるため，p を素数とし，さらに平方完成 させるには2 で割る（2の逆元をかける）操作が要るので，p 奇素数と仮定すると，
ax2+bx+c≡a(x2+a−1bx) +c modp
≡a(x+ (2a)−1b)2+ (4ac−b2)(4a)−1 modp
と変形される．この形から，2次合同式の解を求める問題は，
x2 ≡a mod p という形の方程式の解を求める問題に帰着される．
23. 平方剰余とルジャンドル記号
pを奇素数とする．x2 ≡a modp が解をもつとき，aは pの平方剰余，そうでな いときは平方非剰余という．
a̸≡0 mod p であるとき，a が平方剰余であるか非剰余であるかにしたがって
(a p
)
= +1 または −1 とし，これをルジャンドル記号と言う．
24. 平方剰余と非剰余は同数
(Z/pZ)× ≅Z/(p−1)Z={1, g, g2,· · · , gp−2} の偶数ベキの元は平方剰余である．他 が非剰余であることは容易に確かめられる．
25. 平方剰余の実態
x2 ≡(p−x)2 mod p なので，平方剰余は 1,2,· · · ,(p−1)/2の平方で与えられる．
26. ルジャンドル記号は準同型 定理： p を素数とするとき，
(ab p
)
= (a
p ) (b
p )
がなりたつ．とくに ( p
)
: (Z/pZ)×→ {±1} は群の準同型である．
27. 証明： 明らかだろう．
28. 演習
(1) 20 以下の素数 p に対し，Ker (
p
)
の要素を小さい順に列挙せよ
(2) 2 が平方剰余と成る 50以下の素数 pを列挙せよ．
29. オイラーの基準： ( a p
)
≡ap−21 mod p
30. 証明： a が平方剰余であれば(Z/pZ)×={1, g, g2,· · · , gp−2} と表したときa =g2k であり，とくにフェルマーの小定理より
ap−12 =gk(p−1) = (gp−1)k≡1 mod p
一方，平方非剰余であれば a = g2k+1 で，また gp−12 は (Z/pZ)× の位数 2 の元な ので，
ap−21 =gk(p−1)gp−21 =gp−21 ≡ −1 mod p 31. 平方剰余の相互法則
定理： p, q を相異なる奇素数とするとき (1) （平方剰余の相互法則）
(p q
) (q p
)
= (−1)p−21q−21 (2) （第一補充法則） (
−1 p
)
= (−1)p−12 (3) （第二補充法則） (
2 p
)
= (−1)p
2−1 8
32. 法則の意味
相互法則は，p, q のうち少なくとも一方が 1 mod 4 であれば，
(p q
)
= (q
p )
そうでないときは ( p q
)
=− (q
p )
となることを意味する．
第一補充法則は，x2 ≡ −1 mod p に解があるための必要十分条件が p≡1 mod 4 であることを意味する．
第二補充法則は，x2 ≡ 2 mod p に解があるための必要十分条件が p≡ ±1 mod 8 であることを意味する．
33. 例
(17 23
)
= (23
17 )
= ( 6
17 )
= ( 2
17 ) ( 3
17 )
= ( 3
17 )
= (17
3 )
= (2
3 )
=−1
34. 演習( 365 1847
)
を求めよ．
35. ガウスの補題
(a, p) = 1 のとき，a,2a,· · · ,p−21a のうち，p で割ったときの剰余が p/2 より大き いものの個数を n とすると， (
a p
)
= (−1)n
36. 証明 剰余は mod p では −(p−1)/2 から (p−1)/2 の範囲に収まることに注意 すると
a·2a· · · · · p−1
2 a≡(−1)n·1·2· · · · ·p−1
2 modp なので
ap−12 ≡(−1)n mod p あとは p >2 で両辺とも ±1に等しいことから分かる．
37. 第一補充法則の証明 これはオイラーの基準から直ちにえられる．
38. 第二補充法則の証明 ガウスの補題で a = 2 とおく．2,4,· · · , p−3, p−1 の中で p/2 より大きいものの個数 n は，1,3,· · · , p−2の中で p/2 より小さいものの個数 と一致している．ここでは n が偶数であるか奇数であるかが分かればよいので，
n ≡1 + 3 +· · ·+ p−1
2 mod 2
≡ 1 2
p−1 2
(p−1 2 + 1
)
mod 2
≡ p2−1
8 mod 2
39. 相互法則の証明 平面上の原点O とA= ((p+ 1)/2,0), B = (0,(q+ 1)/2), C = ((p+ 1)/2,(q+ 1)/2) を頂点とする長方形を考える．ガウスの補題により，
(q p
)
= (−1)n における n は，直線 py =qx の 0≤x≤p/2の部分を y 軸方向に 1/2 平行移動し た平行四辺形の内部に含まれる格子点の個数である．また，
(p q
)
= (−1)m における m は，直線 py =qx の 0≤y≤q/2 の部分を x 軸方向に 1/2 平行移動した平行四 辺形の内部に含まれる格子点の個数である．
一方，長方形OACB からこれらの領域を除いた部分は，右上隅の内部に格子点含 まない正方形と，内部に同数 k 個の格子点を含む合同な三角形二つに分かれる．し たがって，OACB の内部に含まれる格子点の個数はn+m+ 2k であり，それは同 時に明らかに
p−1 2
q−1 2 に等しい．したがって
(p q
) (q p
)
= (−1)m+n= (−1)m+n+2k = (−1)p−21q−21
40. 演習
(1) 素数 p が p≡1 mod 8 または p≡3 mod 8 のときに限り (−2
p )
= 1 であることを示せ．
(2) 素数 p が p≡ ±1 mod 5 のときに限り (5
p )
= 1 であることを示せ．
(3) 素数 p が p≡ ±1 mod 12 のときに限り (3
p )
= 1 であることを示せ．
