整数問題を概説

整数論概説
2014 年度
-1-
3
目次
第 1 章 合同式
5
第 2 章 １次不定方程式
11
第 3 章 ピタゴラス数
17
第 4 章 ２次の不定方程式
25
第 5 章 フェルマーの小定理
33
第 6 章 Pell 方程式
43
第 7 章 オイラー関数・約数の個数・完全数
51
第 8 章 連分数と不定方程式
63
5
第 1 章 合同式
入試問題から
２個の正の整数 a, b を正の整数 d で割ったとき、同じ余りが得られたとする。このとき、a, b
は法 d で合同であるといい、a ≡ b (mod d) と表す．
(1) a ≡ a0 (mod d) , かつ b ≡ b0 (mod d) ならば、a + b ≡ a0 + b0 (mod d) であることを証
明せよ．
(2) 10k ≡ 1 (mod d) (k = 1) なので、A = 348092159 を９で割った余りは、
である．
(3) P 2r ≡ 1 (modP + 1) , P 2r+1 ≡ −1 (modP + 1) であることを利用して、５桁の整数
37 x
y
8 が１１の倍数になるように、x, y を定めよ．
【明治大学】
__
__
整数論では剰余が重要な働きをする。そこで、そのための記法が合同式である。定義は本問にあ
る通りで、その基本的性質と演算は、
1 a ≡ a (modd)【反射律】
2 a ≡ b (modd) ⇒ b ≡ a (modd)【対称律】
3 a ≡ b (modd) , b ≡ c (modd) ⇒ a ≡ c (modd)【推移律】この３つの性質をみたすとき、整数
全体は有限個の互いに素な集合に分割できる。例えば、任意の整数は、
C0 = {m |m ≡ 0 (mod2) } , C1 = {m |m ≡ 1 (mod2) }
のいずれかに属し、
C0 ∪ C1 = Z, C0 ∩ C1 = ∅
である。つまり、２で割った剰余は、０か１だから、C0 は剰余が 0，C1 は剰余が 1 の集合で
ある。これらを類とよぶ。この類から代表を１つずつ選んで系を作る。これを剰余系という。
３の剰余系は、{0, 1, 2} であるが、{−1, 0, 1} も剰余系である．
第 1. 合同式
a ≡ a0 (modd) , b ≡ b0 (modd)
4
⇒ a + a0 ≡ b + b0 (modd) , aa0 ≡ bb0 (modd)
5 c, d が互いに素のとき、
ca ≡ cb (modd) ⇒ a ≡ b (modd)
これらから、１次不定方程式を解くことができる。例えば、
3x + 5y = 7 ⇔ 3x ≡ 7 (mod5)
⇔ 2 · 3x ≡ 2 · 7 (mod5) ⇔ x ≡ 14 (mod5)
⇔ x ≡ 4 (mod5)
のように。
解答
(1)
a ≡ a0 (modd) ⇔ a = a0 + q1 d
b ≡ b0 (modd) ⇔ b = b0 + q2 d
のとき、
a + b = a0 + b0 + (q1 + q2 ) d
⇔ a + b ≡ a0 + b0 (modd)
(2)
[
(
)]
10k ≡ 1 (mod9) ∵ 10k − 1 = 9 10k−1 + 10k−2 + · · · + 10 + 1
だから、
348092159
= 3 · 108 + 4 · 107 + 8 · 106 + 9 · 104 + 2 · 103 + 1 · 102 + 5 · 10 + 9
≡ 3 + 4 + 8 + 9 + 2 + 1 + 5 + 9 (mod9)
≡ 5 (mod9)
よって、余りは５である。
(3) 102r ≡ 1 (mod11) , 102r+1 ≡ −1 (mod11) だから、
37xy8 = 3 · 104 + 7 · 103 + x · 102 + y · 10 + 8
≡ 3 · 1 + 7 · (−1) + x · 1 + y · (−1) + 8 (mod11)
≡ x − y − 7 (mod11)
⇔ x − y = 11m + 7
0−95x−y 59−0
−9 5 11m + 7 5 9
-6-
第 1. 合同式
だから、
m = 0, m = −1
∴ x − y = 7, −4
∴ (x, y) = (9, 2) , (8, 1) , (7, 0) ,
(0, 4) , (1, 5) , (2, 6) , (3, 7) , (4, 8) , (5, 9)
入試問題から
an = 19n + (−1)
n−1
24n−3 (n = 1, 2, 3 . . .)
のすべてを割り切る素数を求めよ
【東京工業大学】
解答
a1 = 21 = 3 · 7, a2 = 329 = 7 · 47 だから、求める素数の候補は７。
n−1
an = 19n + 4 (−1)
= 19n + 4 (−16)
24n−4
n−1
とかけるから、
an+2 − (19 − 16) an+1 + 19 · (−16) an = 0
が成り立つ。これより、an , an+1 が７の倍数ならば、an+2 も７の倍数．a1 , a2 も７の倍数だったか
ら、数学的帰納法により、an はつねに７の倍数である。……という証明法が１つ。ここでは、合
同式を使って証明してみよう。
n−1
24n−3
n−1
(mod7)
an = 19n + (−1)
≡ 19n + 2 (−16)
n−1
≡5·5
+ 2 (5)
≡7·5
(mod7)
n−1
n−1
(mod7)
≡ 0 (mod7)
-7-
第 1. 合同式
練習問題
ai ≡ bi (modm) (i = 1, 2, · · · , n)
のとき、
(1)
a1 + a2 + · · · + an ≡ b1 + b2 + · · · + bn (modm)
(2)
a1 × a2 × · · · × an ≡ b1 × b2 × · · · × bn (modm)
を証明せよ。
(1) a1 + a2 + · · · + an ≡ b1 + b2 + · · · + bn (modm) とすると、
a1 + a2 + · · · + an = mQ1 + r
b1 + b2 + · · · + bn = mQ2 + r
an+1 = mq1 + s, bn+1 = mq2 + s
であるから、
a1 + a2 + · · · + an + an+1 = m (Q1 + q1 ) + r + s
b1 + b2 + · · · + bn + bn+1 = m (Q2 + q2) + r + s
よって、
a1 + a2 + · · · + an + an+1 ≡ b1 + b2 + · · · + bn + bn+1 (modm)
ゆえに、数学的帰納法により成立する。
(2)
a1 × a2 × · · · × an ≡ b1 × b2 × · · · × bn (modm)
とすると、
a1 × a2 × · · · × an = mQ1 + r
b1 × b2 × · · · × bn = mQ2 + r
と書ける。
an+1 = mq1 + s, bn+1 = mq2 + s
とおくと、
a1 × a2 × · · · × an × an+1 = mL1 + rs
b1 × b2 × · · · × bn × bn+1 = mL2 + rs
よって、
a1 × a2 × · · · × an × an+1 ≡ b1 × b2 × · · · × bn × bn+1 (modm)
ゆえに、数学的帰納法により成立する。
-8-
第 1. 合同式
練習問題
m1 , m2 が互いに素であって、a ≡ b (modm1 ) , a ≡ b (modm2 ) のとき、
a ≡ b (modm1 m2 )
であることを示せ。
a − b = m1 q1 , a − b = m2 q2
とおけて、
m1 q1 = m2 q2
m1 , m2 が互いに素であるから、q1 = m2 q である。
∴ a − b = m1 m2 q ⇔ a ≡ b (modm1 m2 )
練習問題
111333 + 333111
は７の倍数であることを示せ。
111 ≡ −1 (mod7) , 333 ≡ −3 (mod7)
である。
333
∴ 111333 ≡ (−1)
≡ −1 (mod7)
また、
111
333111 ≡ (−3) (mod7)
( )37
111
37
(−3)
≡ − 33
≡ − (−1) ≡ 1 (mod7)
∴ 111333 + 333111 ≡ −1 + 1 ≡ 0 (mod7)
練習問題
1! + 2! + 3! + · · · + 100!
を 15 で割った余りを求めよ、
n! ≡ 0 (mod15) (n = 5)
であるから、
1! + 2! + 3! + · · · + 100! ≡ 1! + 2! + 3! + 4! (mod15)
≡ 1 + 2 + 6 + 24 ≡ 3 (mod15)
求める余りは 3 である。
-9-
第 1. 合同式
練習問題
52n + 3 · 25n−2
は７の倍数であることを示せ。
( )n−1
52n + 3 · 25n−2 = 25n + 3 · 23 25
n−1
≡ 4n + 3 · 23 (4)
(mod7)
≡ 4n (1 + 3 · 2) (mod7)
≡ 0 (mod7)
練習問題
3n+2 + 42n+1
は１３の倍数であることを示せ。
3n+2 + 42n+1 = 9 · 3n + 4 · 16n
≡ 9 · 3n + 4 · 3n (mod13)
= 13 · 3n ≡ 0 (mod13)
-10-
11
第 2 章 １次不定方程式
入試問題から
(1) 4m + 6n = 7 を満たす整数 m, n は存在しないことを証明せよ．
(2) 3m + 5n = 2 を満たすすべての整数の組 (m, n) を求めよ．
(3) a, b を互いに素な正の整数とする．k を整数とするとき、ak を b で割った余り r(k) で表
\ l ならば r(k) =
\ r(l) であることを示せ．
す．k, l を b − 1 以下の正の整数とするとき、k =
(4) am + bn = 1 を満たす整数 m, n が存在することを示せ．
【2000 大阪女子大学】
__
__
方程式は未知数の個数と方程式の個数が同数でないと解けないが、方程式の個数が不足している
ときは、解は一意的に定まりません。例えば、
x2 + 2xy + 2y 2 = 1
を満たす実数解は無数にあります。y の値を決めるたびに x の２次方程式になって、x が決定する
からです。ところが、解の条件（定義域）を整数と限定すると、解の個数は有限個になることがあ
ります。
（もちろん、無数のときもありますよ）それは、整数が、数直線上で離散的に分布している
からです。それに対して、有理数はどんな近接している有理数の間にも必ず有理数は存在します。
（これを有理数の稠密性（dense）といいます。) この例では、
2
x2 + 2xy + 2y 2 = 1 ⇔ (x + y) + y 2 = 1
で、x + y, y がともに整数だから
{
{
x + y = ±1
x+y =0
,
y=0
y = ±1
⇔ (x, y) = (±1, 0) , (∓1, ±1)
の４組が解になります。このような方程式を不定方程式といいます。本問は、
ax + by = c (a, b, c ∈ Z)
第 2. １次不定方程式
の形をした不定方程式の問題です。この方程式を最初に扱ったギリシャのディオファントス（Dio-
phanntos）にちなんでディオファントス方程式とよびます。
解答
(1) 4m + 6n = 7 が整数解をもたないことをいうには、(m, n) を整数解として、矛盾が生じると
いえばいいのです。つまり、背理法です。このとき、4m + 6n = 2 (2m + 3n) は偶数です。と
ころが、右辺の 7 は奇数。偶数＝奇数。これは矛盾！よって、4m + 6n = 7 は整数解をもた
ない。
それじゃ、3m + 5n = 2 はどうなるだろうか。とりあえず、じっと観察 ∗ すると、１個の解
∗
が見えてきたりする。m = 4, n = −2 がそれさ。もちろん、他にもあるから、これでなきゃ
整数問題では、この
いけないってこともない。すると
観察というのがなかな
か、馬鹿にできない技
術なんだ。
(2) 3m + 5n = 2 ⇔ 3 (m − 4) + 5 (n + 2) = 0 と変形できる。これを、3(m − 4) = −5(n + 4) と
みると、右辺は５の倍数だから、左辺の 3(m − 4) も５の倍数。3,5 には共通の公約数が１し
かない。これを 3,5 は互いに素であるという。だから、
m − 4 = 5k, n + 2 = −3k
⇔ m = 5k + 4, n = −3k − 2 (k ∈ Z)
とかける。つまり、無数の解をもつことになるんだ。さて、ここで、このタイプの方程式が
整数解をもつための条件をもとめようというのが次の（３）（４）だ。
(3)
r (k) =「r (l) ⇔ ak − al = a (k − lは b で割り切れる) 」
とすると、a, b は互いに素で、2 5 b だから、k − l が b で割り切れることになる。
−b + 1 < k − l < b − 1 より、
k−l =0⇔k =l
よって、対偶をとって、
\ l ⇒ r (k) =
\ r (l)
k=
が示せた。
(4) m = 1, 2, 3, . . . , b − 1 に対して、r(1), r(2), r(3), · · · , r(b − 1) はどの２つも異なり、a, b が互
いに素だから、
1 5 r(1), r(2), r(3), · · · , r(b − 1) 5 b − 1
であって、
r(i) = 1, 1 5 i 5 b − 1
となる i が存在する。つまり、
ai = bQ + 1
となる整数 i, Q が存在する。よって、am + bn = 1 となる整数 m, n が存在する。
-12-
第 2. １次不定方程式
, ＜除法の原理＞を証明しておこう。
定理 除法の原理
整数 a, 正の整数 b に対して、
a = bq + r, 0 5 r < b
となる整数 q, r がただ１組存在する。
＜証明＞ b の倍数を数直線上にならべると、
· · · · · · < −3b < −2b < −b < 0 < b < 2b < 3b < · · · · · ·
となる。このとき、任意の整数 a はある区間；
qb 5 x < (q + 1) b
にはいる。したがって、
qb 5 a < (q + 1) b
そこで、r = a − qb とおくと、
a = bq + r, 0 5 r < b
が成立する。
さて、本問の結論は＜定理＞として記憶しておこう。つぎに重要な定理を確認しておこう。
定理 Euclid の互除法
自然数 a を自然数 b で割ったときの商を Q, 余りを r とすると、a, b の最大公約数は、b, r の
最大公約数に一致する。
＜証明＞
a = bq + r
と書ける。a, b の最大公約数を g1 ,b, r の最大公約数を g2 とする。このとき、a は g2 を約数にもつ
から、g2 は a, b の公約数である。
∴ g1 = g2
r = a − bq と書けるから、r は g1 を約数にもつ。g1 は b, r の公約数である。
∴ g2 = g1
以上より g1 = g2 となる。
以下では a, b の最大公約数を (a, b) とか、gcd(a, b) と表すことにする。a を b で割った商を Q1 ,
余りを r1 とすると、
a = bQ1 + r1
(a, b) = (b, r1 )
-13-
第 2. １次不定方程式
b を r1 で割った商を Q2 , 余りを r2 とすると、
b = r1 Q2 + r2
(b, r1 ) = (r1 , r2 )
r1 を r2 で割った商を Q3 , 余りを r3 とすると、
r1 = r2 Q3 + r3
(r1 , r2 ) = (r2 , r1 )
これを繰り返していくと、
(a, b) = · · · = (rn , rn+1 ) = · · ·
r1 > r2 > r3 > · · · · · ·
数列 {rn } は自然数の単調減少列であるから、
rm > rm+1 = 0
となる m がある。(rm , 0) = rm であるから、
(a, b) = rm
である。a, b が互いに素であるときは、rm = 1 となる。
6105 = 2886 × 2 + 333
2886 = 333 × 8 + 222
333 = 222 × 1 + 111
222 = 111 × 2 + 0
であるから、6105,2886 の最大公約数は 111 である。
この互除法を用いると不定方程式 ax + by = 1 の特殊解が得られる。例えば、37x + 127y = 1 を
解いてみよう。
127 = 37 × 3 + 16
37 = 16 × 2 + 5
16 = 5 × 3 + 1
これより、(127, 37) = (5, 1) となり、127 と 37 は互いに素である。
1 = 16 − 5 × 3
= 16 − (37 − 16 × 2) × 3
= 37 × (−3) + 16 × 7
= 37 × (−3) + (127 − 37 × 3) × 7
= 127 × 7 + 37 × (−24)
この一連の計算を逆にたどって、1 を 127 と 37 で表せば、x = −24, y = 7 という解が見つかる。
37x + 127y = 1
37 · (−24) + 127 · 7 = 1
-14-
第 2. １次不定方程式
辺々ひいて、
37 (x + 24) + 127(y − 7) = 0
37,127 は互いに素であるから、
{
x + 24 = 127m
⇔ x = 127m − 24, y = −37m + 7
y − 7 = −37m
これが一般解である。
定理
２つの整数 a, b が互いに素であることと、ax + by = 1 を満たす整数 x, y が存在することは
同値である。
例題 1
任意の正の整数 k に対して、7k + 6 と 6k + 5 は互いに素であることを証明せよ。
＜証明＞
6 (7k + 6) + (−7) (6k + 5) = 1
が成り立つから、7k + 6 と 6k + 5 は互いに素である。
例題 2
21x + 14y + 12z = 1
を満たす整数解を求めよ。
解答
1
21x + 14y = 7w ⇔ 3x + 2y = w · · · とおける。そこで 3x + 2y = 1 を満たす解を１組求めると、
x = 1, y = −1
1 を満たす x, y の１つは x = w, y = −w
であるから、
これより、
3x + 2y = w ⇔ 3 (x − w) = −2 (y + w)
∴ x = w − 2k, y = 3k − w
つぎに、
7w + 12z = 1 ⇔ 7 (w + 5) + 12 (z − 3) = 0
-15-
第 2. １次不定方程式
を解くと、
w + 5 = −12j, z − 3 = 7j
だから、
x = −12j − 2k + 5
y = 3k − 7j − 3
z = 7j + 3
例題 3
3 で割ると 1 余り、5 で割ると 3 余り、7 で割ると 4 余る自然数で最小のものを求めよ。
求める数 N は
N = 3x + 1 = 5y + 3 = 7z + 4
と表せる。まず、
3x + 1 = 5y + 3 ⇔ 3x − 5y = 2
⇔ 3 (x + 1) − 5 (y + 1) = 0
より、
x + 1 = 5k, y + 1 = 3k
このとき、
N = 15k − 2 = 7z + 4
⇔ 15k − 7z = 6
⇔ 15 (k − 6) = 7 (z − 12)
∴ k − 6 = 7j, z − 12 = 15j
となって、
∴ N = 7 (15j + 12) + 4 = 106j + 88
よって、求めるものは、N = 88 である。
-16-
17
第 3 章 ピタゴラス数
入試問題から
x2 + y 2 = z 2 を満たす自然数 x, y, z で、それらの最大公約数が１であるものを既約のピタゴ
ラス数という．
(1) x, y のうち一方だけが偶数であることを示せ．
(2) そこで y を偶数としてよい．このとき、すべての既約のピタゴラス数は
1
x = a2 − b2 , y = 2ab, z = a2 + b2 · · · · · · で与えられることを示せ．ただし、a, b の一方が奇数、他方が偶数で、a > b かつ、a, b
は互いに素であるものとする．
解答
（１）は当然背理法である．まず、
(
)
2
2
(2m) = 4m2 , (2m + 1) = 4 m2 + m + 1
より、任意の整数の平方数は、４で割ると，余りは０または１である．いま、x, y ともに、奇数と
すると、
2
2
x2 + y 2 = (2p + 1) + (2q + 1)
(
)
= 4 p2 + p + q 2 + q + 2 = z 2
z 2 が４で割ると，余りが２となって、矛盾する．よって、x, y の少なくとも１つは偶数であるが、
ともに偶数であることは、既約であることから、あり得ない．よって、x, y のうち一方だけが偶数
である．
1 は確かにピタゴラス数である；
さて、（２）であるが、
(
)2
2
x2 + y 2 = a2 − b2 + (2ab)
(
)2
= a2 + b2 = z 2
1 の x, y, z が既約なピタゴラス数であることはどうしてだろうか．x, z は
であるからだ．では、
ともに奇数である．いま、素数 p が x, z の公約数であると仮定すると、p は奇数である．p は x, z
の公約数だから、p は x + z = 2a2 , z − x = 2b2 の約数になる．よって、p は a, b の公約数になり、
第 3. ピタゴラス数
1 で与えられる x, z は互いに素．これより、x, y
a, b は互いに素であることに矛盾する．よって、
も互いに素．y, z も互いに素であることがわかる．つまり、x, y, z が既約なピタゴラス数である.
1 で与えられることを示す．
逆に既約なピタゴラス数は
上に示したように、x を奇数、y を偶数としてよい．そして、z は奇数であるから、z + x, z − x は
偶数である．そこで、
z + x = 2m, z − x = 2n ⇔ z = m + n, x = m − n (m, n ∈ N )
ここで、m, n の公約数を g とおくと、g は x, z の公約数にもなって、x, z が互いに素であるから、
g = 1. よって、m, n も互いに素である．
( y )2
y 2 = (z + x) (z − x) = 4mn ⇔
= mn
2
これより、mn は平方数であるが、m, n は互いに素であるから、
m = a2 , n = b2
とかける．これより、
x = a2 − b2 , z = a2 + b2
そして、y = 2ab
x が奇数であるから、a, b の一方は奇数、他方は偶数であり、m > n だから、a > b であり、a, b の
\ 1 とすると、g は x, y, z の公約数になってしまうので、a, b は互いに素である．
公約数が g =
,
半径１の単位円 x2 + y 2 = 1 と点 (−1, 0) を通り、傾き t の直線との交点で、(−1, 0) ではないも
のは、
(
1 − t2
2t
,
2
1 + t 1 + t2
)
いま、t を 0 < t < 1 の任意の有理数とすると、この点は第１象限上
にある単位円周上のすべての有理点を表すことになる．
t=
n
(m > n, m, n は互いに素)
m
とおくと、
(
)2 (
)2
1 − t2
2t
+
=1
1 + t2
1 + t2
(
)2
(
)2
2
⇔ 1 − t2 + (2t) = 1 + t2
(
( n )2 )2 ( ( n ))2 (
( n )2 )2
⇔ 1−
= 1+
+ 2
m
m
m
(
)
( 2
)
2
2
2
⇔ m − n2 + (2mn) = m2 + n2
-18-
y=tx
第 3. ピタゴラス数
(
)
よって、 m2 − n2 , 2mn, m2 + n2 はピタゴラス数である．
【演習 1】
a, b, c はどの 2 つも 1 以外の共通な約数をもたない正の整数とする。
a, b, c が，a2 + b2 = c2 を満たしているとき，次の問いに答えよ。
(1) c は奇数であることを示せ。
(2) a, b の 1 つは 3 の倍数であることを示せ。
(3) a, b の 1 つは 4 の倍数であることを示せ。
【2004 旭川医科大学】
1 平方数を４で割った余りは、０か１である。
2 平方数を４で割った余りは、０か１である。
【解答】
(1) 条件より a, b の少なくとも１つは奇数である．
{
2
(2k) = 4k 2
(
)
2
(2k + 1) = 4 k 2 + k + 1
J a, b は互いに素であるから、同時
に偶数とはならない。
であるから、完全平方数を４で割ると，余りは０か１である。
いま、a, b ともに奇数であるとすると、a2 + b2 は４で割ると J 任意の整数 n で、
2
２余る数になり、c2 が４で割ると２余る数となって、矛盾． n ≡ 0, 1( mod 4)
よって、a, b の一方が偶数、他方が奇数である．ゆえに、c は
奇数である．
(2)
{
2
(3k) = 9k 2
(
)
2
(3k ± 1) = 3 3k 2 ± 2k + 1
だから、完全平方数は３で割ると余りは０か１である．
2
2
a, b ともに３の倍数でないとすると、a + b は 3 で割ると
２余る数になり、c2 が 3 で割ると 2 余る数となって、矛盾．
よって、a, b の１つは３の倍数である．ともに３の倍数とは
ならないから、a, b の一方が３の倍数である．
-19-
J 任意の整数 n で、
n2 ≡ 0, 1( mod 3)
第 3. ピタゴラス数
(3)

2

(4k) = 16k 2


(
)
2
(4k ± 1) = 8 2k 2 ± k + 1


(
)

2
(4k + 2) = 8 2k 2 + 2k + 4
a, b ともに４の倍数でないとすると、a2 + b2 は、
8M + 2, 8M + 5, 8M + 8
のいずれかであるが、c2 はこのいずれの形になることもない
から、矛盾．よって、a, b の１つは４の倍数である．
__
__ 議論のポイントは平方剰余である。
【演習 2】
次の条件 (a),(b) をみたす直角三角形を考える．ただし、斜辺の長さを p, その他の２辺の長
さを q, r とする．
(a) p, q, r は自然数で、そのうちの少なくとも２つは素数である．
(b) p + q + r = 132
(1) q, r のどちらかは偶数であることを示せ．
(2) p, q, r の組をすべて求めよ．
【2006 一橋大学】
(1) n を整数とするとき、
J 余りで分類！は整数問題の１つの
技法
( i ) n = 2N ならば、n2 = 4N 2
( ii ) n = 2N + 1 ならば、n2 = 4(N 2 + N ) + 1
であるから、整数の平方が４で割って２余ることはない
· · · · · · (?)
いま、q, r のどちらも奇数とすると
2
2
q 2 + r2 = (2Q + 1) + (2R + 1)
( 2
)
= 4 Q + R2 + Q + R + 2
J 背理法で証明．
J ３平方の定理より、p2 = q 2 + r 2
これは、p が４で割って２余ることになって、(?) に矛盾す
る．よって、q, r のどちらかは偶数である．
(2) q, r の１つは奇数で、もう１つは偶数であるから、q を奇数、
r を偶数としてもよい．p, q, r は自然数で、そのうちの少な
くとも２つは素数であるから、q, r の少なくとも１つは素数
-20-
第 3. ピタゴラス数
である．
J 偶数の素数は 2 だけであり、それ
以外の素数はすべて奇数である
r が素数であるとすると、r = 2 である．
p2 = q 2 + 4
⇔ (p − q) (p + q) = 4
⇔ p − q = 1, p + q = 4
J 整数問題の原則、積形を作れ！
⇔ 2p = 5, 2q = 3
これは不適．従って、p, q が素数である．
p2 = q 2 + r 2
⇔ (p − r) (p + r) = q 2
と変形して、1 5 p − r < p + r であるから、
p + r = q2 , p − r = 1
)
)
1( 2
1( 2
⇔p=
q + 1 ,r =
q −1
2
2
これを、p + q + r = 132 に代入して、
) 1( 2
)
1( 2
q +1 +
q − 1 + q = 132
2
2
⇔ q 2 + q − 132 = 0
J p − r = q, p + r = q なんて分解
はない．
⇔ (q − 11) (q + 12) = 0
q は素数だから、q = 11
r = 1 (112 − 1) = 60, p = 60 + 1 = 61
2
__
__
p2 = q 2 + r2 を満たす整数解をピタゴラス数といい、このような、p, q, r の解は
p = m2 + n2 , q = m2 − n2 , r = 2mn
であることが知られている．
このとき、r が素数ならば、m = n = 1 となって、q = 0 で不適．したがって、p, q が素数である．
q = (m + n)(m − n) が素数だから、m − n = 1 である．m = n + 1 より、
p = (n + 1)2 + n2 , q = (n + 1)2 − n2 , r = 2n(n + 1)
p + q + r = 132、だから
2
2 (n + 1) + 2n(n + 1) = 132
2n2 + 3n − 65 = 0
(n − 5) (2n + 13) = 0
∴ n=5
-21-
第 3. ピタゴラス数
【演習 3】
各辺の長さが整数となる直角三角形がある。
(1) この直角三角形の内接円の半径は整数であることを示せ。
(2) この直角三角形の三辺の長さの和は三辺の長さの積を割り切ることを証明せよ。
【2002 お茶の水女子大学】
【解答】
(1) 直角三角形の３辺の長さを a, b, c とし、a2 + b2 = c2 とする．
内接円の半径を r とすると、
a−r+b−r =c
a+b−c
∴ r=
2
a, b, c がすべて偶数のときは r は整数である．
そうではないとき、a, b, がともに奇数とすると、
{
2
(2k) = 4k 2
(
)
2
(2k + 1) = 4 k 2 + k + 1
だから、a2 + b2 は４で割ると２余る数になるが、完全平方
数 c2 がこのようになることはないから、a, b, の１つが奇数
であり、したがって、c も奇数になるから、r は整数である．
(2)
1
a+b+c
ab =
r
2
2
が成り立つから、
ab
r=
a+b+c
abc
rc =
a+b+c
よって、直角三角形の三辺の長さの和は三辺の長さの積を割
り切る
-22-
第 3. ピタゴラス数
【演習 4】
正の整数 a, b, c, d が等式 a2 + b2 + c2 = d2 を満たすとする。
(1) d が３の倍数でないならば、a, b, c の中に３の倍数がちょうど２つあることを示せ。
(2) d が２の倍数でも３の倍数でもないならば、a, b, c のうち少なくとも１つは６の倍数であ
ることを示せ．
【一橋大学】
【解答】
(1)
{
2
(3k) = 9k 2
(
)
2
(3k ± 1) = 3 3k 2 ± 2k + 1
であるから、d2 = 3M +1 とおける．このとき、a2 +b2 +c2 =
3M + 1 となるのは、a, b, c のうち、１つだけが３の倍数でな
く、２つが３の倍数のときである．
(2)
{
2
(2k) = 4k 2
(
)
2
(2k + 1) = 4 k 2 + k + 1
であるから、d2 = 4M +1 とおける．このとき、a2 +b2 +c2 =
4M + 1 となるのは、a, b, c のうち、２つだけが偶数になると
きであるから、
（１）の結果と合わせれば、a, b, c のうち少な
くとも１つは６の倍数である．
-23-
25
第 4 章 ２次の不定方程式
入試問題から
(1) x2 + 5xy + 6y 2 − 3x − 7y = 0 を満たす整数 x, y を求めよ．
(2)
1 + 1 + 1 = 1 (p = q = r) を満たす整数の組の個数はいくつか．
p
q
r
2
解答
x2 + 5xy + 6y 2 − 3x − 7y = 0 を満たす整数解の１つはすぐに分かる．(x, y) = (0, 0) である．他に
解はないか。１文字着目ということで、x について解いてみようか。
x2 + (5y − 3) x + 6y 2 − 7y = 0
√
−5y + 3 ± y 2 − 2y + 9
⇔x=
2
√
Ohhh! ここで「観察」. x が整数になるためには、 y 2 − 2y + 9 が整数になればいい。そのため
には y 2 − 2y + 9 は平方数にならないとだめ。そこで
y 2 − 2y + 9 = m2 (m = 0)
とおこう．ここに m は整数である．さて、整数問題の鉄則：
「積形をつくれ！」という技法を思い
出そう。
2
(y − 1) − m2 = −8
⇔ (y − 1 − m) (y − 1 + m) = −8
と変形すれば、
(y − 1 − m) + (y − 1 + m) = 2 (y − 1)
だから、y − 1 + m, y − 1 − m はともに偶数。そして、y − 1 + m = y − 1 − m だから、
{
{
y−1+m=4
y−1+m=2
,
y − 1 − m = −2
y − 1 − m = −4
⇔ (y, m) = (2, 3) , (0, 3)
⇔ (x, y) = (0, 0) , (3, 0) , (−5, 2) , (−2, 2)
さて、ここでの２次式 x2 + 5xy + 6y 2 − 3x − 7y = 0 のグラフは双曲線です。この双曲線上にある
格子点を見つけようというのがこの問題です。そこで、x2 + 5xy + 6y 2 − 3x − 7y = 0 を双曲線ら
第 4. ２次の不定方程式
しく変形してみます。
x2 + 5xy + 6y 2 − 3x − 7y = 0
⇔ (x + 2y) (x + 3y) − 3x − 7y = 0
ここで、
{
x + 2y = X
x + 3y = Y
{
⇔
x = 3X − 2Y
y =Y −X
とおくと、
XY − 3 (3X − 2Y ) − 7 (Y − X) = 0
⇔ XY − 2X − Y = 0
⇔ (X − 1) (Y − 2) = 2
∴ (X − 1, Y − 2) = (1, 2) , (2, 1) , (−1, −2) , (−2, −1)
⇔ (X, Y ) = (2, 4) , (3, 3) , (0, 0) , (−1, 1)
⇔ (x, y) = (−2, 2) , (3, 0) , (0, 0) , (−5, 2)
２次の不定方程式が、双曲線の type ならば、積の形にすれば
2
いいことはわかった。では、楕円のときはどうしたらいいの
1
か。方程式の係数をちょっと変えて、
-3 -2 -1
-1
x2 + 5xy + 7y 2 − 3x − 7y = 0
1
2
3
4
5
6
7
8
-2
-3
を考えよう。するとグラフは図のような楕円になる。双曲線と楕円の違いの一つは、楕円は有限の
範囲に収まってしまうことである。そこで、虱潰しに格子点を check していこうという技法が生ま
れる。
x2 + 5xy + 7y 2 − 3x − 7y = 0
⇔ x2 + (5y − 3) x + 7y 2 − 7y = 0
を満たす実数 x が存在するために、
(
)
2
D = (5y − 3) − 4 7y 2 − 7y = 0
⇔ 3y 2 + 2y − 9 5 0
√
√
−1 − 2 7
−1 + 2 7
⇔
5y5
3
3
これをみたす整数 y は y = −2, −1, 0, 1. この y を x2 + (5y − 3) x + 7y 2 − 7y = 0 に代入して、
⇔ (x, y) = (6, −2) , (7, −2) , (0, 0) , (3, 0) , (−2, 1) , (0, 1)
こうして、２次の不定方程式は、
-26-
第 4. ２次の不定方程式
bababababababababababababababab
• 楕円型 …… 範囲を絞って虱潰し。
• 双曲線型…… 積の形に変形。
と技法を定型化しておけばいい。しかし、双曲線型で、x2 − 2y 2 = 1 のような type はそうはいか
ない。これはペル方程式とよばれているもので、後の主題でとりあげる。
つぎの（２）のタイプもよく出題される．
1 1 1
1
+ + = (p = q = r)
p q
r
2
のとき、条件の厳しい r から、その範囲を限定していこう。
1
1
1
5 5
p
q
r
だから、
1
1 1 1
1
3
< + + = 5 ⇔35r56
r
p q
r
2
r
( i ) r = 3 のとき、
1 1 1
1
1 1
1
+ + = ⇔ + =
p q
3
2
p q
6
⇔ pq − 6p − 6q = 0 ← 双曲線型
⇔ (p − 6) (q − 6) = 36 ← 積形に変形
⇔ (p − 6, q − 6) = (36, 1) , (18, 2) , (12, 3) , (9, 4) , (6, 6)
の５組の解。
( ii ) r = 4 のとき、
1 1 1
1
1 1
1
+ + = ⇔ + =
p q
4
2
p q
4
⇔ pq − 4p − 4q = 0
⇔ (p − 4) (q − 4) = 16
⇔ (p − 4, q − 4) = (16, 1) , (8, 2) , (4, 4)
の３組の解。
(iii) r = 5 のとき、
1
1 1
3
1 1 1
+ + = ⇔ + =
p q
5
2
p q
10
⇔ 3pq − 10p − 10q = 0
⇔ (3p − 10) (3q − 10) = 100
-27-
第 4. ２次の不定方程式
3p − 10, 3q − 10 は３で割ると余る数だから、
(3p − 10, 3q − 10) = (50, 2)
の１組の解。
(iv) r = 6 のとき、
1
1 1
1
1 1 1
+ + = ⇔ + =
p q
6
2
p q
3
⇔ pq − 3p − 3q = 0
⇔ (p − 3) (q − 3) = 9
⇔ (p − 3, q − 3) = (9, 1) , (3, 3)
の２の解。結局、全部で、１２組の解がある。
【演習 5】
4x2 + 10x − y 2 − y = 0
を満たす整数の組 (x, y) をすべて求めよ。
【日本女子大学】
【解答】
4x2 + 10x − y 2 − y = 0
(
)2
(
)2
5
25
1
1
⇔4 x+
−
− y+
+ =0
4
4
2
4
)2 (
)2
(
1
5
− y+
=6
⇔4 x+
4
2
(
)(
)
5
1
5
1
⇔ 2x + + y +
2x + − y −
=6
2
2
2
2
J 平方完成
⇔ (2x + y + 3) (2x − y + 2) = 6
であって、
2x + y + 3 + 2x − y + 2 = 4x + 4 + 1
J 積形完成
に注意すると、
(
)
2x + y + 3
J 和が４で割ると１余る数になる
( ) ( ) ( ) ( )
2
3
−1
−6
=
,
,
,
2x − y + 2
3
2
−6
−1
( ) ( ) ( ) ( ) ( )
x
0
0
−3
−3
⇔
=
,
,
,
y
−1
0
−3
2
__
__
1 次のように積形を作るのもよい。
4x2 + 10x − y 2 − y = 0
⇔ (2x + y) (2x − y) + 10x − y = 0
-28-
第 4. ２次の不定方程式
ここで、
{
2x + y = X
2x − y = Y
とおくと、
XY + 5
(
⇔ 2x =
X +Y
2
)
−
X +Y
X −Y
,y =
2
2
X −Y
=0
2
⇔ XY + 2X + 3Y = 0
⇔ (X + 3) (Y + 2) = 6
X + Y + 5 = 4x + 5 = (4 の倍数) + 1 だから、
(X + 3, Y + 2) = (2, 3) , (3, 2) , (−1. − 6) , (−6, −1)
以下略。
2 双曲線型である。
【演習 6】
abcd = a + b + c + d
を満たす正の整数 a, b, c, d を求めよ。
【東京女子大学】
【解答】
対称性より 0 < a 5 b 5 c 5 d とおいて考察する。
abcd = a + b + c + d
1
1
1
1
⇔1=
+
+
+
bcd acd abd abc
1
1
1
1
1
,
,
,
5 3
bcd acd abd abc
a
J 不等式を用いて範囲をしぼれ
だから
4
1 5 3 ⇔ a3 5 4 ⇔ a = 1
a
1=
J 最小の a が厳しい。だから、ま
ずは a
1
1
1
1
+
+
+
bcd cd bd bc
と、
1
1 1 1 1
1
5 3, , ,
5 2
bcd
b cd bd bc
b
-29-
第 4. ２次の不定方程式
とより、
1
3
+ 2
3
b
b
⇔ b3 − 3b 5 1
(
)
⇔ b b2 − 3 5 1
15
J b > 1 で単調増加
これを満たす b は b = 1 である。
cd = 2 + c + d
⇔ (c − 1) (d − 1) = 3
と変形して、
(c − 1, d − 1) = (1, 3) ⇔ (c, d) = (2, 4)
∴ {a, b, c, d} = {1, 1, 2, 4}
J {· · ··} は組み合せ
__
__
1 大小関係を導入することがポイント。
2 １文字ずつ量化していこう。必要条件でしぼりだしていく。(1 − bcd) a は a の単調増加関数だ
から、
abcd = a + b + c + d
(bcd − 1) a = b + c + d = bcd − 1
よって、
bcd − b − c − d 5 1
(cd − 1) b − c − d 5 1
b 5 1 だから、
cd − 1 − c − d 5 1
(c − 1) (d − 1) 5 3
∴ c − 1 = 1, d − 1 = 2
以下略。
【演習 7】
x, y, z は自然数で、x 5 y 5 z とする。
(1)
1 1
1
+ + = 1 を満たす x, y, z の値をすべて求めよ。
x y z
1 1 1
1 1 1
+ + < 1 を満たすとき、 + + の最大値と、最大値を与える x, y, z
x y z
x y z
の値を求めよ。
(2) x, y, z が
【1981 都立大学】
-30-
第 4. ２次の不定方程式
【解答】
J 前演習で修得済みの技術
(1)
1
1 1
1
1
1
3
1= + + 5 + + =
x y z
x x x
x
∴ x53
だから、x = 1, 2, 3 であるが x = 1 は適さず。
J 積形つくれ
x = 2 のとき、
1
1 1
= + ⇔ yz = 2y + 2z
2
y z
⇔ (y − 2) (z − 2) = 4
⇔ (y − 2, z − 2) = (1, 4) , (2, 2)
⇔ (y, z) = (3, 6) , (4, 4)
x = 3 のとき、
2
1 1
= + ⇔ 2yz = 3y + 3z
3
y z
(
)(
)
3
3
9
⇔ y−
z−
=
2
2
4
⇔ (2y − 3) (2z − 3) = 9
⇔ (2y − 3, 2z − 3) = (3, 3) (∵ 2y − 3 = 3)
⇔ (y, z) = (3, 3)
以上より、(x, y, z) = (2, 3, 6), (2, 4, 4), (3, 3, 3)
(2)
1
1 1
+ +
x y z
とおく。x 5 y 5 z とする。ここに、f は x, y, z の単調減少
関数である。x = 4 とすると、
1
1
1
3
3
f (x, y, z) 5 + + = 5
x x x
x
4
x = 3 のとき、
1 1
2
f (3, y, z) < 1 ⇔ + <
y z
3
1 1
のもとで + を最大にすることを考える。z を固定して、
y
z
3 5 y 5 z のもとでは、
f (x, y, z) =
1 1
1 1
2
+ 5 + <
y z
3 z
3
∴ z=4
∴ f (3, y, z) 5
1 1 1
11
+ + =
3 3 4
12
-31-
J 分母を小さくして、最大値を求め
る。
J 多変数で困ったら、１変数に着目、
他は固定
第 4. ２次の不定方程式
最後に x = 2 のときを考える。
1 1
1
f (2, y, z) < 1 ⇔ + <
y z
2
1 1
このもとで、 + を最大にすることを考える。z を固定し
y z
て、2 5 y 5 z のもとでは、
f (2, 2, z) > 1
となるから、y = 3 が必要。z を固定して、3 5 y 5 z のもと
では、
f (2, 3, z) =
5 1
+ <1⇔z>6
6 z
となるから、
41
42
これが求める最大値で、x = 2, y = 3, z = 7 である。
f (2, y, z) 5 f (2, 3, 7) =
__
__
1 この問題は頻出である。(2) は離散量の最大最小値問題である。一般には階差で議論するのが
常道であるが、ここでは単調減少は明らかに分かる。
2 x = 4, x = 3, x = 2 と場合分けをして議論するのがポイントである。
-32-
33
第 5 章 フェルマーの小定理
入試問題から
n, p が任意の自然数とするとき、np , np+4 の１の位の数字が一致することを証明せよ．
【甲南大学】
__ p p+4
p
p+4
の１の位の数字が一致するということは、n , n
を１０で割った余りが等しい、つ
__n , n
(
)
まり、np+4 − np が１０の倍数ということです。np+4 − np = np n4 − 1 が任意の自然数 p に対し
(
)
て、１０の倍数であるためには、n n4 − 1 が１０の倍数であることが必要十分です。倍数問題の
技法は次のようにまとめておきましょう。
bababababababababababababababab
1 剰余で分類
•
2 連続 p 整数の積を作る。
•
3 階差を調べる。
•
4 漸化式を作る。
•
1 の技法では
まず
(
)
(
)
f (n) = n n4 − 1 = n (n − 1) (n + 1) n2 + 1
とおくと、
( i ) n = 5m のときは、f (n) の因数の n が５の倍数
( ii ) n = 5m + 1 のときは、f (n) の因数の n − 1 が５の倍数
(iii) n = 5m + 2 のときは、f (n) の因数の n2 + 1 が５の倍数
(iv) n = 5m + 3 のときは、f (n) の因数の n2 + 1 が５の倍数
( v ) n = 5m + 4 のときは、f (n) の因数の n + 1 が５の倍数
第 5. フェルマーの小定理
よって、f (n) は５の倍数である．また、
( i ) n = 2m のときは、f (n) の因数の n が２の倍数
( ii ) n = 2m + 1 のときは、f (n) の因数の n − 1 が２の倍数
よって、f (n) は２の倍数である．２と５は互いに素だから、f (n) は１０の倍数である。
2 の技法では
M = (n − 2) (n − 1) n (n − 1) (n + 2)
は連続５整数の積だから、5! = 120 の倍数。
N = n (n − 1)
は連続２整数の積だから２の倍数である。よって、
(
)
f (n) = n n4 − 1
(
)
= n n4 − 5n2 + 4 − 5n3 + 5n
= M − 5N (n + 1)
は１０の倍数である。
3 の技法では、
5
f (n + 1) − f (n) = (n + 1) − (n + 1) − n5 + n
= 5n4 + 10n3 + 10n2 + 5n
(
)
= 5 n3 + 2n2 + 2n + 1 n
(
)
= 5n (n + 1) n2 + n + 1
は１０の倍数。f (1) = 0 倍数。も１０の倍数。よって、数学的帰納法により、f (n) は１０の倍数
である。
, ここで、n
5
− n は５の倍数であるという事実の背景が、次に Fermart の小定理です。
Fermart の小定理
p が素数のとき、np − n は p の倍数である．
これによれば、n − n は２の倍数．n − n は３の倍数．n − n は７の倍数になります．
2
3
7
＜証明＞
f (n) = np − n とおく．
f (n + 1) − f (n)
p
= (n + 1) − (n + 1) − np + n
=
p−1
∑
p Cr n
r
r=1
-34-
第 5. フェルマーの小定理
ここに、p は素数だから、pCr (1 5 r 5 p − 1) は p の倍数である．よって、f (n + 1) − f (n) は p
の倍数．また、f (1) = 0 も p の倍数．ゆえに数学的帰納法により、f (n) は p の倍数となる．
-35-
第 5. フェルマーの小定理
【演習 8】
選択肢から最も適切なものを選びその番号を解答欄に記入しなさい。
相異なる自然数 a と b が 1 以外に共通の約数を持たないとき，a と b は互いに素であるとい
う。自然数 n を素数 p で割った余りを Mp (n) で表すことにする。また p − 1 以下の自然数
x, y に対して，x ⊗ y = Mp (xy) と演算 ⊗ を定義する。ただし右辺の xy は通常の積である。
たとえば，M11 (6 × (1) ) = 2 である。この演算 ⊗ は交換法則 (2) (3) や結合法則 (4) (5)
を満たす。ここで x, y, z は p − 1 以下の自然数である。
次の命題はフェルマーの小定理とよばれている。
自然数 a と素数 p が互いに素ならば ap−1 を p で割った余りは 1 である。
命題
この命題を証明しよう。上の記号を用いれば Mp ( (6) ) = (7) を示せばよい。以下，Mp の
添字 p は省略する。x, y を p − 1 以下の自然数とする。M (ax) = M (ay) ならば a(x − y) は
(8) (9)
の (10) (11) となる。よって x = y でなくてはならない。この (12) (13) を考えれば，
(14) (15)
ならば (16) (17) である。このことから
M (1a), M (2a), · · · , M ((p − 1)a)
は異なった自然数である。よって
M (1a) ⊗ M (2a) ⊗ · · · ⊗ M ((p − 1)a) = 1 ⊗ 2 ⊗ · · · ⊗
(18) (19)
となる。一方，M の性質を使えば
M (1a) ⊗ M (2a) ⊗ · · · ⊗ M ((p − 1)a) = M (
(20)
) ⊗ 1 ⊗ 2 ⊗ ··· ⊗
(21) (22)
となる。x ⊗ y = y のとき，x = (23) となることに注意すれば，M ( (6) ) = (7) を得る。
(1)
(5)
(9)
(13)
(17)
(21)
(25)
(29)
(33)
(34)
(35)
1
(2) 2
0
(6) a
ap+1
(10) x − y
\ y
x+y
(14) x =
p+1
(18) p
逆
(22) 対偶
矛盾
(26) 倍数
互いに素
(30) p − 1 以下
x⊗y⊗z =y⊗z⊗x=z⊗x⊗y
x ⊗ (y ⊗ z) = (x ⊗ y) ⊗ z
x ⊗ (y + z) = x ⊗ y + x ⊗ z
(3)
(7)
(11)
(15)
(19)
(23)
(27)
(31)
3
ap−1
x⊗y
M (ax) = M (ay)
p−1
裏
約数
x⊗y =0
(4)
(8)
(12)
(16)
(20)
(24)
(28)
(32)
4
ap
xy
x=y
\ M (ay)
M (ax) =
否定
素数
x⊗y =y⊗x
【2005 慶應義塾大学】
【解答】
(1)
4
(2)(3)
32
(4)(5)
34
(6)
7
(7)
1
(8)(9)
18
(10)(11)
26
-36-
(12)(13)
22
(14)(15)
14
(16)(17)
20
第 5. フェルマーの小定理
(18)(19)
19
(20)
7
(21)(22)
19
(23)
1
自然数 n を素数 p で割った余りを Mp (n) で表すことにする。また p − 1 以下の自然数 x, y
に対して，x ⊗ y = Mp (xy) と演算 ⊗ を定義する。ただし右辺の xy は通常の積である。た
とえば，M11 (6 ×
4 ) = 2 である。この演算 ⊗ は交換法則
x ⊗ (y ⊗ z) = (x ⊗ y) ⊗ z
x ⊗ y = y ⊗ x や結合法則
を満たす。ここで x, y, z は p − 1 以下の自然数である。
次の命題はフェルマーの小定理とよばれている。
命題
自然数 a と素数 p が互いに素ならば ap−1 を p で割った余りは 1 である。
この命題を証明しよう。上の記号を用いれば Mp (ap−1 = 1 を示せばよい。以下，Mp の添字
p は省略する。x, y を p − 1 以下の自然数とする。M (ax) = M (ay) ならば a(x − y) は p の
倍数
となる。よって x = y でなくてはならない。この
対偶
\ y
を考えれば， x =
ならば
\ M (ay) である。このことから
M (ax) =
M (1a), M (2a), · · · , M ((p − 1)a)
は異なった自然数である。よって
M (1a) ⊗ M (2a) ⊗ · · · ⊗ M ((p − 1)a) = 1 ⊗ 2 ⊗ · · · ⊗
p-1
となる。一方，M の性質を使えば
M (1a) ⊗ M (2a) ⊗ · · · ⊗ M ((p − 1)a) = M ( ap−1
となる。x ⊗ y = y のとき，x =
1
) ⊗ 1 ⊗ 2 ⊗ ··· ⊗
p-1
となることに注意すれば，Mp (ap−1 ) = 1 を得る。
【演習 9】
自然数 n の関数 f (n), g(n) を
f (n) = n を 7 で割ったあまり、
)
( 7
∑
n
g(n) = 3f
k
k=1
によって定める．
(1) すべての自然数 n に対して、f (n7 ) = f (n) を示せ．
(2) あなたの好きな自然数 n を１つ決めて g(n) を求めよ．その g(n) の値をこの設問 (2) に
おけるあなたの得点とする．
【1995 京都大学】
1 フェルマーの小定理
-37-
第 5. フェルマーの小定理
【解答】
(1)
(n − 3) (n − 2) (n − 1) n (n + 1) (n + 2) (n + 3)
(
)(
)(
)
= n n2 − 1 n2 − 4 n2 − 9
(
)
= n n6 − 14n4 + 49n2 − 36
= n7 − 14n5 + 49n3 − 36n
(
)
= n7 − n + 7 −2n5 + 7n3 − 5n
(n − 3) (n − 2) (n − 1) n (n + 1) (n + 2) (n + 3) は連続７整
数の積だから７の倍数である．よって、n7 − n も７の倍数で
ある．すなわち、f (n7 ) = f (n) が成り立つ．
(2) n を６で割った余りを r, 商を q とおくと、n = 6q + r
k n − k r = k 6q+r − k r
(
)
= k r k 6q − 1
}
(
) {( 6 )q−1 ( 6 )q−2
( )
= kr k6 − 1
k
+ k
+ · · · + k6 + 1
}
(
) {( 6 )q−1 ( 6 )q−2
( )
= k r−1 k 7 − k
k
+ k
+ · · · + k6 + 1
であるから、r = 1, 2, 3, 4, 5 のときは、
f (k n ) = f (k r )
したがって、
g (n) = 3f (1 + 2n + 3n + 4n + 5n + 6n + 7n )
= 3f (1 + 2n + 3n + 4n + 5n + 6n )
= 3f (1 + 2r + 3r + 4r + 5r + 6r )
 r
r
r
6 + 1 = (7 − 1) + 1 = 7M + (−1) + 1


r
r
r
r
r
5r + 2 = (7 − 2) + 2 = 7M + (−2) + 2

 r
r
r
r
r
r
4 + 3 = (7 − 3) + 3 = 7M + (−3) + 3
だから、r が奇数のときは、これらはみな７の倍数になる．だ
から、
g (n) = 3f (1 + 2r + 3r + 4r + 5r + 6r ) = 0
．r = 2 のとき、
1 + 2r + 3r + 4r + 5r + 6r
= 7M + 2 (1 + 4 + 9) = 7N
だから、
g (n) = 3f (1 + 2r + 3r + 4r + 5r + 6r ) = 0
r = 4 のとき、
1 + 2r + 3r + 4r + 5r + 6r
(
)
= 7M + 2 1 + 42 + 92 = 7N
-38-
第 5. フェルマーの小定理
だから、
g (n) = 3f (1 + 2r + 3r + 4r + 5r + 6r ) = 0
よって、r = 1, 2, 3, 4, 5 のとき、g(n) = 0
n = 6q のとき、
【演習 10】
(1) 正の整数 n で n3 + 1 が 3 で割り切れるものをすべて求めよ。
(2) 正の整数 n で nn + 1 が 3 で割り切れるものをすべて求めよ。
【2003 一橋大学】
1 余りで分類．
2 連続 p 整数の積は p! の倍数．
【解答】
(1) n3 − n = (n − 1)n(n + 1) は連続３整数の積ゆえ３の倍数で
ある．
したがって、n3 + 1 = n3 − n + n + 1 が３の倍数になるの
は、n + 1 が３の倍数のときである．
(2) f (n) = nn + 1 とおく．
( i ) n = 3m のとき、
n
f (3m) = (3m) + 1
は３の倍数ではない．
( ii ) n = 3m + 1 のとき、
n
f (3m + 1) = (3m + 1) + 1 = 3M + 1 + 1 = 3M + 2
は３の倍数ではない．
(iii) n = 3m − 1 のとき、
n
n
f (3m − 1) = (3m − 1) + 1 = 3M + (−1) + 1
が３の倍数であるのは、n が奇数のとき．3m−1 = 2l −1
とおけるから、m は偶数．
∴ n = 3 (2k) − 1 = 6k − 1
-39-
第 5. フェルマーの小定理
【演習 11】
n を 2 以上の整数とするとき，次の問いに答えよ。
(1) n3 − n が 6 で割り切れることを証明せよ。
(2) n5 − n が 30 で割り切れることを証明せよ。
【2005 弘前大学】
1 連続 p 整数の積は p! の倍数．
2 漸化式．数学的帰納法．
【解答】
(1) n3 − n = (n − 1)n(n + 1) は連続３整数の積ゆえ 3! = 6 の倍
数である．
(2)
(n − 2) (n − 1) n (n + 1) (n + 2)
(
)(
)
= n n2 − 1 n2 − 4
= n5 − 5n3 + 4n
は連続５整数の積だから、5! = 120 の倍数である．
n5 − n = (n − 2) (n − 1) n (n + 1) (n + 2) + 5n3 − 5n
(
)
= (n − 2) (n − 1) n (n + 1) (n + 2) + 5 n3 − n
と変形して、（１）の結果を合わせると、n5 − n は３０の倍
数である．
【演習 12】
3 以上 9999 以下の奇数 a で，a2 − a が 10000 で割り切れるものをすべて求めよ。
【2005 東京大学】
1 a と a − 1 はお隣さん．
2 1 次不定方程式に．
【解答】
a (a − 1) = 10000Q = 24 · 54 Q
a が奇数、a − 1 が偶数であって、しかも同時に５の倍数になるこ
-40-
第 5. フェルマーの小定理
ともないから、
a = 54 M (M : 奇数) , a − 1 = 24 · N または、
a = M (M :) , a − 1 = 24 · 54 N
後者の場合は
a = 10000N + 1 > 10001
となり、条件に適さず．
a = 54 M, a − 1 = 24 N
のとき、a を消去すると、
54 M − 1 = 24 · N ⇔ 625M + 16N = 1
625 = 16 × 39 + 1 ⇔ 625 · 1 + 16 · (−39) = 1
を利用すると．
625 (M − 1) + 16 (N + 39) = 0
と変形でき、625 と 16 は互いに素だから、
N + 39 = 625m
N = 625m + 39
∴ a = 24 · (625m + 39) + 1
= 10000m + 625
a < 10000 だから、a = 625
__
__ ax + by = c · · · ♣ を満たす整数解 (x, y) を求めるには、定数項 c を消去して、♣ を積形にす
1 のとき、この式を満たす特殊な解を１つ求め
るのがポイントです．例えば、73x + 18y = 3 · · · 2 となり、特
ます．73 を 18 で割ると、73 = 18 × 4 + 1 であるから、73 × 3 + 18 × (−12) = 3 · · · 1 −
2 より
殊な解が見つかります．
73(x − 3) + 18(y + 12) = 0 ⇔ 73(x − 3) = −18(y + 12)
73 と 18 は互いに素だから、
x − 3 = −18m, y + 12 = 73m ⇔ x = 3 − 18m, y = 73m − 12
と一般解が得られます．
さて、特殊な解が割り算１回で求められましたが、いつもこううまくは行きません．そのような
ときは繰り返し割り算を実行します．ユークリッドの互除法という手法で求めることができます．
-41-
43
第 6 章 Pell 方程式
次の
の中に適当な数または式を入れよ。また、（イ）∼（ホ）の「 」で囲まれた
文章の理由を、述べよ。
1
方程式 x2 − 3y 2 = 1 · · · · · · を満たす整数の組 (x, y) を求めることを考える。
（以下この方程式の整数解を単に解と略称す
る。）準備のために次のことを確かめておく。
√
√
(イ) 「a, b, c, d が整数であって、a + b 3 = c + d 3 ならば、a = c, b = d である」次に (x, y) が
1 により、明らかであ
解であれば、(x, −y), (−x, y), (−x, −y) もかいであることは、方程式
るから (x, y) がともに負でない解を求めることが基本的である。それでそのような解を求め
る手段として、
√
√
2 (xn , yn は負でない整数、n = 1, 2, 3, · · · )
(2 + 3)n = xn + yn 3 · · · · · · とおく。そうすると（イ）によって
3
x0 = 1, y0 = 0.x1 = 2, y1 = 1 · · · · · · , y2 = , x3 = , y3 = √
√
√
√
である。一方、(2 + 3)2 と (2 − 3)2 ,(2 + 3)3 と (2 − 3)3 などを比較することによっ
て、一般に、
√
√
4
(2 − 3)n = xn − yn 3, n = 0, 1, 2, 3 · · · · · · √
√
2 と
4 と (2 +
であることがわかる。
3)(2 − 3) = 1 とを使って、
√
√
1 = (2 + 3)n (2 − 3)n = xn 2 − 3yn 2
x2 =
2 で定まる (xn , yn ) は方程式の解であることがわかる。とくに x, y の一方が 0
となるから、
3 の (x0 , y0 ) にほかならない。
となるような負でない解は、明らかに、x = 1, y = 0 でそれは
次に (xn−1 , yn−1 ), と (xn , yn ) との関係を求めてみる。(n = 1)
(
√ )n
xn + yn = 2 + 3
(
√ )
= (xn−1 + yn−1 ) 2 + 3
=
第 6. PELL 方程式
ゆえに、xn =
, yn =
したがって、(x0 , y0 ) から出発して、負でない解 (x1 , y1 ), (x2 , y2 ), · · · , (xn , yn ), · · · , を順次
求めて行くことができる。しかも、y1 < y2 < y3 < · · · である。
以上のことで負でない解を多数みつけたのであるが、これらで負でない解が尽くされている
かどうかを次に吟味する。
いま任意の正の解 (x, y)(x > 0, y > 0) とすると、
√
√
√
(x + 3y)(2 − 3) = (2x − 3y) + (2y − x) 3
(ロ) 「x0 = 2x − 3y, y 0 = 2y − x とおくとき、(x0 , y 0 ) も解である。」
(ハ) 「それで、任意の正の解 (x, y) から出発して、（ロ）における (x0 , y 0 ) を求める操作を順
3 に示す負でない解 (x0 , y0 ) に達する」
次行うことによって、
2 によって定まる (xn , yn )(n = 0, 1, 2, · · · ) のど
(ニ) 「したがって、任意の負でない解 (x, y) は式
れか１つである。」
【京都大学】
解答 数学の問題としては長文の問題で出題者の思考について行くのも大変ですが、整数問題の
有名な問題です。
（イ）の理由
√
√
a + b 3 = c + d 3 (a, b, c, d ∈ Z)
\ 0 とすると、
のとき、b − d =
√
c−a
3=
= 有理数
b−d
となって矛盾。よって、
a = c, b = d
である。
(
√ )n
√
2
2 + 3 = xn + yn 3 · · · · · · とおくと、
(
√
√ )(
√ )
xn+1 + yn+1 3 = 2 + 3 xn + yn 3
√
= 2xn + 3yn + (xn + 2yn ) 3
{
xn+1 = 2xn + 3yn
∴
yn+1 = xn + 2yn
-44-
第 6. PELL 方程式
これより、
(x0 , y0 ) = (1, 0) , (x0 , y0 ) = (2, 1)
(x2 , y2 ) = (7, 4) , (x3 , y3 ) = (26, 15)
√
√
xn+1 − yn+1 3 = 2xn + 3yn − (xn + 2yn ) 3
(
√ )(
√ )
= 2 − 3 xn − yn 3
(
√
√ )n (
√ ) (
√ )n
∴ xn − yn 3 = 2 − 3
x0 + y0 3 = 2 − 3
∴
(
√ )(
√ ) (
√ )n (
√ )n
xn + yn 3 xn − yn 3 = 2 − 3
2+ 3
∴ x2n − 3yn2 = 1
2 で生成される (xn , yn ) は Pell 方程式 x2 − 3y 2 = 1 の負でない解である。
だから、
（ロ）の理由 いま任意の正の解 (x, y)(x > 0, y > 0) とすると、
√
√
√
(x + 3y)(2 − 3) = (2x − 3y) + (2y − x) 3
x0 = 2x − 3y, y 0 = 2y − x とおくとき、
x02 − 3y 02 = (2x − 3y) − 3 (−x + 2y)
2
2
= x2 − 3y 2 = 1
であるから、(x0 , y 0 ) も解である。
（ハ）の理由
x − x0 = x − (2x − 3y)
= −x + 3y
9y 2 − x2
6y 2 − 1
=
>0
3y + x
3y + x
4x2 − 9y 2
x0 = 2x − 3y =
2x + 3y
( 2
)
4 3y + 1 − 9y 2
=
=
2x + 3y
3y 2 + 12
>0
=
2x + 3y
=
だから、x > x0 > 0
y − y 0 = y − (−x + 2y)
=x−y
x2 − y 2
2y 2 + 1
=
>0
x+y
x+y
−x2 + 4y 2
y 0 = −x + 2y =
x + 2y
( 2
)
− 3y + 1 + 4y 2
y2 − 1
=
=
=0
x + 2y
x + 2y
=
-45-
第 6. PELL 方程式
だから、y > y 0 = 0
（ニ）の理由
(x, y) → (x0 , y 0 )
の操作を繰り返していけば、この列は単調に減少するから、有限回の操作によって、(x0 , y0 ) に達
する。
（ホ）の理由
任意の負でない解 (x, y) に対して、
(
√ )n
√ )(
x + 3y 2 − 3 = 1
(
√
√ )n
1
⇔ x + 3y = (
√ )n = 2 + 3
2− 3
2 によって定まる (xn , yn )(n = 0, 1, 2, · · · )
となる n が存在するから、任意の負でない解 (x, y) は式
のどれか１つである。
【演習 13】
(1) 等式 (x2 − ny 2 )(z 2 − nt2 ) = (xz + nyt)2 − n(xt + yz)2 を示せ。
(2) x2 − 2y 2 = −1 の自然数解 (x, y) が無限組であることを示し、x > 100 となる解を１組
求めよ。
【1998 お茶の水女子大学】
解答
(1)
2
2
(xz + nyt) − n (xt + yz) = x2 z 2 + 2xznt + n2 y 2 t2 − nx2 t2 − 2xznt − ny 2 z 2
= x2 z 2 − nx2 t2 + n2 y 2 t2 − ny 2 z 2
(
)(
)
= x2 − ny 2 z 2 − nt2
(2) (1) で n = 2, z = t = 1 とおくと、
( 2
)
2
2
x − 2y 2 (−1) = (x + 2y) − 2 (x + y)
が成り立つ。これより、(x, y) が x2 − 2y 2 = 1 を満たすならば、
X = x + 2y, Y = x + y
で定まる (X.Y ) は X 2 − 2Y 2 = −1 を満たす。また、
(x, y) が x2 − 2y 2 = −1 を満たすならば、
X = x + 2y, Y = x + y
-46-
第 6. PELL 方程式
で定まる (X.Y ) は X 2 − 2Y 2 = 1 を満たす。そこで、x, y が、x2 − 2y 2 = 1 を満たすならば、
{
X = (x + 2y) + 2 (x + y) = 3x + 4y
Y = (x + 2y) + (x + y) = 2x + 3y
なる (X.Y ) は X 2 − 2Y 2 = 1 を満たすことがわかる。このとき、1 つの自然数の解 (x, y) のに
対して、この (X, Y ) は
X > x, Y > y
なる異なる大きな解の組が得られる。そこで、解 (1, 1) から初めてこの変換を繰り返せば、よ
り大きい解がいくらでも得られる。こうして、無数に解が存在することがわかる。
(7, 5) → (41, 29) → (239, 169) → (571, 264)
と求めれば、(x, y) = (239, 169) が１つの解になる。
【演習 14】
２つの条件
( i ) a2 − 2b2 = 1 または a2 − 2b2 = −1
√
( ii ) a + 2b > 0
を満たす任意の整数 a, b から得られる実数 g = a +
√
2b 全体の集合を G とする。1 より大き
い G の元のうち最小のものを u とする。
(1) u を求めよ。
(2) 整数 n と G の元 g に対し、gun は G の元であることを示せ。
(3) G の任意の元 g は適当な整数 m によって、g = um と書かれることを示せ。
【東京工業大学】
解答
(1) 条件 (i)(ii) を満たす (a, b) の存在範囲は図のようになる。
√
この中の格子点 (a, b) を通り、k = a + 2b を最小にす
√
るものは、a = 1, b = 1 でこのとき、1 + 2 > 1 となる。
つまり、
√
u=1+ 2
(2)
√
√
a + b 2 ∈ G, c + d 2 ∈ G
-47-
b
O
a
第 6. PELL 方程式
のとき、
(
√ )(
√ )
√
a + b 2 c + d 2 = (ac + 2bd) + (bc + ad) 2
であり、
2
2
(ac + 2bd) − 2 (bc + ad)
= a2 c2 + 4b2 d2 − 2b2 c2 − 2a2 d2
(
)
(
)
= a2 − 2b2 c2 − 2d2 a2 − 2b2
(
)(
)
= a2 − 2b2 c2 − 2d2 = ±1
(
√ )
√ )(
∴ a+b 2 c+d 2 ∈G
であるから、G は乗法について閉じている。したがって、自然数 n について、
1
gun ∈ G · · · √
1
√ = −1 + 2
u−1 =
1+ 2
1 は負の整数でも成立する。
も条件を満たすものだから、u−1 ∈ G となるので、
(3)
k < j ⇒ u k < uj
が成り立つ。いま、任意の g ∈ G に対して、
uk <5 g 5 uk+1
となる整数 k が存在する。このとき、
1 < gu−k 5 u
ここに、u の最小性より、
gu−k = u ⇔ g = uk+1
となる。
【演習 15】
{
√
}
A = m + n 3 |m, n は整数 とする。
√
(1) 集合 A を定義域とする関数 f を f (m + n 3) = m2 − 3n2 と定める。このとき、A の２
元 x, y に対し、f (xy) = f (x)f (y) が成り立つことを示せ。
(2) 0 でない整数 k が与えられたときに、方程式 m2 − 3n2 = k が整数解 (m, n) を１つで
ももつならば、この方程式は解を無数にもつことを示せ。ただし、(1) の f について
√
f (2 + 3) = 1 となることを用いよ。さらに、k = 4 のときは解があるかどうか、もし
あるならば３組求めよ。
【津田塾大学】
解答
-48-
第 6. PELL 方程式
(1)
√
x=m+n 3∈A
√
y =p+q 3∈A
のとき、
(
√ )(
√ )
xy = m + n 3 p + q 3
√
= mp + 3nq + (np + mq) 3
だから、
2
2
f (xy) = (mp + 3nq) − 3 (np + mq)
(
)(
)
= m2 − 3n2 p2 − 3q 2 = f (x) f (y)
(2) m2 − 3n2 = k を満たす１つの解は対称性により、m = 0, n = 0 と考えてよく、m, n の少なく
とも１つは 0 でない。
√
x=m+n 3
√
u=2+ 3
とおくと、
f (xu) = f (x) f (u) = k × 1 = k
√
xu = 2m + 3n + (m + 2n) 3
であるから、(2m + 3n, m + 2n) も解である。この解は元の解と異なってしかも解の成分は増
加しているから、この操作を続ければ無数の解が得られる。(2, 0) からはじめると、
k = 4 のとき、
(4, 2) → (14, 8) → (52, 30)
と３組の解を得る。
【演習 16】
(
)
2 −3
とする。
−1 2
( 0)
( )
x
x
2
2
(1)
=
A
で x2 − 3y 2 = 1, x > 0, y = 1 ならば、x0 − 3y 0 = 1, 0 5 y 0 < y が成立
y0
y
することを示せ。
( )
( )
1
x
(2) x, y が x2 − 3y 2 = 1 を満たす自然数ならば、ある自然数 n をとると、
= An
と
0
y
なることを示せ。
A=
【1988 京都大学】
解答は自力作成せよ。
-49-
51
第 7 章 オイラー関数・約数の個数・完全数
入試問題から
自然数 n に対して、実数 f (n) を次の規則で定める。
(A) f (1) = 1
(
)
1
(B) 素数 p, 自然数 n に対して、f (pa ) = pa 1 −
p
(C) 自然数 m, n が互いに素であるとき、f (mn) = f (m)f (n)
f (n)
(1) 自然数 n(n = 2) を n = pa1 1 · pa2 2 · · · par r (ar = 1) と素因数分解するとき、
を
n
p1 , p2 , · · · , pr を用いて表せ。
(2) f (n) =
1
n となるとき、n = 2a · 3b (a = 1, b = 1) と表されることを示せ。
3
【1993 横浜市立大学】
a
(1) pai i と pj j は互いに素であるから (C) より、
r
f (n) = f (p1α1 ) · · · f (pα
r )
つづいて、(B) を用いて、
(
)
(
)
1
1
αr
1
f (n) = pα
1
−
·
·
·
p
1
−
r
1
p1
pr
(
) (
)
1
1
αr
1
1−
= pα
··· 1 −
1 · · · pr
p1
pr
(
)
)
(
1
1
··· 1 −
=n 1−
p1
pr
(
)
(
)
f (n)
1
1
∴
= 1−
··· 1 −
n
p1
pr
1
(2) f (n) = n となるのは、(1) より、
3
(
)
(
)
1
1
1
1−
··· 1 −
=
p1
pr
3
⇔ 3 (p1 − 1) · · · (pr − 1) = p1 · · · pr
第 7. オイラー関数・約数の個数・完全数
ここで、一般性を失うことなく、
2 5 p1 < p2 < · · · < pr
\ 2 とすると、左辺は偶数、右辺は奇数だから、矛盾。よって、p1 = 2 である。
とおく。p1 =
3 (p2 − 1) · · · (pr − 1) = 2p2 · · · pr
左辺は 2 の倍数だから、p2 = 3 である。p3 が存在するとすれば、
(p3 − 1) · · · (pr − 1) = p3 · · · pr
となって、矛盾。
∴ n = 2a · 3b
ここで登場した関数 f はオイラー関数と呼ばれる整数論関数のひとつである。これは次のよう
に定義される関数で ϕ を用いる。
m > 1 のとき、m より小さくて m と互いに素な自然数の個数を ϕ(m) と表す。ただし、
ϕ(1) = 1 と定める。
言い方を換えると、ϕ(m) は 1 2
m−1
, ,··· ,
m m
m
の中の既約分数の個数でもある。ϕ(m) についての次の定理が成り立つ。
定理１ p が素数のとき、ϕ(pk ) = pk − pk−1 。とくに、ϕ(p) = p − 1 である。
定理２ a, b が互いに素ならば、
ϕ (ab) = ϕ (a) ϕ (b)
定理３ α が α = pa1 1 · pa2 2 · · · · · par r と素因数分解されるとき、
(
) (
)
1
1
ϕ (α) = α 1 −
··· 1 −
p1
pr
以下に証明を揚げる。
定理１の証明 pk 以下で pk と互いに素でない数は、p, 2p, 3p, · · · , pk の pk−1 個あるから、
ϕ(pk ) = pk − pk−1
-52-
第 7. オイラー関数・約数の個数・完全数
定理２の証明 1 から ab までの数を次のように並べる。
1
2
3
1+a
2+a
3+a
1 + 2a
2 + 2a
3 + 2a
···
···
···
1 + (b − 1) a 2 + (b − 1) a 3 + (b − 1) a
···
···
···
···
···
a
2a
3a
···
ba
1 から a までに a と互いに素であるものは p = ϕ (a) 個ある。これらを
α 1 , α2 , · · · , αp
とする。このとき、αi + ak と a は互いに素であるから、1 から ab までで a と互いに素であ
るものは
α1
α2
α3
α1 + a
α2 + a
α3 + a
α1 + 2a
α2 + 2a
α3 + 2a
···
···
···
α1 + (b − 1) a α2 + (b − 1) a α3 + (b − 1) a
···
···
···
···
···
αp
αp + a
αp + 2a
···
αp + (b − 1) a
この表を縦にみて、任意の列：
αi
αi + a
αi + 2a · · · · · ·
αi + (b − 1) a
の b 個の数を b で割った余りは互いに異なる。もし、同じ余りになるものがあるとすると、
αi + ma ≡ αi + na (mod b)
⇔ (m − n) a ≡ (mod b)
となって、a, b が互いに素であることに矛盾する。よって、この列を b で割った余りは 0, 1, 2, · · · , b−
1 すべてである。この b 個の中には b と互いに素であるものは ϕ (b) 個あるから、
ϕ (ab) = ϕ (a) ϕ (b)
が成り立つ。
定理３の証明
ϕ (α) = ϕ (pa1 1 · pa2 2 · · · · · par r )
= ϕ (pa1 1 ) ϕ (pa2 2 ) · · · ϕ (par r )
(
)
)
(
)
(
1
1
1
= pa1 1 1 −
pa2 2 1 −
· · · par r 1 −
p1
p2
pr
)(
)
(
)
(
1
1
1
1−
··· 1 −
=α 1−
p1
p2
pr
-53-
第 7. オイラー関数・約数の個数・完全数
【演習 17】
\ q ）の形で表されるとき，n の正の約数は 6 個あり，
自然数 n が n = p2 q （p, q は素数，p =
それらの和は
(
)(
)
ア + p + p2
イ +q
と表すことができる。このような n で正の約数の和が 2n となるような数を求める。正の約
数の和が 2n であるから，
(
)
)(
2p2 q =
ア + p + p2
イ +q
が成り立つ。 ア + p + p2 は奇数であり，p の倍数ではないから， イ + q は 2p2 の倍数
となり，
イ + q = 2p2 k（k は自然数）
とおける。したがって，
)
(
ア + p + p2 k
q=
となるが，q は素数であるから。k =
ウ である。よって
p2 − p − エ = 0
これを解いて，p =
オ である。ゆえに n =
カ である。
【2010 早稲田大学】
【解答】
ア
1
イ
1
ウ
1
エ
2
オ
2
カ
28
\ q ）の形で表されるとき，n の正の約数は 6 個あり，そ
自然数 n が n = p2 q （p, q は素数，p =
れらの和は
(
)
1 + p + p2 + q + qp + qp2 = 1 + p + p2 (1 + p)
と表すことができる。このような n で正の約数の和が 2n となるような数を求める。正の約数の和
が 2n であるから，
(
)
1 + p + p2 (1 + p) = 2p2 q
が成り立つ。1 + p + p2 = 1 + p(p + 1) は奇数であり，p の倍数ではないから，1 + q は 2p2 の倍数
となり，
1 + q = 2p2 k（k は自然数）
とおける。したがって，
(
)
q = 1 + p + p2 k
-54-
第 7. オイラー関数・約数の個数・完全数
となるが，q は素数であるから。k = 1 である。よって
p2 − p − 2 = 0
これを解いて，p = 2 である。ゆえに n = 28 である。
自然数 n が
αk
α2
1
n = pα
1 · p2 · · · · · pk
と素因数分解されるとき、n の約数は
px1 · py2 · · · · · pzk


x = 0, 1, · · · , α1 ,
 y = 0, 1, · · · , α , 
2 



··· ,

z = 0, 1, · · · , αk
と表されるからその個数 d(n) は
d (n) = (1 + α1 ) (1 + α2 ) · · · (1 + αk )
また、約数の総和は
αk
α2
1
σ (n) = (1 + p1 + · · · + pα
1 ) (1 + p2 + · · · + p2 ) · · · (1 + pk + · · · + pk )
=
k +1
1 +1
2 +1
1 − pα
1 − pα
1 − pα
1
2
k
×
× ··· ×
1 − p1
1 − p2
1 − pk
である。
一般に正の整数 n について、
σ (n) = 2n
となる n を完全数という。
σ (6) = (1 + 2) (1 + 3) = 12 = 2 · 6
σ (28) = (1 + 2 + 4) (1 + 7) = 56 = 2 · 28
だから、6,28 は完全数である。
完全数について次の定理が有名である。
定理
2n − 1 が素数ならば、2n−1 (2n − 1) は完全数である。
（証明）
p = 2n − 1, N = 2n−1 p
-55-
第 7. オイラー関数・約数の個数・完全数
とおくと、
(
)
σ (N ) = 1 + 2 + 22 + · · · + 2n−1 (1 + p)
= (2n − 1) (1 + p)
= (2n − 1) 2n
= 2N
よって、示せた。これにより、
n = 2 とおくと, 2n − 1 = 3, N = 6
n = 3 とおくと, 2n − 1 = 7, N = 28
n = 5 とおくと, 2n − 1 = 31, N = 496
と順に完全数が得られる。
ここで、現れた 2n − 1 という形で書ける素数をメルセンヌ数という。
【演習 18】
自然数 n に対して，n 以下の自然数で n との最大公約数が 1 であるような自然数の個数を
f (n) とする。
例えば，n = 12 に対しては，このような自然数は，1, 5, 7, 11 の 4 個なので，f (12) = 4 で
ある。また，f (1) = 1, 素数 p に対しては f (p) = p − 1 である。
次の問に答えよ。
(1) f (77) の値を求めよ。
(2) f (pq) = 24 となる 2 つの素数 p, q （ただし，p < q とする）の組を求めよ。
(3) k, n を自然数とするとき，f (2k 3n ) の値を k と n の式で表せ。
【2005 早稲田大学（社会科学）】
(1) 77 = 7 × 11 である。
[ ]
[ ]
[ ]
77
77
77
= 11,
= 7.
=1
7
11
77
より 1 から 77 までで 7 または 11 で割り切れる数は、
11 + 7 − 1 = 17
個ある。
∴ f (77) = 77 − 17 = 60
オイラー関数により、
)(
)
(
1
1
1−
= 60
f (77) = 77 1 −
7
11
-56-
第 7. オイラー関数・約数の個数・完全数
(2)
f (pq) = pq − p − q + 1 = (p − 1) (q − 1) = 24
だから、
∴ (p − 1, q − 1) = (1, 25) , (2, 12) , (3, 8) , (4, 6) ,
⇔ (p, q) = (2, 26) , (3, 13) , (4, 9) , (5, 7)
このうち適するものは、
(p, q) = (3, 13) , (5, 7)
(3)
(
)
f 2k · 3n = 2k · 3n −
([
] [ k n ] [ k n ])
2k · 3n
2 ·3
2 ·3
+
−
2
3
2·3
= 2k · 3n − 2k−1 · 3n − 2k · 3n−1 + 2k−1 · 3n − 1
(
)(
)
1
1
= 2k · 3n 1 −
1−
= 2k · 3n−1
2
3
【演習 19】
p を素数，n を正の整数とするとき，(pn )! は p で何回割り切れるか。
1, 2, 3, · · · · · · , pn
の中に、p の倍数は
[ n]
p
p
個あり、この中には p2 の倍数が
[ n]
p
p2
個ある。これを繰り返していくと、(pn )! は p で
n [ n]
∑
p
pn − 1
=
pk
p−1
k=1
回割れる。
-57-
【2009 京都大学】
第 7. オイラー関数・約数の個数・完全数
∞ [ n ]
∑
である。
k
k=1 2
1 から n までの自然数の積 n! を素因数分解すると, 2 の指数は、
∞ [ n ]
∑
である。
k
k=1 3
3 の指数は、
生徒の質問
Mn = 2n − 1 (n ∈ N )
F (x) は x (x ∈ N ) の約数の総和とする。
1
(1) 「n は素数でない。 ⇒ Mn は素数でない。」· · · · · · 2
「n は素数である。 ⇒ Mn は素数である。」· · · · · · 1 を示せ。また、
2 の反例をあげよ。
(2) x, k, l が正の整数であるとき、x = k · l のとき、F (x) = F (k) × F (l) が成り立つことを
示せ。
(3)
[
]
N は偶数である。かつ
3
······
F (N ) = 2N

1
Mn (Mn + 1)
······

4
2
(n は Mn が素数となるような値とする)

N=
3 をみたすことと、N が
4 をみたすことは同値であることを示せ。
このとき、N が
3 （もしくは
4 ）のとき、N の末尾の数は 6 か 8 であることを示せ。
(4) 1 の証明」
(1) 「
n は素数であるから、２つの 2 以上の整数 a, b の積と表される。このとき、
Mn = 2ab − 1
{
}
b−1
b−2
= (2a − 1) (2a )
+ (2a )
+ · · · + 2a + 1
であり、
2a − 1 > 1, (2a )
b−1
b−2
+ (2a )
+ · · · + 2a + 1 > 0
であるから、Mn は素数ではない。
1 の反例」
「
23 − 1 = 7, 25 − 1 = 31, 27 − 1 = 127,
211 − 1 = 2047 = 23 × 89
-58-
第 7. オイラー関数・約数の個数・完全数
(2) k の約数を
1, p1 , p2 , · · · · · · , pn
l の約数を
1, q1 , q2 , · · · · · · , qm
とすると、x = kl の約数は
1, p1 , p2 , · · · · · · , pn
q1 , q1 p1 , q1 p2 , · · · · · · , q1 pn
q2 , q2 p1 , q2 p2 , · · · · · · , q2 pn
············
qm , qm p1 , qm p2 , · · · · · · , qm pn
であるから、
F (kl) = 1 + p1 + p2 + · · · · · · + pn
+q1 (1 + p1 + p2 + · · · · · · + pn )
+q2 (1 + p1 + p2 + · · · · · · + pn )
············
+qm (1 + p1 + p2 + · · · · · · + pn )
= (1 + q1 + q2 + · · · · · · + qm ) (1 + p1 + p2 + · · · · · · + pn )
= F (k) F (l)
p が素数のとき、pn の約数は
1, p, p2 · · · , pn
だから、
F (pn ) = (1 + p + p2 + · · · pn ) =
1 − pn+1
1−p
x を素因数分解して、
x = p1 α1 · p2 α2 · · · · · · · pk αk
と表わせたとすると、
F (x) =
1 − p1 α1 +1
1 − p2 α2 +1
1 − pk αk +1
×
× ··· ×
1 − p1
1 − p2
1 − pk
となる。
-59-
第 7. オイラー関数・約数の個数・完全数
4 の証明」
3 ⇒
(3) 「
N は偶数であるから、
N = 2n · M (M : 奇数)
とおける。
{
(
)
F (N ) = F (2n ) F (M ) = 2n+1 − 1 F (M )
F (N ) = 2N = 2n+1 · M
(
)
∴ 2n+1 · M = 2n+1 − 1 F (M )
この式において、2n+1 は偶数、M は奇数、2n+1 − 1 は奇数であるから、2n+1 − 1 は M の約
数である。
(
)
M = 2n+1 − 1 M1
とおくと、
(
)
(
)
2n+1 · 2n+1 − 1 M1 = 2n+1 − 1 F (M )
∴ 2n+1 · M1 = F (M )
((
)
)
F (M ) = F 2n+1 − 1 M1
(
)
= F 2n+1 − 1 F (M1 )
だから、
(
)
(
)
5
2n+1 · M1 = F 2n+1 − 1 F (M1 ) = F 2n+1 − 1 M1 · · · · · · ここで等号が成り立つのは、
F (M1 ) = M1 ⇔ M1 = 1
のときであることに注意。従って、
(
)
6
2n+1 > F 2n+1 − 1 > 2n+1 · · · · · · (
)
∴ F 2n+1 − 1 = 2n+1
5 ,
6 より、M = 2n+1 − 1 であるから、
これより、2n+1 − 1 は素数であることがわかる。
(
) 1
N = 2n · 2n+1 − 1 = Mn+1 (Mn+1 + 1)
2
とかけて、ここに、2n+1 − 1 は素数である。
4 ⇒
3 の証明」
「
N = 2n−1 (2n − 1)
で 2n − 1 が素数のとき、
(
)
F (N ) = F 2n−1 F (2n − 1)
= (2n − 1) 2n = 2N
-60-
第 7. オイラー関数・約数の個数・完全数
(4)
(
)
(
)
an+4 = 2n+4 2n+5 − 1 − 2n 2n+1 − 1
(
)
= 2n 2n+9 − 16 − 2n+1 + 1
{
}
= 2n 2n+1 · 255 − 15 = 10 の倍数
であるから、an の１位の数は周期４で繰り返される。
a1 = 2 · 3 = 6
a2 = 4 · 7 = 28
a3 = 8 · 15 = 120 (15 は素数ではない)
a4 = 16 · 31 = 496
ここに、n = 4m + 3 のとき、
2n+1 − 1 = 24(m+1) − 1
(
)(
)(
)
= 2m+1 − 1 2m+1 + 1 22m+2 + 1
は素数にならない。よって、N の１位の数は６か８である。
-61-
63
第 8 章 連分数と不定方程式
入試問題から
a
a, b を互いに素な自然数とし、 はある自然数 a1 , a2 , a3 によって、
b
a
= a1 +
b
1
a2 +
1
a3
p1 p2
p1
p2
1
と表されている。 ,
は既約分数とし、
= a1 ,
= a1 +
であるとする。xy − zw
q1 q2
q1
q2
a2
x z を
と書くとき、
w y p p 2
1 (1) の値を求めよ。
q2 q1 a p +p p 3 2
1
2 (2) の値を求めよ。
a3 q2 + q1 q2 (3) a = a3 p2 + p1 , b = a3 q2 + q1 であることを示せ。
【1983 早稲田大学】
(1)
p2
q2
p1 a1 a2 + 1
=
q1 a2
a1 1 = (a1 a2 + 1) − a1 a2 = 1
(2)
a3 p2 + p1
a3 q2 + q1
p2 a3 p2 + a1
=
q2 a3 q2 + 1
a1 a2 + 1 a2
= (a3 p2 + a1 ) a2 − (a1 a2 + 1) (a3 q2 + 1)
= a3 p2 a2 + a1 a2 − a1 a2 a3 q2 − a1 a2 − a3 q2 − 1
= a2 a3 (a1 a2 + 1) − a1 a2 a3 a2 − a3 a2 − 1
= −1
第 8. 連分数と不定方程式
(3)
a
a3
a1 a3 a2 + a1 + a3
= a1 +
=
b
a3 a2 + 1
a3 a2 + 1
ここで、a3 a2 + 1, a3 は互いに素であり、a1 a3 a2 + a1 + a3 , a3 a2 + 1 は互いに素だから、
a = a1 a3 a2 + a1 + a3 = a3 (a1 a2 + 1) + a1
= a3 p2 + p1
b = a3 a2 + 1 = a3 q2 + q
有理数をこのように表すことを連分数展開と呼ぶ。これは Euclid の互除法 (No2。
pdf １次不定方程式を見よ）をもちいて表すことができる。a を b で割ったときの商を a1 、余りを
a3 とすると、
a = a1 b + a3 ⇔
a
a3
= a1 +
b
b
つぎに、b を a3 で割った商を a2 としたとき、余りが 1 になったとすると、
b = a3 a2 + 1 ⇔
b
1
= a2 +
a3
a3
この互除法より、a, b が互いに素であることがわかる。
これらから、連分数展開ができる。
a
a3
1
1
= a1 +
= a1 +
=
1
b
b
b
a2 +
a3
a3
a, b が互いに素であるとき、１次不定方程式 ax + by = 1 は整数解をもつ。このことを互除法で
示そう。a = a1 , b = a2 とし、互除法を繰り返すと、
a1 = a2 q1 + a3 (0 < a3 < a2 )
a2 = a3 q2 + a4 (0 < a4 < a3 )
a3 = a4 q3 + a5 (0 < a5 < a4 )
············
an−1 = an qn−1 + an+1 (0 < an+1 < an )
ここで {an } は単調減少の自然数の数列であるから、有限回の操作で余りが１になるはずである。
-64-
第 8. 連分数と不定方程式
そこで、an+1 = 1 とおくと、上の除法を分数形で表すと、
a1
a3
1
= q1 +
= q1 +
a2
a2
a2
a3
a2
a4
1
= q2 +
= q2 +
a3
a3
a3
a4
a3
a5
1
= q3 +
= q3 +
a4
a4
a4
a5
············
an+1
1
an−1
= qn−1 +
= qn−1 +
an
an
an
となる。これを順に代入していくと、
a1
= q1 +
a2
1
1
q2 +
a2
a3
= q1 +
1
1
q2 +
a3
a4
1
= q1 +
q2 +
q3 +
1
= · · · · · · = q1 +
1
q2 +
q3 +
1
..
. + qn−1 +
1
1
an
-65-
1
a4
a5
第 8. 連分数と不定方程式
【演習 20】
(1) α, β を互いに素な正の整数とする。
[ 1 ] αx − βy = 0 の整数解をすべて求めよ。
[2 ]
α
= a1 +
β
1
(a1 , a2 , a3 , a4 は正の整数)
1
a2 +
a3 +
1
a4
とかけるとする。
1
a1 +
a2 +
1
a3
を通分して得られる分子 a1 a2 a3 + a1 + a3 を p, 分母 a2 a3 + 1 を q とするとき、
αq − βp の値を求めよ。
(2) 157x − 68y = 3 の整数解をすべて求めよ。
【1993 早稲田大学】
(1) [ 1 ]
αβm = −βy
∴ y = −αm
αx − βy = 0 ⇔ αx = −βy
αx は β の倍数であるが、α, β を互いに素であるから、x が β の倍数である。
x = βm (m ∈ Z)
とおけて、
αβm = βy
∴ y = αm
[2 ]
α
= a1 +
β
1
a2 +
1
1
a4
(a1 , a2 , a3 , a4 は正の整数)
a3 +
-66-
第 8. 連分数と不定方程式
と書けることから、
α>β
であり、このとき、α を β で割って、
α = βa1 + r
α
r
1
⇔ = a1 + = a1 + β
β
β
r
となる。与えられた式と比べて、
β
1
= a2 +
r
a3 +
1
a4
そこで、β を r で割って、
β = rQ + r1
β
r1
1
⇔ =Q+
=Q+ r
r
r
r1
∴ a2 = Q, a3 +
1
r
=
a4
r1
r を r1 で割って、
r = Q0 r1 + r2
r
r2
⇔
= Q0 +
r1
r1
∴ Q0 = a3 ,
r2
1
=
r1
a4
以上から、

1
α = βa1 + r · · · · · · 




 β = ra2 + r1 · · · · · · 2
3
r = r1 a3 + r2 · · · · · · 



1
r

 2 =
4
······
r1
a4
1 ∼
3 より
Euclid の互除法によれば、a, b の最大公約数を (a, b) と表せば、
(α, β) = (β, r) = (r, r1 ) = (r1 , r2 )
4 より、
α, β は互いに素であったから、r1 , r2 も互いに素である。
a4 r2 = r1
であるが、(1) の結果を用いると、
a4 = mr1 , 1 = mr2
-67-
第 8. 連分数と不定方程式
となる正の整数が存在する。
∴ m = 1, r2 = 1, a4 = r1
3 に代入して、
この結果を
r = a4 a3 + 1
2 を用いて、a4 = r1 を消去する。
1 = r − a4 a3
= r − (β − ra2 ) a3
= r (1 + a2 a3 ) − βa3
2 を用いて、r を消去する。
1 = r − a4 a3
= r − (β − ra2 ) a3
= r (1 + a2 a3 ) − βa3
= (α − βa1 ) (1 + a2 a3 ) − βa3
= α (1 + a2 a3 ) − β (a1 a2 a3 + a1 + a3 )
= αq − βp
(2)
157
21
1
=2+
=2+
68
68
68
21
1
1
=2+
=2+
5
1
3+
3+
21
21
5
1
=2+
1
3+
1
4+
5
1 + 3 · 4 = 13, 2 · 3 · 4 + 2 + 4 = 30
より、
157 · 13 − 68 · 30 = 1
157 · 39 − 68 · 90 = 3
これより、
157x − 68y = 3
は
157 (x − 39) − 68 (y − 90) = 0
とかけて、157 と 68 は互いに素であるから、
x − 39 = 68n, y − 90 = 157n (n ∈ N)
∴ x = 39n + 68n, y = 90 + 157n
-68-