大学入試対策 [新課程対応]
COM PASS
整数有名問題集
第２版
数学的に深い背景を持つ問題を厳選！
実力アップに最適な内容の濃い５４問
本
書
の
構
成
本書の特長: 数学的に深い背景を持つ問題を厳選
大学入試では, 深い数学的背景を持つ問題が多数出題されている. 特に, 整数問題
について, この傾向は顕著である. この手の問題は, 一度解いておかないとなかなか
手のつけられないことが多いが, 思考力と洞察力の鍛錬にふさわしい良問が多い.
まず, 問題を解く動機がはっきりしているため, 知識や計算力が問われるだけの
問題より意義深い学習ができる. 本質的に重要な事柄に触れることで, 問題の着眼
点を見抜く力を養うことができるのである. さらに, 多くの関連事項を同時に学ぶ
ことができるため, 基本的な公式などの要点を確認するだけにとどまらず, 応用の
利くさまざまな考え方を身につけることができる.
このようなメリットを考慮して, 短期間でも効率良く実力アップができるような
コンパクトで網羅的な問題集を目指し, 数学的に内容の濃い問題を中心に質の高い
代表的な問題を厳選した. 融合問題や, 少し発展的な問題もバランスよく収録した.
凡例
問題
31 問
特に重要な内容を含む代表的な問題を取り上げた. 短期間
での学習用に, これらの問題のみを解いても一通りの学習
ができるようになっている.
補充
23 問
上記の問題で学んだ事項の理解を深めるのに役立つ関連
問題を取り上げた. 受験前に一度は解いておきたい独特の
方策 , 策 1 , · · ·
解答 , 解 1 解 2 , · · ·
発想が求められる問題を多く扱った.
解の方針や考え方, 着眼点, 問題を解くために必要な知識
を簡潔にまとめた. ヒントとして利用しても良い.
高校学習指導要領から見て標準的で自然な発想に基づく
簡潔な解答の一例を挙げた.
さまざまな観点から考える能力が養われるように, 別解を
できるだけ紹介した.
注
問題の内容や解答を補足するための注意事項や, 具体例,
背景 高校の履修範囲を超えた内容を含め, 問題の背景や, 問題
w参
解答の書き方に関するアドバイスなどを載せた.
に関連のある興味深い話題を紹介した.
関連問題のページを挙げた.
問題の認知度
• 有名: 重要な数学的背景を持つ. 出題頻度はさまざま.
• 典型: 出題頻度が比較的高く, 解法がよく知られている.
• 特殊: 出題頻度が比較的低く, 独特の発想が求められる.
問題の難易度
• 基本: 教科書の練習問題レベル, 大学入試の基本レベル
易
• 標準: 教科書の章末問題レベル, 大学入試の標準レベル
• 実戦: 教科書の研究課題レベル, 大学入試の実戦レベル
• 発展: 教科書の研究課題レベル, 大学入試の発展レベル
難
解答時間の目安
記述式の場合の解答時間の目安を 10 分単位で表示した.
• 小問の番号が (1), (2), ... の場合: 大問の解答時間
• 小問の番号が (a), (b), ... の場合: 小問の解答時間の最大値
小問の番号
• (1), (2), ... : 誘導問題
• (a), (b), ... : 小問の間に直接的な関係はない
数学用語
数学的背景を強調し, テーマを簡潔に表すために, 専門的な用語もいくつか紹介
した. 高校の範囲を超える用語には, 本文中に † 印を付けた.
3
目
倍
1.
数
次
と
約
数
1
倍数・約数
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
除法の定理
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
8
ユークリッドの互除法
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9
GCD と 1 次不定方程式 .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
10
素数の性質
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
12
合同式の性質 .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
14
フェルマーの小定理 .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
15
方 程 式 の 整 数 解
2.
1 変数 n 次方程式
不定方程式
17
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
20
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
21
分数型方程式 .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
24
ピタゴラス数 .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
26
ペル方程式
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
30
2 次曲線の有理点 .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
33
指数方程式
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
34
3.
.
.
.
進
n
法
35
倍数の判定法 .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
36
累乗数の下位 .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
38
循環小数
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
39
.
.
そ
4.
の
他
40
整数値をとる多項式 .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
42
ガウスの記号 .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
44
オイラーの関数
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
47
格子点
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
48
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
50
.
.
.
鳩の巣原理の応用
記号一覧表
51
問題一覧表
52
1
1.
倍
数
と
約
数
問題 1 (p. 3)
任意の正整数 n に対して, 32n−1 + 5n は 4 の倍数であることを示せ.
問題 2 (p. 5)
任意の整数 n に対して, n5 − n は 30 の倍数であることを示せ.
問題 3 (p. 6)
630 , 306 の正の公約数の総和 S を求めよ.
補充 1 (p. 6)
正整数 n の正の約数の個数を d(n) で表すとき,
(1) d(n) が奇数であるための必要十分条件を求めよ.
(2) d(n) が偶数である 100 以下の正整数 n の個数を求めよ.
問題 4 (p. 7)
0 < a ≦ b なる整数 a, b の最小公倍数 ℓ, 最大公約数 g について, 次の各条件
の下で a, b の値を求めよ:
(a) ℓ = 72, g = 6.
(b) a + b = 180, g = 18.
(c) ab = 2592, ℓ = 216.
問題 5 (p. 8)
任意の整数 a と正整数 b に対して, 次を満たす整数 q, r がただ 1 組存在する
ことを示せ:
1,
a = bq + r · · · ⃝
2.
0 ≦ r < b ···⃝
問題 6 (p. 9)
0 でない整数 a, b の最大公約数を (a, b) で表す.
(1) a を b で割った余りが r であるとき, 等式 (a, b) = (b, r) を示せ.
(2) (4123, 1729) の値を求めよ.
(3) (5n + 1, 4n + 2) = 3 であるような 100 以下の正整数 n の総数を求めよ.
問題 7 (p. 10)
a, b, g を正整数とし, 整数 k に対して ak を b で割った余りを rk で表す.
次のことを示せ:
(1) a, b が互いに素であるとき, 1 以上 b − 1 以下の任意の整数 i, j に対して,
ri = r j =⇒ i = j.
(2) g が a, b の最大公約数であるならば, ax + by = g の整数解が存在する.
2
補充 2 (p. 11)
整数全体の集合を Z で表す. a, b ∈ Z, ab , 0 として,
I = {ax + by|x, y ∈ Z}
とおく. 各整数 m に対して mZ = {mz|z ∈ Z} と定める. 次のことを示せ:
(1) k1 , k2 ∈ Z, n1 , n2 ∈ I =⇒ k1 n1 + k2 n2 ∈ I.
(2) I に属する最小の正整数を d とおくとき, I = dZ.
(3) a, b の最大公約数を g とおくとき, I = gZ.
問題 8 (p. 12)
a, b を整数, p を素数とする. 問題 7 (2) の結果を利用して, 次のことを示せ:
「ab が p の倍数である =⇒ a または b は p の倍数である」 · · · ⃝
*.
補充 3 (p. 12)
f (n) = n3 − 5n2 + 5n − 1 が素数となるような整数 n の値を求めよ.
問題 9 (p. 13)
n を正整数とする. 2n − 1 が素数ならば, n は素数であることを示せ.
補充 4 (p. 13)
n を正整数とする. n, n + 2, n + 4 が素数ならば, n = 3 であることを示せ.
問題 10 (p. 14)
(1) 任意の整数 a, b, a′ , b′ と正整数 m に対して, 次のことを示せ:
a ≡ a′ , b ≡ b′ (mod m) =⇒ a + b ≡ a′ + b′ (mod m).
(2) 次の漸化式で定まる数列 {an } について, 第 n 項 an が 10 の倍数である
ための n に関する必要十分条件を求めよ:
a1 = a2 = 1,
an+2 = an+1 + an .
問題 11 (p. 15)
a, b, a′ , b′ , c, m を整数とし, (2) 以降で a, a′ , c は素数 p と互いに素とする.
(1) a ≡ a′ , b ≡ b′ (mod m) =⇒ ab ≡ a′ b′ (mod m) を示せ.
(2) ca ≡ ca′ (mod p) =⇒ a ≡ a′ (mod p) を示せ.
(3)
p − 1 以下の正整数全体から成る集合を G とおき, k ∈ G なる各整数 k に
対して ka を p で割った余りを rk とおく. {rk |k ∈ G} = G を示せ.
(4) a p−1 ≡ 1 (mod p) を示せ.
補充 5 (p. 16)
p を素数とし, k を p − 1 以下の正整数とする. 次のことを示せ:
(1) k p Ck = p p−1 Ck−1 .
(2)
p Ck
は p の倍数である.
(3) 任意の整数 a に対して, a p − a は p の倍数である.
倍数と約数 > 倍数・約数
3
問題 1: 累乗和の倍数性 (典型, 基本, 20 分)
任意の正整数 n に対して, 32n−1 + 5n は 4 の倍数であることを示せ.
†
策 1 • 合同式 の性質を用いた方法が手っ取り早い. 整数 a, b を 0 でない
整数 m で割った余りが等しいとき, a, b は m を法として合同 † である
といい, a ≡ b (mod m) と表す.
• 明らかに,
a ≡ 0 (mod m) ⇐⇒ a は m の倍数.
• また, 整数 a′ , b′ と正整数 n に対して,
a ≡ a′ , b ≡ b′ (mod m) =⇒ a + b ≡ a′ + b′ , a n ≡ a′n (mod m).
w証明は, 問題 10 (1) と 11 (1) を参照.
• 累乗数を含む合同式の問題では, ±1 と合同な数, すなわち mq ± 1
(q :整数) の形に表される数が見つかれば計算が簡単になる.
解 1 3 ≡ −1, 5 ≡ 1 (mod 4) だから,
32n−1 + 5n ≡ (−1)2n−1 + 1n = −1 + 1 = 0 (mod 4).
ゆえに, 32n−1 + 5n は 4 の倍数である. 終 策 2 合同式と正の奇数 N に対して成り立つ次の恒等式を用いた別解もある:
N−1
∑
N
N
x + y = (x + y)
x N−1−k (−y) k .
解 2 5 ≡ 1 (mod 4) だから,
k=0
2n−2
∑
32n−1 +5n ≡ 32n−1 +1n = 32n−1 +12n−1 = (3+1)
32n−2−k (−1)k ≡ 0 (mod 4).
k=0
ゆえに, 32n−1 + 5n は 4 の倍数である. 終 ∑n
n−k k
n
策 3 • 二項定理 (x + y) = k=0 nC k x y を用いた別解もある.
• 32n−1 , 5n を 4 で割った余りは, (4 − 1)2n−1 , (4 + 1)n を二項定理で展開
したときの 4 で割り切れない項から求まる.
解 3 二項定理により,
2n−1
∑
2n−1
2n−1
2n−1−k
3
= (4 − 1)
=
(−1)k − 1,
2n−1 Ck 4
k=0
5n = (4 + 1)n =
n−1
∑
n−k
n Ck 4
+ 1.
k=0
よって,
32n−1 = 4d − 1,
5n = 4q + 1
なる整数 d, q が存在する. d + q は整数だから,
は 4 の倍数である. 終 32n−1 + 5n = 4(d + q)
倍数と約数 > 倍数・約数
4
策 4 • 数学的帰納法 (単に帰納法とも呼ぶ) による別解も可能である.
本問のように, 整数の性質の証明には帰納法が有効なことが多い.
• まず, n = 1 の場合を示す.
• 次に, n = k の場合を仮定して (帰納法の仮定と呼ぶ), n = k + 1 の場合
を示す. n = k + 1 の場合の式を帰納法の仮定が使えるように変形する
ことが証明の鍵となる.
2·1−1
+ 51 = 8 より, 32n−1 + 5n は 4 の倍数である.
解 4 ( i ) n = 1 のとき. 3
(ii) n = k のとき. 32k−1 + 5k が 4 の倍数であるとする. すなわち,
32k−1 + 5k = 4q
1
···⃝
なる整数 q の存在を仮定する. このとき,
32(k+1)−1 + 5k+1 = 9 · 32k−1 + 5 · 5k
= 9(32k−1 + 5k ) − 9 · 5k + 5 · 5k
= 9 · 4d − 4 · 5k = 4(9q − 5k ).
9q−5k は整数だから, n = k+1 のとき 32n−1 +5n は 4 の倍数である.
( i ), (ii) より, 任意の正整数 n に対し 32n−1 + 5n は 4 の倍数である. 終 注 (ii) では n を変数とみなし, その値を新しい文字 k で表した. しかし,
与えられた正整数 n に対して 32n−1 + 5n が 4 の倍数であると
する. すなわち 32n−1 + 5n = 4q なる整数 q の存在を仮定する.
このとき,
32(n+1)−1 + 5n+1 = 9 · 32n−1 + 5 · 5n
= 9(32n−1 + 5n ) − 9 · 5n + 5 · 5n
= 9 · 4q − 4 · 5n = 4(9q − 5n ).
9q − 5n は整数だから, 32(n+1)−1 + 5n+1 は 4 の倍数である.
のように n を与えられた値として扱う (n を固定するともいう) ことを
明記すれば, 新しい文字を導入する必要はない.
w参
以下, 文字の節約と解答の短縮のため, この方針に従う.
類題: 問題 23 (1).
倍数と約数 > 倍数・約数
5
問題 2: 多項式で表された整数 (有名, 基本, 20 分)
任意の整数 n に対して, n5 − n は 30 の倍数であることを示せ.
5
策 1 • n − n を因数分解する.
•「連続する r 個の整数の積は r! の倍数」を利用する.
解 1 • n を 5 で割った余りで場合に分け, n5 −n は 5 の倍数であることを示す.
n5 − n = n(n4 − 1) = n(n2 + 1)(n2 − 1)
= (n − 1)n(n + 1)(n2 + 1)
1
···⃝
であり, (n − 1)n(n + 1) は 3! = 6 の倍数だから, n5 − n は 6 の倍数である.
30 の因数 6, 5 は互いに素だから, n5 − n が 5 の倍数であることを示す.
1 のある因数が 5 の倍数である
n を 5 で割った余りで場合分けして, ⃝
ことを示す.
( i ) n = 5q (q: 整数) のとき. n は 5 の倍数である.
(ii) n = 5q ± 1 (q: 整数) のとき.
n ∓ 1 = (5q ± 1) ∓ 1 = 5q
は 5 の倍数である.
(iii) n = 5q ± 2 (q: 整数) のとき.
n2 + 1 = (5q ± 2)2 + 1 = 5(5q2 ± 4q + 1)
は 5 の倍数である.
( i )∼(iii) より, 題意が示された (以上, 複号同順). 終 †
策 2 本質的に解 1 と同じだが, 合同式 を使って議論を簡略化する.
解 2 ( i )∼(iii) の部分:
( i ) n ≡ 0 (mod 5) のとき. n は 5 の倍数である.
(ii) n ≡ ±1 (mod 5) のとき.
n ∓ 1 ≡ ±1 ∓ 1 = 0 (mod 5)
より, n ∓ 1 は 5 の倍数である.
(iii) n ≡ ±2 (mod 5) のとき.
n2 + 1 ≡ (±2)2 + 1 = 5 ≡ 0 (mod 5)
より, n2 + 1 は 5 の倍数である. 終 注 複号 ±, ∓ を使うことで, 解答を大幅に短縮できることがある.
(ii) の等式は n − 1 = (5q + 1) − 1 = 5q と n + 1 = (5q − 1) + 1 = 5q を
1 つにまとめたものである. この場合, 複号を含む等式からもとの等式
を読み解くためには, 符号をとる順番が重要になる. そこで, ± と ∓ を
併用し,「複号同順」であることを明記する.
†
背景 問題 11 (4), 補充問題 5 (3) で示すフェルマーの小定理 が背景にある.
倍数と約数 > 倍数・約数
6
問題 3: 約数の和 (典型, 標準, 10 分)
630 , 306 の正の公約数の総和 S を求めよ.
方策 • 整数 a, b の任意の公約数は, a, b の最大公約数 g の約数である.
• a = p1 α1 · · · pr αr , b = p1 β1 · · · pr βr (pk : 相異なる素数, αk , βk : 非負整数)
のとき, α k , β k の小さい方を γ k とおくと, g = p1 γ1 · · · pr γr .
• a = p1 e1 · · · pr er (pk : 相異なる素数, ek : 正整数) の正の約数は
S = (1 + p1 + · · · + p1 e1 ) · · · (1 + pr + · · · + pr er )
の展開式の項にもれなく現れるから, その総和は S .
• 次の等比数列の和の公式を用いる:
r , 1 =⇒ a + ar + · · · + ar n−1 =
a(r n − 1)
r−1
.
30
30
30
6
30
30
30
30
6
6
6
解答 6 = 2 · 3 , 30 = 2 · 3 · 5 より, 6 , 30 の最大公約数は, 2 · 3 .
よって, 630 , 306 の公約数は 26 · 36 の約数である.
そのうち正の約数の総和は,
S = (1 + 2 + · · · + 26 )(1 + 3 + · · · + 36 )
=
1(27 −1) 1(37 −1)
2187−1
·
= (128−1)
= 138811.
2−1
3−1
2
答 補充 1: 約数の個数 (典型, 標準, 20 分)
正整数 n の正の約数の個数を d(n) で表すとき,
(1) d(n) が奇数であるための必要十分条件を求めよ.
(2) d(n) が偶数である 100 以下の正整数 n の個数を求めよ.
e1
er
方策 n = p1 · · · pr (pk : 相異なる素数, ek : 正整数) の正の約数の個数は,
d(n) = (e1 + 1) · · · (e r + 1).
e1
er
解答 (1) n の素因数分解を n = p1 · · · pr (pk : 相異なる素数, ek : 正整数)
とする. n の正の約数は p1 i1 · · · pr ir (ik : 整数, 0 ≦ ik ≦ ek ) の形に表
され, 各指数 ik の指数について ek + 1 通りの取り方があるから,
d(n) = (e1 + 1) · · · (er + 1).
よって, d(n) が奇数であるための必要十分条件は, e1 + 1, · · · , er + 1
が奇数であること, すなわち e1 , · · · , er が偶数であること, つまり
a が平方数であることである.
(2) 100 以下の正整数 n うち d(n) が奇数であるものは, 平方数 1 = 12 ,
· · · , 102 = 100 で, ちょうど 10 個ある. ゆえに, 100 以下の正整数
n のうち d(n) が偶数であるものの総数は, 100 − 10 = 90. 答 背景 約数の個数, 約数の和は整数論で非常に重要なテーマである.
倍数と約数 > 倍数・約数
7
問題 4: 最小公倍数と最大公約数 (典型, 基本, 10 分)
0 < a ≦ b なる整数 a, b の最小公倍数 ℓ, 最大公約数 g について, 次の各条件
の下で a, b の値を求めよ:
(a) ℓ = 72, g = 6.
(b) a + b = 180, g = 18.
(c) ab = 2592, ℓ = 216.
′ ′
方策 • a, b の最大公約数が g であるとき, 互いに素な正整数 a , b を用いて
a = a′ g, b = b′ g
と書ける. このとき, a, b の最小公倍数は ℓ = a′ b′ g と書ける.
• 両辺に g を掛けると ℓ g = ab となる.
′ ′
解答 (a) g = 6 より, 互いに素な正整数 a , b を用いて
a = 6a′ , b = 6b′
と書ける. このとき, ℓ = 72 より,
6a′ b′ = 72.
∴ a′ b′ = 12.
また, a ≦ b より, a′ ≦ b′ . よって,
(a′ , b′ ) = (1, 12), (3, 4).
∴ (a, b) = (6, 72), (18, 24).
答 (b) g = 18 より, 互いに素な正整数 a′ , b′ を用いて
a = 18a′ ,
b = 18b′
と書ける. このとき, a + b = 180 より,
18(a′ + b′ ) = 180.
∴ a′ + b′ = 10.
a′ , b′ の選び方と大小関係に注意すると,
(a′ , b′ ) = (1, 9), (3, 7).
∴ (a, b) = (18, 162), (54, 126).
答 (c) ab = ℓg と条件より,
ab 2592
=
= 12.
ℓ
216
′ ′
よって, 互いに素な正整数 a , b を用いて
g=
a = 12a′ ,
b = 12b′
と書ける. このとき, ℓ = 216 より,
12a′ b′ = 216.
∴ a′ b′ = 18.
よって, a′ , b′ の選び方と大小関係に注意すると,
(a′ , b′ ) = (1, 18), (2, 9).
答 注 • 略記のために, 「ゆえに」を意味する記号 ∴ を使った.
∴ (a, b) = (12, 216), (24, 108).
•「なぜならば」を意味する記号 ∵ と混乱しないように注意.
倍数と約数 > 除法の定理
8
問題 5: 除法の定理 (有名, 実戦, 40 分)
任意の整数 a と正整数 b に対して, 次を満たす整数 q, r がただ 1 組存在する
1,
a = bq + r · · · ⃝
ことを示せ:
2.
0 ≦ r < b ···⃝
方策 • まず, a ≧ 0 の場合を帰納法で示す.
• 全段仮定の帰納法: a − b を b で割った余りは a に応じて様々な値を
とるから, 帰納法の仮定を a 未満のすべての非負整数に対して立てる.
1,⃝
2 を満たす整数 q, r の存在を示す.
解答 まず, ⃝
( I ) a ≧ 0 の場合. a に関する帰納法で示す.
1,⃝
2 が成り立つ.
( i ) a = 0 のとき. q = r = 0 に対して ⃝
1,⃝
2 を
(ii) a > 0 のとき. a 未満の任意の非負整数に対して ⃝
満たす整数 q, r の存在を仮定する.
1,⃝
2 が成り立つ.
• a < b のとき, q = 0, r = a に対して ⃝
• a ≧ b のとき. 0 ≦ a − b < a だから, 帰納法の仮定より
a − b = bq1 + r1 ,
0 ≦ r1 < b
を満たす整数 q1 , r1 が存在する. a = b(q1 + 1) + r1 だから,
1,⃝
2 が成り立つ.
q = q1 + 1, r = r1 に対して ⃝
1,⃝
2 を満たす整数 q, r が存在する.
( i ), (ii) より, a ≧ 0 のとき ⃝
(II) a < 0 の場合. −a > 0 と ( i ) より,
−a = bq2 + r2 ,
0 ≦ r2 < b
を満たす整数 q2 , r2 が存在する.
1,⃝
2 が成り立つ.
• r2 = 0 のとき, q = −q2 , r = 0 に対して ⃝
• r2 > 0 のとき, a = b(−q2 − 1) + (b − r2 ), 0 ≦ b − r2 < b だから,
1,⃝
2 が成り立つ.
q = −q2 − 1, r = b − r2 に対して ⃝
( I ), (II) より, すべての場合に q, r の存在が示された.
1,⃝
2 を満たす整数 q, r の一意性を示す. 上記の q, r に加えて,
次に, ⃝
′
1 ,
a = bq′ + r′ · · · ⃝
′
2
0 ≦ r′ < b · · · ⃝
を満たす整数 q′ , r′ の存在を仮定する.
′
⃝
1 −⃝
1 より b(q − q′ ) + (r − r′ ) = 0 となるから,
r − r′ = b(q′ − q).
′
2,⃝
2 より,
よって, r − r′ は b の倍数である. 一方, ⃝
−b < r − r′ < b.
したがって, r − r′ = 0 より, r = r′ .
これと bq + r = bq′ + r′ より bq = bq′ = 0 だから, q = q′ .
2 を満たす整数 q, r の一意性が示された. 終 1,⃝
以上より, ⃝
背景 これは, 除法の定理と呼ばれ, 整数論で最も基本的な定理の 1 つである.
倍数と約数 > ユークリッドの互除法
9
問題 6: ユークリッドの互除法 (有名, 標準, 30 分)
0 でない整数 a, b の最大公約数を (a, b) で表す.
(1) a を b で割った余りが r であるとき, 等式 (a, b) = (b, r) を示せ.
(2) (4123, 1729) の値を求めよ.
(3) (5n + 1, 4n + 2) = 3 であるような 100 以下の正整数 n の総数を求めよ.
方策 (1) a = bq + r (q: 整数) と表して, 最大公約数の最大性を用いる.
(2) 素因数分解が難しいので, 割り算を繰り返し行い, (1) を利用する.
この最大公約数の計算法をユークリッドの互除法 (単に互除法) と
呼ぶ.
(3) 多項式 f (x) を g(x) で割った余りが r(x) であり, g(n) , 0 である
とき, f (n) を g(n) で割った余りは r(n) だから, (1) が利用できる.
解答 (1) 除法の定理により, a = bq + r (q: 整数) と表せる.
( i ) a, b の公約数 (a, b) は r = a − bq の約数だから, b, r の公約数
である. よって, (b, r) の最大性により, (a, b) ≦ (b, r).
(ii) b, r の公約数 (b, r) は a = bq + r の約数だから, a, b の公約数
である. よって, (a, b) の最大性により, (a, b) ≧ (b, r).
( i ), (ii) より, (a, b) = (b, r).
(2)
4123 = 2 · 1729 + 665,
665 = 1 · 399 + 266,
1729 = 2 · 665 + 399,
399 = 1 · 266 + 133.
よって, (1) より,
(4123, 1729) = (1729, 665) = (665, 399)
= (399, 266) = (266, 133) = 133.
(3) ( i ) n = 1 のとき. 5n + 1 = 6, 4n + 2 = 6 の最大公約数は 6 , 3.
(ii) n が n ≧ 2 なる整数であるとき. 4n + 2 > 0, n − 1 > 0 であり,
5n + 1 = (4n + 2) · 1 + (n − 1),
4n + 2 = (n − 1) · 4 + 6.
よって, (1) より,
(5n + 1, 4n + 2) = (4n + 2, n − 1) = (n − 1, 6).
6 = 2 · 3 に注意すると, (5n + 1, 4n + 2) = 3 であるためには,
n − 1 が奇数かつ 3 の倍数であることが必要十分である.
2 ≦ n ≦ 100 のとき, 1 ≦ n − 1 ≦ 99. この範囲に 3 の倍数は
33 個, 6 の倍数は 16 個, 奇数である 3 の倍数は 17 個ある.
( i ), (ii) より, 求める個数は 17. 答 注 4123 = 7 · 19 · 31, 1729 = 7 · 13 · 19 より, (4123, 1729) = 7 · 19 = 133.
背景 互除法は, 紀元前に発見された最古のアルゴリズムとして有名であるが,
最大公約数を求める高速の計算法として現代でもよく利用されている.
倍数と約数 > GCD と 1 次不定方程式
10
問題 7: GCD と 1 次不定方程式 I (有名, 実戦, 20 分)
a, b, g を正整数とし, 整数 k に対して ak を b で割った余りを rk で表す.
次のことを示せ:
(1) a, b が互いに素であるとき, 1 以上 b − 1 以下の任意の整数 i, j に対して,
ri = r j =⇒ i = j.
(2) g が a, b の最大公約数であるならば, ax + by = g の整数解が存在する.
方策 • a, b の最大公約数が 1 であるとき, a, b は互いに素であるという.
(1) 「整数 a, a′ を b で割った余りが一致 ⇐⇒ a − a′ は b の倍数」を
利用する. i − j のとり得る値の範囲に注意する.
(2) 与式の両辺を g で割ることにより, g = 1 の場合に帰着させる.
ak を b で割った商を qk とおくと
ak + b(−qk ) = rk
となるから, rk = 1 を満たす整数 k の存在を示せば良い.
そのために, (1) の対偶を利用する.
解答 (1) ri = r j を仮定する. このとき, ia − ja = (i − j)a は b の倍数となる.
a, b は互いに素だから, i − j が b の倍数とならざるを得ない.
一方, 0 ≦ i ≦ b − 1, −(b − 1) ≦ − j ≦ 0 より,
−(b − 1) ≦ i − j ≦ b − 1.
よって, i − j = 0 より i = j となる.
(2) g が a, b の最大公約数であるとする.
方程式 ax + by = g の両辺を g で割ることにより, 問題は g = 1 の
場合, すなわち a, b が互いに素である場合に帰着する.
このとき, 整数 k に対して ak を b で割った商を qk とおくと,
ak = bqk + rk より
ak + b(−qk ) = rk
となる. よって, rk = 1 なる整数 k の存在を示せば良い.
(1) の対偶を考えると, 1 以上 b − 1 以下の任意の整数 i, j に対して
i , j =⇒ ri , r j
が成り立つから,
{r1 , · · · , rb−1 } = {1, · · · , b − 1}.
よって, rk = 1 なる整数 k が 1 以上 b − 1 以下の整数から見つかる.
題意が示された. 終 背景 関連問題 2 の結果から, (2) の逆も成り立つ. よって, ax + by = g の
整数解が存在するという条件は, 最大公約数の特徴付けを与える.
倍数と約数 > GCD と 1 次不定方程式
11
補充 2: GCD と 1 次不定方程式 II (有名, 発展, 30 分)
整数全体の集合を Z で表す. a, b ∈ Z, ab , 0 として,
I = {ax + by|x, y ∈ Z}
とおく. 各整数 m に対して mZ = {mz|z ∈ Z} と定める. 次のことを示せ:
(1) k1 , k2 ∈ Z, n1 , n2 ∈ I =⇒ k1 n1 + k2 n2 ∈ I.
(2) I に属する最小の正整数を d とおくとき, I = dZ.
(3) a, b の最大公約数を g とおくとき, I = gZ.
方策 (2) I ⊂ dZ を示すには, 除法の定理を用いる. つまり, I の要素を d で
割った余りが 0 であることを d の最小性から示す.
(3) I = gZ を示すには, dZ = gZ を示せば良い. gZ ⊂ dZ を示すには,
d が a, b の公約数であること, g の最大性を利用.
解答 (1) n j = ax j + by j (x j , y j ∈ Z, j ∈ {1, 2}) と表せるから,
k1 n1 + k2 n2 = k1 (ax1 + by1 ) + k2 (ax2 + by2 )
= a(k1 x1 + k2 x2 ) + b(k1 y1 + k2 y2 ) ∈ I.
(2) ( i ) d ∈ I だから, (1) より各整数 z に対して dz ∈ I. よって, dZ ⊂ I.
(ii) n ∈ I とする. 除法の定理により, n = dq+r (q, r ∈ Z, 0 ≦ r < d)
と表せる. このとき, (1) より
r = n − dq ∈ I.
d の最小性により r = 0 だから, n = dq ∈ dZ. よって, I ⊂ dZ.
( i ), (ii) より, I = dZ.
(3) ( i ) a = ga′ , b = gb′ , d = ax + by (a′ , b′ , x, y ∈ Z) と表すと,
各整数 z に対して
dz = (ga′ x + gb′ y)z = g(a′ x + b′ y)z ∈ gZ
となる. よって, dZ ⊂ gZ.
(ii) a = a · 1 + b · 0 ∈ I = dZ, b = a · 0 + b · 1 ∈ I = dZ より,
a, b は d の倍数である.
すなわち, d は a, b の公約数だから, g は d の倍数である.
よって, 各整数 z ∈ Z に対して gz は d の倍数だから, gz ∈ dZ.
したがって, gZ ⊂ dZ.
( i ), (ii) より, dZ = gZ. (2) の結果と合わせると, I = gZ. 終 †
背景 • (1) の性質を満たす集合 I は Z のイデアル と呼ばれる.
• (3) は, 問題 7 (2) の主張とその逆の集合論的な言い換えである.
• 初等整数論は, 本問のように集合論的に整理されている.
w参
そのため, 整数の集合の等式の証明問題がしばしば出題されている.
関連: 問題 13.
倍数と約数 > 素数の性質
12
問題 8: 素数の性質 (有名, 実戦, 20 分)
a, b を整数, p を素数とする. 問題 7 (2) の結果を利用して, 次のことを示せ:
「ab が p の倍数である =⇒ a または b は p の倍数である」 · · · ⃝
*.
方策 • 正整数 p が ±1 と ±p 以外の約数を持たないとき, p を素数と呼ぶ.
• ab が p の倍数であると仮定する. 「 A または B」は「 A でない =⇒ B」
と同値だから, a が p と互いに素な場合が問題なので, その場合に
問題 7 (2) の結果を適用する.
解答 ab が p の倍数であるとする.
( i ) a が p の倍数であるとき. 示すべきことは何もない.
(ii) a が p の倍数でないとき. p は素数だから, a, p の最大公約数は 1.
よって, 問題 7 (2) の結果より, ax + py = 1 を満たす整数 x, y が
存在する.
このとき, 仮定より abx + bpy = b は p の倍数となる.
( i ), (ii) より, ⃝
* が成り立つ. 終 * を満たす整数 p は素数に限る.
背景 上記の性質 ⃝
そのため, この性質は素数の特徴付けとして本質的に重要である.
補充 3: 多項式で表される素数 (典型, 基本, 20 分)
f (n) = n3 − 5n2 + 5n − 1 が素数となるような整数 n の値を求めよ.
方策 • 因数定理と組立除法を使って f (n) を因数分解する.
• 素数 p が p = ab (a, b: 正整数) と分解されるとき a, b のいずれかは
1 であることを使う.
解答 f (1) = 0 より, f (x) は x − 1 で割り切れる. 割り算を実行すると,
f (x) = (x − 1)(x2 − 4x + 1).
よって, f (n) が素数のとき,
| f (n)| = |n − 1||n2 − 4n + 1|
も素数だから, |n − 1|, |n2 − 4n + 1| のいずれかは 1 でなければならない.
∴ n − 1 = ±1 または
n2 − 4n + 1 = ±1.
( i ) n − 1 = 1 のとき. n = 2 であり, f (2) = 1 · (22 − 4 · 2 + 1) = −3.
(ii) n − 1 = −1 のとき. n = 0 であり, f (0) = 1.
(iii) n2 − 4n + 1 = 1 のとき. n(n − 4) = 0 より, n = 0, 4 であり, f (0) = 1,
f (4) = (4 − 1) · 1 = 3.
(iv) n2 − 4n + 1 = −1 のとき. n2 − 4n + 2 = 0 より, n = 2 ±
これは整数ではないので, 不適.
( i )∼(iv) より, 求める値は, n = 4. 答 √
2.
倍数と約数 > 素数の性質
13
問題 9: メルセンヌ素数 (有名, 標準, 20 分)
n を正整数とする. 2n − 1 が素数ならば, n は素数であることを示せ.
方策 •「 A =⇒ B」は「 B でない =⇒ A でない」と同値だから, 直接的な証明
が難しい命題は対偶を証明すれば良い (対偶法).
• 素数でない正整数は 1 または合成数である.
• ℓ > 1, m > 1 なる整数 ℓ, m の積 ℓm を合成数と呼ぶ.
n
解答 対偶を示すため, n を 1 または合成数として, 2 − 1 は 1 または合成数
であることを示す.
( i ) n = 1 のとき. 2n − 1 = 21 − 1 = 1.
(ii) n が合成数のとき. n = ℓm (ℓ, m: 整数, ℓ > 1, m > 1) と書けて
2n − 1 = 2ℓm − 1 = (2ℓ )m = (2ℓ − 1)(2ℓ(m−1) + · · · + 1),
2ℓ − 1 > 21 − 1 = 1,
2ℓ(m−1) + · · · + 1 ≦ 20 + 1 > 1
となるから, 2n − 1 は合成数である.
( i ), (ii) より対偶は真だから, 示すべき命題も真である. 終 n
†
背景 • 2 − 1 の形の素数をメルセンヌ素数 と呼ぶ.
• 素数が無限にあることは容易に証明できるが, n が素数でも 2n − 1 が
素数であるとは限らず, メルセンヌ素数が無限にあるか否かは未解決.
• 史上最大の素数は, メルセンヌ素数から発見されている.
補充 4: 公差 2 の「三つ子素数」 (有名, 基本, 20 分)
n を正整数とする. n, n + 2, n + 4 が素数ならば, n = 3 であることを示せ.
方策 • 対偶をとると見通し良く証明できる.
• n を 3 で割った余りで場合分けして示す.
解答 対偶を示すため, n , 3 として, n, n + 2, n + 4 の少なくとも 1 つは素数
でないことを示す.
( i ) n = 3d (d: 正整数) のとき. d ≧ 2 だから, n は素数でない.
(ii) n = 3d+1 (d: 非負整数) のとき. d = 0 ならば n = 1 は素数でなく,
d ≧ 1 ならば n + 2 = (3d + 1) + 2 = 3(d + 1) は素数でない.
(iii) n = 3d+2 (d: 非負整数) のとき. d = 0 ならば n+2 = 4 は素数でなく,
d ≧ 1 ならば n + 4 = (3d + 2) + 4 = 3(d + 2) は素数でない.
( i )∼(iii) より対偶は真だから, 示すべき命題も真である. 終 †
背景 • 差が 2 の素数の対, 双子素数 が無限にあるか否かは未解決.
• (p, p+2, p+4) の形の素数の 3 つ組は本問の通り (3, 5, 7) に限るから
三つ子素数と呼ばず, (p, p+2, p+6), (p, p+4, p+6) の形の素数の 3 つ
組を 三つ子素数 † と呼ぶ. 三つ子素数が無限にあるか否かも未解決.
倍数と約数 > 合同式の性質
14
問題 10: 数列の余りの周期性 (有名, 標準, 20 分)
(1) 任意の整数 a, b, a′ , b′ と正整数 m に対して, 次のことを示せ:
a ≡ a′ , b ≡ b′ (mod m) =⇒ a + b ≡ a′ + b′ (mod m).
(2) 次の漸化式で定まる数列 {an } について, 第 n 項 an が 10 の倍数である
ための n に関する必要十分条件を求めよ:
a1 = a2 = 1,
an+2 = an+1 + an .
†
方策 (1) 合同式 の定義に戻って示す.
(2) 10 = 2 · 5 より, an が 2, 5 の倍数であるための各条件を調べる.
小さい番号 n について an を 2, 5 で割った余りを具体的に計算
してみると, その周期性が見えてくる.
′
′
解答 (1) a = a + md, b = b + me (d, e: 整数) とおくと,
a + b = a′ + b′ + m(d + e) ≡ a′ + b′ (mod m).
(2) (1) より, 0 でない整数 m による割り算について, an の余りが rn で
あるとき an+2 = an+1 + an の余りは rn+1 + rn の余りに等しい.
• an を 2 で割った余りを xn とおくと
x1 = 1, x2 = 1, x3 = 0,
x4 = 1, x5 = 1, · · ·
となるから, 各正整数 m に対して
x3m−2 = x3m−1 = 1, x3m = 0
となる. よって,
an は 2 の倍数 ⇐⇒ xn = 0 ⇐⇒ n は 3 の倍数
1.
···⃝
• an を 5 で割った余りを yn とおくと
y1 = 1, y2 = 1, y3 = 2, y4 = 3, y5 = 0,
y6 = 1, y7 = 1, · · ·
となるから, 各正整数 m に対して
y5m−4 = y5m−3 = 1, y5m−2 = 2, y5m−1 = 3, y5m = 0
となる. よって,
an は 5 の倍数 ⇐⇒ yn = 0 ⇐⇒ n は 5 の倍数
2.
···⃝
⃝
1,⃝
2 より,
an は 10 の倍数 ⇐⇒ an は 2 の倍数かつ 5 の倍数
⇐⇒ n は 3 の倍数かつ 5 の倍数 ⇐⇒ n は 15 の倍数.
ゆえに, 求める条件は, n が 15 の倍数であること. 答 注 一般に,「和の余りは余りの和の余り」である.
†
背景 (2) の数列 {an } をフィボナッチ数列 と呼ぶ.
参 (1) の類題: 問題 11 (1).
w
倍数と約数 > フェルマーの小定理
15
問題 11: フェルマーの小定理 I (有名, 発展, 30 分)
a, b, a′ , b′ , c, m を整数とし, (2) 以降で a, a′ , c は素数 p と互いに素とする.
(1) a ≡ a′ , b ≡ b′ (mod m) =⇒ ab ≡ a′ b′ (mod m) を示せ.
(2) ca ≡ ca′ (mod p) =⇒ a ≡ a′ (mod p) を示せ.
(3)
p − 1 以下の正整数全体から成る集合を G とおき, k ∈ G なる各整数 k に
対して ka を p で割った余りを rk とおく. {rk |k ∈ G} = G を示せ.
(4) a p−1 ≡ 1 (mod p) を示せ.
†
方策 • (1), (2) は, 合同式 の定義に戻って示す.
• rk (k ∈ G) がどの値をとるかは複雑であるが, k を動かすと 1 から
p − 1 までのすべての値をとるという (3) が証明のポイントである.
′
′
解答 (1) a = a + md, b = b + me (d, e: 整数) とおくと,
ab = a′ b′ + m(db′ + a′ e + mde) ≡ a′ b′ (mod m).
(2) c が p と互いに素であることに注意すると, 合同式の定義により,
ca ≡ ca′ (modp) ⇐⇒ ca − ca′ は p の倍数
⇐⇒ c(a − a′ ) は p の倍数 ⇐⇒ a − a′ は p の倍数
⇐⇒ a ≡ a′ (mod p).
(3) i ∈ G, j ∈ G, i , j なる整数 i, j に対して, a は p と互いに素で
あるという仮定と i . j (mod p) から, (2) の対偶より, ia . ja
(mod p) が成り立ち, よって ri , r j が成り立つ.
これは {rk |k ∈ G} = G が成り立つことを意味する.
(4) k ∈ G なる全整数 k について ka ≡ rk (mod p) の辺々を掛けると,
(p − 1)!an−1 ≡ (p − 1)!
注
(mod p)
(∵ (1), (3)).
(p − 1)! は p と互いに素だから, (2) より, a
n−1
≡ 1 (mod p). 終 (1) より, ab を m で割った余りは a, b を m で割った余りの積の余りに
等しいことが分かる. つまり, 「積の余りは余りの積の余り」である.
†
背景 • (4) の定理をフェルマーの小定理 と呼ぶ.
• 素数を法とする合同式についても剰余の定理の存在が知られており,
それを用いるとフェルマーの小定理 † からウィルソンの定理 †
p は素数 ⇐⇒ (p − 1)! ≡ −1 (mod p)
···⃝
*
の (⇒) が導かれる. 実際, 多項式 f (x) = x p−1 − 1 について, k ∈ G の
とき f (k) ≡ 0 (mod p) が成り立つから, 剰余の定理により,
f (x) ≡ (x − 1) · · · {x − (p − 1)} (mod p).
これに x = 0 を代入すると, −1 ≡ (−1) p−1 (p − 1)! (mod p).
p ≧ 3 のとき, (−1) p−1 = 1 だから, ⃝
* が成り立つ.
p = 2 のときは, (2 − 1)! = 1 ≡ −1 (mod 2) より, ⃝
* が成り立つ.
倍数と約数 > フェルマーの小定理
16
補充 5: フェルマーの小定理 II (有名, 発展, 30 分)
p を素数とし, k を p − 1 以下の正整数とする. 次のことを示せ:
(1) k p Ck = p p−1 Ck−1 .
(2)
p Ck
は p の倍数である.
(3) 任意の整数 a に対して, a − a は p の倍数である.
p
方策 • (3) では, 誘導に従って, まず a > 0 の場合を帰納法で示す.
∑
帰納法の第二段階では, 二項定理 (x + y) n = nk=0 nC k x n−k y k を利用.
• p ≧ 3 のとき, p は奇数だから (−a) p − (−a) = −(a p − a) となり,
a < 0 の場合は a > 0 の場合に帰着する.
• p = 2 の場合は, また別個に考える.
解答 (1) 二項係数の定義により,
p!
p
(p − 1)!
k p Ck = k·
= k· ·
= p p−1 Ck−1 .
k!(p − k)!
k (k − 1)!{(p − 1) − (k − 1)}!
(2) (1) より, k p Ck は p の倍数である.
p は素数であり 1 ≦ k ≦ p − 1 だから, p, k は互いに素である.
よって, p Ck は p の倍数である.
(3) ( I ) a ≧ 0 のとき. a に関する帰納法で示す.
( i ) a = 0 のとき. 0 p − 0 = 0 より, a p −a は p の倍数である.
(ii) 与えられた非負整数 a に対して a p − a が p の倍数
であるとする. このとき, (2) より
p−1
∑
p
p−k
− (a + 1)
C
a
+
1
(a + 1) − (a + 1) = a +
p k
p
k=1
= (a − a) +
p
は p の倍数となる.
p−1
∑
p Ck a
p−k
k=1
( i ), (ii) より, a ≧ 0 のとき a p −a は p の倍数である.
(II) a < 0, p ≧ 3 のとき. p は奇数だから (−a) p − (−a) = −(a p − a)
であり, これは ( i ) より p の倍数である. よって, a p − a も p
の倍数である.
(III) p = 2 のとき. a2 − a = a(a − 1) は偶数だから, a p − a は p の
倍数である.
注
w参
( I )∼(III)より, 任意の整数 a に対し a p −a は p の倍数である. 終 p と互いに素な整数 a に対しては a p −a = a(a p−1 −1) が p の倍数である
ことと a p−1 − 1 が p の倍数であることは同値だから, (3) と前問の (4)
は同値である.
関連: 問題 2.
17
2.
方 程 式 の 整 数 解
問題 12 (p. 20)
n を 2 以上の整数, p を素数, d0 , · · · , dn−1 を整数とする.
多項式 f (x) = xn + pdn−1 xn−1 + · · · + pd1 x + pd0 について, 次のことを示せ:
(1)
f (x) = 0 が整数解 α を持つ =⇒ α は p で割り切れる.
(2) d0 が p で割り切れない =⇒ f (x) = 0 は整数解を持たない.
補充 6 (p. 20)
2 次以上の整数係数多項式 f (x) =
∑n
ak xk について, a0 , an が奇数である
∑
とする. f (x) = 0 は有理数解を持つならば, nk=0 ak は偶数であることを示せ.
k=0
問題 13 (p. 21)
次の方程式の整数解をすべて求めよ:
45x + 38y = 1
···⃝
*.
補充 7 (p. 22)
次の方程式, 連立方程式の整数解をすべて求めよ
:
(a) 3x + 5y + 7z = 1
···⃝
*.
1,
2x + 3y + 4z = 5 · · · ⃝
(b)
6x − 7y + 8z = −9 · · · ⃝
2.
問題 14 (p. 23)
p, q を p < q なる素数とする.
n = pq の正の約数の総和 σ(n) が 2n に等しいとき, n の値を求めよ.
補充 8 (p. 23)
和と積が等しい 3 個の正整数の組合せをすべて求めよ.
問題 15 (p. 24)
(1) 次の条件付き方程式の整数解をすべて求めよ:
1 1 1
1 , x ≧ y ≧ z > 0 ···⃝
2.
+ + = 1 ···⃝
x y z
1 の整数解の総数を求めよ.
(2) ⃝
補充 9 (p. 25)
1 の左辺の最大値を求めよ:
次の連立不等式の整数解について, ⃝
1 1 1
1,
+ + < 1 ···⃝
x y z
2.
x ≧ y ≧ z > 0 ···⃝
18
問題 16 (p. 26)
互いに素な整数 a, b, c が a2 + b2 = c2 を満たすとき, 次のことを示せ:
(1) a, b の偶奇は異なり, c は奇数である.
c+a
c−a
(2) a が奇数のとき, d =
,e=
は互いに素な平方数である.
2
2
(3) a が奇数のとき, a, b, c は互いに素なある整数 m, n を用いて次のように
表される:
a = m2 − n2 ,
b = 2mn,
c = m2 + n2 .
問題 17 (p. 27)
点 A(−1, 0) を通る傾き t の直線と原点中心の単位円の交点 P(x, y) について,
1−x
を t で表せ.
1+x
(2) x, y が有理数のとき, t は有理数であることを示せ.
(1) x, y,
(3) t が正の有理数のとき, x, y は互いに素なある正整数 m, n を用いて次の
ように表されることを示せ:
x=
m2 − n2
,
m2 + n2
y=
2mn
.
m2 + n2
補充 10 (p. 28)
3 辺の長さ a, b, c が整数である直角三角形において, θ を tan θ =
鋭角とする.
b
なる
a
1 − cos θ
θ
を t = tan で表せ.
1 + cos θ
2
(2) t は有理数であることを示せ.
(1) cos θ, sin θ,
(3) 3 辺の比は互いに素なある正整数 m, n を用いて次のように表されること
を示せ:
a : b : c = (m2 − n2 ) : 2mn : (m2 + n2 ).
問題 18 (p. 29)
整数 a, b, c が a2 + b2 = c2 を満たすとき, 次のことを示せ:
(a) a または b は 3 の倍数である.
(b) a または b は 4 の倍数である.
(c) a, b, c の少なくとも 1 つは 5 の倍数である.
19
問題 19 (p. 30)
(1) 各正整数 n に対して
√
√
(3 + 2 2)n = xn + yn 2
1
···⃝
を満たす整数 xn , yn の存在を証明し, xn+1 , yn+1 を xn , yn で表せ.
√
(2) 数列 {xn − yn 2} の一般項を求めよ.
(3) 各番号 n に対して, (x, y) = (xn , yn ) は次式の整数解であることを示せ:
x2 − 2y2 = 1
···⃝
*.
(4) ⃝
* を満たす正整数 x, y から定まる整数の組 (p, q) = (3x − 4y, −2x + 3y)
について, 次のことを示せ:
p2 − 2q2 = 1,
0 ≦ q < y.
(5) ⃝
* の任意の正の整数解は (3) のような形に表されることを示せ.
補充 11 (p. 32)
(1) (xu + dyv)2 − d(xv + yu)2 を因数分解せよ.
(2) u2 − 2v2 = 1 の整数解を 1 つ与えよ.
(3) x2 − 2y2 = −1 は無限個の整数解を持つことを示せ.
問題 20 (p. 33)
次のことを示せ:
(1) a, b を整数とする. a2 + b2 が 3 の倍数ならば, a, b は 3 の倍数である.
(2) x2 + y2 = 3 の有理数解は存在しない.
問題 21 (p. 34)
2 x + 1 = y2 の整数解をすべて求めよ.
補充 12 (p. 34)
2x
について, x ≧ 3 のとき, 不等式 f (x) < f (x + 1) を示せ.
x2
x
2
(2) 2 = x の整数解をすべて求めよ.
(1) 関数 f (x) =
方程式の整数解 > 1 変数 n 次方程式
20
問題 12: アイゼンシュタイン多項式 (有名, 標準, 20 分)
n を 2 以上の整数, p を素数, d0 , · · · , dn−1 を整数とする.
多項式 f (x) = xn + pdn−1 xn−1 + · · · + pd1 x + pd0 について, 次のことを示せ:
(1)
f (x) = 0 が整数解 α を持つ =⇒ α は p で割り切れる.
(2) d0 が p で割り切れない =⇒ f (x) = 0 は整数解を持たない.
方策 • f (α) = 0 を変形する.
解答 (1) α を f (x) = 0 の整数解とする. f (α) = 0 より,
αn = −p(dn−1 αn−1 + · · · + d0 ).
よって, αn は p で割り切れるから, α は p で割り切れる.
(2) 対偶を示すため, f (x) = 0 が整数解 α を持つとする.
このとき, (1) より, ある整数 q について α = pq となる.
f (α) = 0 より, pd0 = −p2 (pn−2 qn + dn−1 pn−2 qn−1 + · · · + d1 q).
n ≧ 2 に注意すると, pd0 は p2 で割り切れるから, d0 は p で割り
切れる. ゆえに, 対偶は真だから, 示すべき命題も真である. 終 †
背景 • 本問は, 次のアイゼンシュタインの既約判定法 を背景としている:
整数 an−1 , · · · , a0 が素数 p で割り切れ, a0 が p2 で割り切れないとき,
2 次以上の多項式 f (x) = xn + an−1 xn−1 + · · · + a0 は n 次未満の整数
係数多項式の積に分解できない (既約であるという).
• このとき, 特に f (x) は整数解を持たない. 本問ではこちらを示した.
補充 6: 整数係数方程式の有理数解 (典型, 標準, 20 分)
2 次以上の整数係数多項式 f (x) =
∑n
ak xk について, a0 , an が奇数である
∑
とする. f (x) = 0 は有理数解を持つならば, nk=0 ak は偶数であることを示せ.
k=0
∑n
k
方策 • 整数係数多項式 f (x) = k=0 ak x (an , 0) について, f (x) = 0 の
有理数解 α は a0 の約数 d, an の約数 e を用いて α = de−1 と表せる.
1 を活用する.
• f (α) = 0 の分母を払って得られる式 ⃝
−1
解答 α = de (d, e: 互いに素な整数, e , 0) を f (x) = 0 の有理数解とする.
f (α) = 0 より, an dn e−n + an−1 dn−1 e1−n + · · · + a1 de−1 + a0 = 0.
1.
両辺に en を掛けると, an dn + an−1 dn−1 e + · · · + a1 den−1 + a0 en = 0 · · · ⃝
an dn = −e(an−1 dn−1 + · · · + a0 en−1 ),
a0 en = −d(an dn−1 + · · · + a1 en−1 )
と d, e の取り方より, d, e はそれぞれ a0 , an の約数である.
1 の左辺の各項の偶奇は
a0 , an は奇数だから d, e も奇数なので, ⃝
1 の右辺は偶数である.
an , · · · , a1 , a0 の偶奇に一致する. 一方, ⃝
∑n
ゆえに, k=0 ak は偶数である. 終 方程式の整数解 > 不定方程式
21
問題 13: 2 変数 1 次不定方程式 (典型, 標準, 20 分)
次の方程式の整数解をすべて求めよ:
···⃝
*.
45x + 38y = 1
方策 • 整数係数 2 変数 1 次不定方程式
ax + by = c · · · [♡]
が 1 つの整数解 (x, y) = (x0 , y0 ) を持つとき, 任意の整数解は, [♡]
から ax0 + by0 = 1 の辺々を引いて得られる a(x − x0 ) = −b(y − y0 ) を
満たすから, この値を abn (n: 整数) とおくと, 次のようになる:
(x, y) = (x0 + bn, y0 + an).
• よって, [♡] の整数解を何でも良いので 1 つ求めることが問題になる.
5x + 3y = 1 の解 (x, y) = (2, −3) のように試行錯誤で簡単に見つかる
w問題 6) の計算を
場合もあるが, 本問では難しい. そこで, 互除法 (
解答 利用して [♡] の整数解の 1 つを求める.
45 = 38 + 7
1,
···⃝
38 = 7 · 5 + 3
2,
···⃝
7=3·2+1
3
···⃝
より,
1=7−3·2
3)
(∵ ⃝
2)
= 7 − (38 − 7 · 5) · 2 (∵ ⃝
= 7 · 11 − 38 · 2
1)
= (45 − 28) · 11 − 38 · 2 (∵ ⃝
= 45 · 11 + 38 · (−13)
4.
···⃝
⃝
4 より,
* −⃝
45(x − 11) + 38(y + 13) = 0.
よって, 45, 38 が互いに素であることに注意すると, ⃝
* の整数解 (x, y)
が与えられれば
45(x − 11) = −38(y + 13) = 45 · 38n
5
···⃝
を満たす整数 n が定まる.
5 を満たす整数 n が与えられれば, ⃝
逆に, ⃝
* の整数解 (x, y) が定まる.
ゆえに, ⃝
* の整数解は,
(x, y) = (38n + 11, −45n − 13) (n: 任意の整数).
答 方程式の整数解 > 不定方程式
注
22
1 − 5y 1 − y
=
− 2y と −2y が整数である
2
2
ことから 1 − y = 2n とおくと, 次のように求まる:
• 2x + 5y = 1 の整数解は, x =
y = 1 − 2n,
x = n − 2y = n − 2(1 − 2n) = 5n − 2 (n: 任意の整数).
• a, b のうち絶対値の小さい方で割るというこの解法は, 本問のように
w参
うまくいかない場合もあるので注意されたい.
ax + by = c が整数解を持つための条件: 問題 7, 補充問題 2.
補充 7: 3 変数 1 次不定方程式 (典型, 実戦, 20 分)
次の方程式, 連立方程式の整数解をすべて求めよ
:
···⃝
*.
(a) 3x + 5y + 7z = 1
1,
2x + 3y + 4z = 5 · · · ⃝
(b)
6x − 7y + 8z = −9 · · · ⃝
2.
方針 (a) 問題 13 の「注」で述べた 2 変数 1 次方程式の解法をまねて, まず
係数が小さい変数について解く.
(b) まず 1 文字消去して, 2 変数の場合を解く.
* を満たすとする. ⃝
* より,
解答 (a) 整数 x, y, z が ⃝
1 − 5y − 7z 1 − 2y − z
x=
=
− y − 2z
3
3
1 − 2y − z
と −y − 2z は整数だから,
も整数である.
3
そこで, 1 − 2y − z = 3m, y = n とおくと,
z = 1 − 3m − 2n,
x = m − n − 2(1 − 3m − 2n) = 7m + 3n − 2.
ゆえに, ⃝
* の整数解は,
(x, y, z) = (7m+3n−2, n, 1−3m−2n) (m, n: 任意の整数).
答 1,⃝
2 を満たすとする. (−2) × ⃝
1 +⃝
2 より,
(b) 整数 x, y, z が ⃝
2x − 13y = −19.
よって,
13y − 19 y − 1
=
+ 6y − 9
2
2
y−1
と 6y − 9 は整数だから,
も整数である.
2
そこで, y − 1 = 2n とおくと,
x=
y = 2n + 1,
x = n + 6(2n + 1) − 9 = 13n − 3.
1 より,
したがって, ⃝
5−2x−3y 5−2(13n−3)−3(2n+1)
=
= 2−8n.
4
4
1,⃝
2 の整数解は,
ゆえに, ⃝
z=
(x, y, z) = (13n − 3, 2n + 1, 2 − 8n) (n: 任意の整数).
答 方程式の整数解 > 不定方程式
23
問題 14: 2 変数 2 次不定方程式 (有名, 基本, 20 分)
p, q を p < q なる素数とする.
n = pq の正の約数の総和 σ(n) が 2n に等しいとき, n の値を求めよ.
方策 • σ(n) を書き下すと, 2 次方程式 pq − p − q − 1 = 0 の整数解を求める
問題に帰着できる.
• このタイプの方程式は, (ax + by)(cx + dy) = e の形に変形できれば,
素因数分解から整数解が求められる.
解答 n = pq の正の約数は 1, p, q, pq で尽くされるから,
σ(n) = 1 + p + q + pq.
2n = σ(n) より,
2pq = 1 + p + q + pq.
整理すると pq − p − q + 1 = 2 となるから,
(p − 1)(q − 1) = 2.
2 ≦ p < q より 1 ≦ p − 1 < q − 1 であることに注意すると,
(p − 1, q − 1) = (1, 2).
ゆえに, n = pq = 6. 答 ∴ (p, q) = (2, 3).
†
背景 • σ(n) = 2n なる正整数を完全数 と呼ぶ.
• 奇数の完全数はまだ発見されていない.
• 完全数が無限に存在するかどうかは未解決である.
補充 8: 対称な高次不定方程式 (典型, 標準, 20 分)
和と積が等しい 3 個の正整数の組合せをすべて求めよ.
方策 • x + y + z = xyz の正の整数解の組合せを求める. このままでは手を
付けにくいが, 両辺は x, y, z に関して対称であることに着目し, 条件
x ≦ y ≦ z を付加して考えると, x, y, z の値の範囲を絞り込める.
解答 • 1 ≦ xy ≦ 3 より, xy の値で場合分けして解を決定する.
x + y + z = xyz
1,
···⃝
x≦y≦z
2
···⃝
1,⃝
2 より,
の正整数解 x, y, z を求めれば良い. ⃝
xyz = x + y + z ≦ z + z + z = 3z.
∴ 1 ≦ xy ≦ 3.
( i ) xy = 1 のとき. x = y = 1 より x+y+z = z+2 , z = xyz だから不適.
1 は z + 3 = 2z と同値であり,
(ii) xy = 2 のとき. x = 1, y = 2 より, ⃝
2 を満たす.
その解は z = 3. これは ⃝
1 は z + 4 = 3z と同値であり,
(iii) xy = 3 のとき. x = 1, y = 3 より, ⃝
2 を満たさない.
その解は z = 2 だが, ⃝
( i )∼(iii) より, 求める解は 1, 2, 3. 答 方程式の整数解 > 分数型方程式
24
問題 15: 対称な分数型方程式 (典型, 発展, 20 分)
(1) 次の条件付き方程式の整数解をすべて求めよ:
1 1 1
1 , x ≧ y ≧ z > 0 ···⃝
2.
+ + = 1 ···⃝
x y z
1 の整数解の総数を求めよ.
(2) ⃝
2 は⃝
1 の解の組合せを一意的に表すための付加的な条件だが, x, y, z
方策 ⃝
の取りうる値の範囲の絞り込みに利用できる.
1,⃝
2 を満たすとする. このとき,
解答 (1) 整数 x, y, z が ⃝
1 1 1
3
≦ ≦
···⃝
x y
z
より,
1 1 1 1 1 1 3
1 = + + ≦ + + = . ∴ z ≦ 3.
x y z
z z z
z
( I ) x > 0, y > 0 より
1 1
+ >0
x y
だから, z , 1. z = 1 は不適.
3 より
1,⃝
(II) z = 2 のとき. ⃝
1 1 1 1 1 2
= + ≦ + =
2 x y y y y
だから, 2 = z ≦ y ≦ 4.
1
( i ) x > 0 より > 0 だから, y , 2. y = 2 は不適.
x
1 1
1 は = となるから, x = 6.
(ii) y = 3 のとき. ⃝
x 6
1 1
1 は = となるから, x = 4.
(iii) y = 4 のとき. ⃝
x 4
3 より
1,⃝
(III) z = 3 のとき. ⃝
だから, y ≦ 3.
2 1 1 1 1 2
= + ≦ + =
3 x y y y y
これと y ≧ z = 3 より, y = 3.
1 1
= より, x = 3.
x 3
2 の整数解は,
1,⃝
( I )∼(III)より, ⃝
このとき,
(x, y, z) = (6, 3, 2), (4, 4, 2), (3, 3, 3).
2 の仮定を取り除くと, ⃝
1 を満たす正整数の組 (x, y, z) は,
(2) ⃝
(6, 3, 2) から 3! 組, (4, 4, 2) から 3 通り, (3, 3, 3) から 1 組
得られるから, その総数は
3! + 3 + 1 = 10.
答 方程式の整数解 > 分数型方程式
25
補充 9: 対称な分数型不等式 (典型, 発展, 30 分)
1 の左辺の最大値を求めよ:
次の連立不等式の整数解について, ⃝
1 1 1
1,
+ + < 1 ···⃝
x y z
2.
x ≧ y ≧ z > 0 ···⃝
1 1 1 3
方策 問題 15 と同様に 1 > x + y + z ≦ z としても, z の範囲を絞り込むこと
1 1 1
1,⃝
2 の下で + + の最大値を z の小さい方から
ができないので, ⃝
x y z
調べてみる.
1 1 1
1,⃝
2 を満たすとし, S = + + とおく.
解答 整数 x, y, z が ⃝
x y z
1 1
( I ) x > 0, y > 0 より + > 0 だから, z = 1 は不適.
x y
1 より
(II) z = 2 のとき. ⃝
1 1 1 1
< + <
y
x y 2
だから, y > 2 すなわち y ≧ 3.
1 1
( i ) y = 3 のとき. < だから, x > 6 すなわち x ≧ 7. よって,
x 6
1 1 1 41
S ≦ + + =
.
7 3 2 42
1 1
(ii) y = 4 のとき. < だから, x > 4 すなわち x ≧ 5. よって,
x 4
1 4 1 19
S ≦ + + =
.
5 3 2 20
(iii) y ≧ 5 のとき. x ≧ y ≧ 5 より,
1 1 1
9
S ≦ + + =
.
5 5 2 10
2 より, y ≧ x = 3.
(III) z = 3 のとき. ⃝
1 1
(iv) y = 3 のとき. < だから, x > 3 すなわち x ≧ 4. よって,
x 3
1 1 1 11
S ≦ + + =
.
4 3 3 12
( v ) y ≧ 4 のとき. x ≧ y ≧ 4 より,
1 1 1 5
S ≦ + + = .
4 4 3 6
(IV) z ≧ 4 のとき. x ≧ y ≧ z ≧ 4 より,
1 1 1 3
S ≦ + + = .
4 4 4 4
各場合の S の最大値を比較すると
9
19 41
5 11 41
3 41
<
<
,
<
<
,
<
.
10 20 42
6 12 42
4 42
41
1 1 1
をとる. 答 ゆえに, + + は (x, y, z) = (2, 3, 7) のとき最大値
x y z
42
方程式の整数解 > ピタゴラス数
26
問題 16: 原始ピタゴラス数 I (有名, 実戦, 30 分)
互いに素な整数 a, b, c が a2 + b2 = c2 を満たすとき, 次のことを示せ:
(1) a, b の偶奇は異なり, c は奇数である.
c−a
c+a
(2) a が奇数のとき, d =
,e=
は互いに素な平方数である.
2
2
(3) a が奇数のとき, a, b, c は互いに素なある整数 m, n を用いて次のように
表される:
a = m2 − n2 ,
b = 2mn,
c = m2 + n2 .
方策 (1) 背理法で示す.
(2) 平方数の素因数分解における指数は偶数であることをうまく使う.
2
2
2
解答 (1) ( i ) 仮に a, b が偶数であるとすると, a + b = c は偶数となり,
c は偶数となって, a, b, c が互いに素であることに反する.
(ii) 仮に a, b が奇数であるとする. 4 で割るとき, 奇数の平方
(2q + 1)2 = 4(q2 + q) + 1 (q : 整数)
の余りは 1 だから, a2 + b2 の余りは 1 + 1 = 2.
よって, a2 + b2 が 2 で割り切れる回数は奇数だから, a2 + b2
は平方数でない. これは a2 + b2 = c2 に反する.
( i ), (ii) より, a, b の偶奇は異なる. よって, a2 , b2 の偶奇は異な
り, a2 + b2 = c2 は奇数だから, c は奇数である.
(2) c2 − a2 = b2 より,
( )2
c + a c − a c2 − a2 b2
b
de =
·
=
= 2 =
.
2
2
2
2
2
2
d, e の公約数は, d + e = a, d − e = c の公約数となるから, a, c の
取り方より ±1 に限る.
つまり, d, e は互いに素である. 以上より, d, e は平方数である.
仮にそうでなければ, d, e の素因数分解における指数が奇数である
ような素因数が公約数となってしまうからである.
(3) (2) より, 互いに素なある正整数 m, n に対して
c+a
c−a
d=
= m2 , e =
= n2
2
2
となる. このとき, a = m2 − n2 , c = m2 − n2 .
b2
= m2 n2 より, b > 0 であることに注意すると, b = 2mn. 終 4
2
•
a
+
b2 = c2 の正の整数解 (a, b, c) をピタゴラス数 † と呼ぶ.
背景
• a, b, c が互いに素なピタゴラス数 (a, b, c) は 原始的 † であるという.
• ピタゴラス数 (a, b, c) について, a, b, c の最大公約数を g とおき,
a = ga′ , b = gb′ , c = gc′ (a′ , b′ , c′ : 互いに素な整数) と表すと,
a2 + b2 = c2 の両辺を g2 で割ることにより a′2 + b′2 = c′2 が得られる
ので, (a′ , b′ , c′ ) は原始ピタゴラス数になる.
方程式の整数解 > ピタゴラス数
27
問題 17: 原始ピタゴラス数 II (有名, 実戦, 30 分)
点 A(−1, 0) を通る傾き t の直線と原点中心の単位円の交点 P(x, y) について,
1−x
を t で表せ.
1+x
(2) x, y が有理数のとき, t は有理数であることを示せ.
(1) x, y,
(3) t が正の有理数のとき, x, y は互いに素なある正整数 m, n を用いて次の
ように表されることを示せ:
x=
m2 − n2
,
m2 + n2
y=
2mn
.
m2 + n2
解答 (1) 点 A(−1, 0) を通る傾き t の直線の方程式は,
1.
y = t(x + 1) · · · ⃝
原点を中心とする単位円の方程式は,
x +y =1
2
2
y
1
P(x, y)
2.
···⃝
点 P(x, y) はこれらの交点だから,
A(−1, 0)
O
1
⃝
1 を⃝
2 に代入すると,
(1 + t2 )x2 + 2t2 x + (t2 − 1) = 0.
−1
x の他に −1 もこの方程式の解だから, 解と係数の関係により
2t2
x−1=−
.
1 + t2
よって,
2t2
1 − t2
3,
x=1−
=
···⃝
1 + t2 1 + t2
(
)
1 − t2
2t
4,
y=t
+1 =
···⃝
2
1+t
1 + t2
1 − x (1 + t2 ) − (1 − t2 )
5.
= t2 · · · ⃝
=
1 + x (1 + t2 ) + (1 − t2 )
5 より t2 は有理数である.
(2) 仮定より x は有理数だから, ⃝
1 + t2
4 より t =
さらに, y も有理数だから, ⃝
y も有理数である.
2
n
3,⃝
4 より
(3) 互いに素な正整数 m, n を用いて t = とおくと, ⃝
m
2mn
m2 − n2
, y= 2
x= 2
2
m
+
n
m
+ n2
と表せる. 終 †
背景 • 曲線 C 上の各座標が有理数である点を C の有理点 と呼ぶ.
• 一般に, 2 次曲線 C が有理点 P を持てば, 点 P を通る傾きが有理数の
直線と C の交点をとることによって, 無限個の有理点を構成できる.
これは, 3 次以上の曲線には一般化できない.
x
方程式の整数解 > ピタゴラス数
28
補充 10: 原始ピタゴラス数 III (有名, 発展, 30 分)
3 辺の長さ a, b, c が整数である直角三角形において, θ を tan θ =
鋭角とする.
b
なる
a
1 − cos θ
θ
を t = tan で表せ.
1 + cos θ
2
(2) t は有理数であることを示せ.
(1) cos θ, sin θ,
(3) 3 辺の比は互いに素なある正整数 m, n を用いて次のように表されること
を示せ:
a : b : c = (m2 − n2 ) : 2mn : (m2 + n2 ).
2
2
2
2
方策 (1) 三角比の相互関係 cos α + sin α = 1, 1 + tan α = 1/ cos α,
2 tan α
倍角の公式 tan 2α =
を利用.
1 − tan2 α
2t
解答 (1) 倍角の公式より tan θ = 1 − t2 だから,
(
)2
1
(1−t2 )2
1−t2
2
cos θ =
=
,
=
1+t2
1+tan2 θ (1−t2 )2 +(2t)2
(
)2
(1+t2 )2 −(1−t2 )2
2t
2
2
sin θ = 1−cos θ =
=
.
(1+t2 )2
1+t2
0◦ < θ < 90◦ より cos θ > 0, sin θ > 0, 0 < t < 1 だから,
1 − t2
2t
1,
cos θ =
, sin θ =
···⃝
2
1+t
1 + t2
1 − cos θ (1 + t2 ) − (1 − t2 )
2.
=
= t2 · · · ⃝
1 + cos θ (1 + t2 ) + (1 − t2 )
(2) 問題 17 (2) と同様.
n
(3) (2) より, 互いに素な正整数 m, n を用いて t = とおくと,
m
a
m2 − n2
b
2mn
c
= cos θ = 2
,
= sin θ = 2
b
c
c
m + n2
m + n2
となるから,
θ
a : b : c = (m2 − n2 ) : 2mn : (m2 + n2 ).
終 a
背景 ピタゴラス数は, 古くから直角の計測に用いられるなど, 生活に役立て
られてきた. 円を描くのにも便利である. 問題 16, 17 と本問で示した
公式から得られる原始ピタゴラス数を小さい順に 10 個まとめておく.
w参
m
2
3
4
4
5
n
1
2
1
3
2
a
3
5
15
7
21
b
4
12
8
24
20
ピタゴラス数の性質: 問題 18.
c
5
13
17
25
29
m
6
5
7
6
7
n
1
4
2
5
4
a
35
9
45
11
33
b
12
40
28
60
56
c
37
41
53
61
65
方程式の整数解 > ピタゴラス数
29
問題 18: ピタゴラス数の性質 (有名, 実戦, 20 分)
整数 a, b, c が a2 + b2 = c2 を満たすとき, 次のことを示せ:
(a) a または b は 3 の倍数である.
(b) a または b は 4 の倍数である.
(c) a, b, c の少なくとも 1 つは 5 の倍数である.
2
2
2
方策 • 整数 m, n について, n , m + n を 3, 4, 5 で割った余りは限られた値
しか取らないことに着目する.
• 背理法や間接証明法をうまく利用する.
2
2
解答 (a) a, b が 3 の倍数でないとして, a +b が平方数でないことを示せば
良い. 任意の整数 n に対して,
n ≡ ±1
(mod 3) =⇒ n2 ≡ 1 (mod 3)
1.
···⃝
よって, a2 ≡ b2 ≡ 1 (mod 3) だから,
2.
···⃝
a2 + b2 ≡ 1 + 1 = 2 (mod 3)
1 より,
n ≡ 0 (mod 3) =⇒ n2 ≡ 0 (mod 3) と ⃝
3.
(mod 3) · · · ⃝
⃝
3 より, a + b は平方数でない. 終 2,⃝
(b) a, b が 4 の倍数でないとして, a2 +b2 が平方数でないことを示せば
整数 N が平方数 =⇒ N ≡ 0, 1
2
2
良い. 任意の整数 q に対して,
(2q + 1)2 = 4q(q + 1) + 1 を 4, 8 で割った余りは 1.
(4q + 2)2 = 16q(q + 1) + 4 を 8, 16 で割った余りは 1.
( i ) a, b が奇数のとき. a2 + b2 ≡ 1 + 1 = 2 (mod 4).
a2 + b2 は, 2 で 1 回しか割り切れないから, 平方数でない.
(ii) a, b の一方のみが奇数のとき. a2 + b2 ≡ 1 + 4 = 5 (mod 8).
(平方数) ≡ 0, 1, 4 (mod 8) だから, a2 + b2 は平方数でない.
(iii) a, b が 4 の倍数でない偶数のとき. a2 +b2 ≡ 4+4 = 8 (mod 16).
a2 +b2 は, 2 で 3 回しか割り切れないから, 平方数でない. 終 (c) a, b が 5 の倍数でないとして, a2 + b2 が平方数ならば a2 + b2 は
5 の倍数であることを示せば良い. 任意の整数 n に対して,
n ≡ ±1, ±2 (mod 5) =⇒ n2 ≡ ±1 (mod 5)
1.
···⃝
よって, a ≡ ±1 (mod 5), b ≡ ±1 (mod 5) だから,
2
2
a2 + b2 ≡ 0, ±2
(mod 5)
2.
···⃝
1 より,
n ≡ 0 (mod 5) =⇒ n2 ≡ 0 (mod 5) と ⃝
整数 N が平方数 =⇒ N ≡ 0, ±1 (mod 5)
w
3.
···⃝
⃝
3 より, a2 +b2 が平方数ならば a2 +b2 は 5 の倍数である. 終 2,⃝
参 すべてのピタゴラス数を求める方法: 問題 16, 17, 補充問題 10.
方程式の整数解 > ペル方程式
30
問題 19: ペル方程式 I (有名, 発展, 40 分)
(1) 各正整数 n に対して
√
√
(3 + 2 2)n = xn + yn 2
1
···⃝
を満たす整数 xn , yn の存在を証明し, xn+1 , yn+1 を xn , yn で表せ.
√
(2) 数列 {xn − yn 2} の一般項を求めよ.
(3) 各番号 n に対して, (x, y) = (xn , yn ) は次式の整数解であることを示せ:
···⃝
*.
x2 − 2y2 = 1
(4) ⃝
* を満たす正整数 x, y から定まる整数の組 (p, q) = (3x − 4y, −2x + 3y)
について, 次のことを示せ:
p2 − 2q2 = 1,
0 ≦ q < y.
(5) ⃝
* の任意の正の整数解は (3) のような形に表されることを示せ.
方策 (1) 帰納法で示す.
√
(2) (1) の結果を用いて, xn+1 − yn+1 2 を変形する.
√
√
(3) x2 − dy2 = (x + y d)(x − y d) がポイント.
(5) (4) をヒントに, y 座標が単調減少になるような ⃝
* の整数解の
連立漸化式を立てる.
1 を満たす整数 xn , yn が x1 = 3, y1 = 2
解答 (1) ( i ) n = 1 のとき. ⃝
として確かに存在する.
1 を満たす整数 xn , yn の存在
(ii) 与えられた正整数 n に対して, ⃝
を仮定する. このとき,
√
√
√
(3 + 2 2)n+1 = (3 + 2 2)n (3 + 2 2)
√
√
= (xn + yn 2)(3 + 2 2)
√
= (3xn + 4yn ) + (2xn + 3yn ) 2.
√
√
よって, (3 + 2 2)n+1 = xn+1 + yn+1 2 なる整数 xn+1 , yn+1 が
xn+1 = 3xn + 4yn
2,
···⃝
yn+1 = 2xn + 3yn
3
···⃝
として確かに存在する.
1 を満たす整数 xn , yn が
( i ), (ii) より, 任意の正整数 n に対して ⃝
3 のように表される.
2,⃝
存在し, ⃝
3 ×
2 −⃝
(2) ⃝
√
2 より,
√
√
xn+1 − yn+1 2 = (3xn + 4yn ) − (2xn + 3yn ) 2
√
√
= (3 − 2 2)(xn − yn 2).
√
√
よって, {xn − yn 2} は初項と公比が 3 − 2 2 の等比数列だから,
√
√
4.
xn − yn 2 = (3 − 2 2)n · · · ⃝
方程式の整数解 > ペル方程式
31
1,⃝
4 より,
(3) ⃝
√
√
xn 2 − 2yn 2 = (xn + yn 2)(xn − yn 2)
√
√
√
√
= (3 + 2 2)n (3 − 2 2)n = {(3 + 2 2)(3 − 2 2)}n
= 1n = 1.
よって, (x, y) = (xn , yn ) は ⃝
* の整数解である.
(4) ( i ) ⃝
* より,
p2 − 2q2 = x2 − 2y2 = 1.
(ii) 仮定より y > 0 だが, x2 − 2 · 12 = 1 の整数解は存在しない
から, y ≧ 2. よって, ⃝
* より
9y2 − 4x2 = y2 − 4(x2 − 2y2 ) = y2 − 4 ≧ 0
となるから,
q = 3y − 2x ≧ 0.
√
(iii) y + 1 > 0 より 2y2 + 1 > y2 すなわち 2y2 + 1 > y だから,
√
q = 3y − 2x = 3y − 2 2y2 + 1 < 3y − 2y = y.
2
( i )∼(iii) より, 題意が示された.
(5) 与えられた ⃝
* の正整数解 (x, y) について
p1 = x,
pk+1 = 3pk − 4qk
q1 = y,
qk+1 = −2pk + 3qk
5,
···⃝
6
···⃝
により整数の数列 {pk }, {qk } を定める. このとき, (4) より qk は正
である限り小さくなっていく.
しかし, y 以下の非負整数は有限個だから, ある正整数 n に対して
qn+1 = 0 となる. このとき, pn+1 = 1.
5,⃝
6 を pk , qk について解くと
さらに, ⃝
pk = 3pk+1 + 4qk+1 ,
qk = 2pk+1 + 3qk+1
となり, (pn , qn ) = (3, 2) となる.
↷
↷
↷
(1, 0)
∥
(pn+1 , qn+1 )
(x1 , y1 ) ↷ · · · ↷ (xn , yn )
∥
∥
(3, 2)
(x, y)
∥
∥
(pn , qn )
...
(p1 , q1 )
よって, (1) で示したことから, (x, y) = (xn , yn ). 終 2
2
2
2
背景 • x − dy = 1, x − dy = −1 (d: 1 以外の平方数を約数に持たない整数)
の形の方程式をペル方程式 † と呼ぶ.
• x2 − dy2 = 1 は必ず無限個の整数解を持つが, x2 − dy2 = −1 は整数解
w参
を持つとは限らない.
有理数解については, 問題 20 の「背景」を参照.
方程式の整数解 > ペル方程式
32
補充 11: ペル方程式 II (有名, 発展, 20 分)
(1) (xu + dyv)2 − d(xv + yu)2 を因数分解せよ.
(2) u2 − 2v2 = 1 の整数解を 1 つ与えよ.
(3) x2 − 2y2 = −1 は無限個の整数解を持つことを示せ.
2
2
方策 • (3) では, (1) の結果と (2) の解を用いて x − 2y を別の形で表す.
• x2 − 2y2 = −1 の整数解を 1 つ求め, 各座標が単調増加になるような
整数解の連立漸化式を導く.
解答 (1) 与式を展開して整理すると,
(xu + dyv)2 − d(xv + yu)2
= (x2 u2 + 2dxyuv + d2 y2 v2 ) − (dx2 v2 + 2dxyuv + dy2 u2 )
= x2 u2 − dx2 v2 − dy2 u2 + d2 y2 v2
= (x2 − dy2 )(u2 − dv2 )
1.
···⃝
(2) (u, v) = (3, 2) は
u2 − 2v2 = 1
2
···⃝
の 1 つの解を与える.
1 に d = 2, (u, v) = (3, 2) を代入すると, ⃝
2 より,
(3) ⃝
x2 − 2y2 = (3x + 4y)2 − 2(2x + 3y)2 .
また, (x, y) = (1, 1) は x2 − 2y2 = −1 を満たす.
そこで, 数列 {xn }, {yn } を
x1 = 1,
y1 = 1,
xn+1 = 3xn + 4yn ,
yn+1 = 2xn + 3yn
で定めると, 一般項の対 (x, y) = (xn , yn ) は x2 −2y2 = −1 の整数解
になる. xn+1 > xn に注意すると, これらの解は互いに異なる.
ゆえに, x2 − 2y2 = −1 は無限個の整数解を持つ. 終 方程式の整数解 > 2 次曲線の有理点
33
問題 20: 有理点を持たない 2 次曲線 (有名, 標準, 20 分)
次のことを示せ:
(1) a, b を整数とする. a2 + b2 が 3 の倍数ならば, a, b は 3 の倍数である.
(2) x2 + y2 = 3 の有理数解は存在しない.
方策 (1) a, b を 3 で割った余りで場合分けして示す.
(2) x2 +y2 = 3 の有理数解の存在 a2 + b2 = 3c2 の整数解の存在は同値.
解答 (1) 整数 n について,
( i ) n が 3 の倍数のとき, n2 も 3 の倍数である.
(ii) n = 3d ± 1 (d: 整数) のとき,
n2 = (3d ± 1)2 = 3(3d2 ± 2d) + 1
を 3 で割った余りは 1.
よって, a または b が 3 で割り切れないならば, a2 + b2 を 3 で
割った余りは 0 + 1 = 1 + 0 = 1 または 1 + 1 = 2 だから, a2 + b2 は
3 で割り切れない.
対偶をとると, a2 + b2 が 3 の倍数ならば, a, b は 3 の倍数である.
(2) 有理数 x, y が x2 + y2 = 3 を満たすとして矛盾を導く.
このとき, 互いに素な整数 a, b, c (c , 0) を用いて x =
と書ける. 与式に代入して分母を払うと,
a
b
,y=
c
c
a2 + b2 = 3c2 .
a2 + b2 は 3 の倍数だから, (1) より a, b はともに 3 の倍数である.
よって, a2 , b2 はともに 9 の倍数であり, したがって a2 + b2 = c2
も 9 の倍数である.
したがって, c2 は 3 の倍数だから, c も 3 の倍数である.
これは, a, b, c が互いに素であることに反する.
w参
ゆえに, x2 + y2 = 3 の有理数解は存在しない. 終 関連: 問題 17.
方程式の整数解 > 指数方程式
34
問題 21: 指数方程式の整数解 I (特殊, 標準, 20 分)
2 x + 1 = y2 の整数解をすべて求めよ.
方策 • まず, x > 0 を示す.
• このとき, 2 x + 1 = y2 は奇数となり, y も奇数となるので, y = 2n + 1
とおいて x, n の方程式を解く.
x
2
2
x
1.
解答 x, y を 2 + 1 = y の整数解とする. y = 2 + 1 > 0 だから, y > 0 · · · ⃝
2
x
また, y = 2 + 1 は整数だから, x ≧ 0.
さらに, 10 + 1 = y2 の解は存在しないから, x , 0.
2.
よって, x > 0 より 2 x + 1 = y2 は奇数だから, y も奇数である · · · ⃝
⃝
2 より y = 2n + 1 (n: 非負整数) とおくと,
1,⃝
2 x + 1 = (2n + 1)2 = 4n(n + 1) + 1.
∴ 2 x−2 = n(n + 1).
n(n + 1) は偶数だから, x − 2 ≧ 1 となり, x ≧ 3 となる.
さらに, 2 x−2 の素因数は 2 のみで, n, n + 1 のいずれかは奇数である.
3 以上の奇数は 3 以上の素因数を持つことに注意すると, n = 1.
このとき, y = 2 · 1 + 1 = 3.
ゆえに, 求める解は, (x, y) = (3, 3). 答 補充 12: 指数方程式の整数解 II (特殊, 発展, 30 分)
2x
について, x ≧ 3 のとき, 不等式 f (x) < f (x + 1) を示せ.
x2
x
2
(2) 2 = x の整数解をすべて求めよ.
(1) 関数 f (x) =
方策 (1) f (x) < f (x + 1) を示すには, f (x)/ f (x + 1) < 1 を示せば良い.
(2) 「2 x = x2 ⇐⇒ f (x) = 1」より, (1) で示した f (x)
.
( の単調性を利用
)2
1
1
1
4
1
16
≦
<2
解答 (1) x ≧ 3 のとき. ≦ より 1 + ≦ となり, 1 +
x
3
x
3
x
9
となるから,
(
)2
f (x)
2 x (x + 1)2 1
1
=
·
=
1+
< 1.
f (x + 1) x2
2
x
2 x+1
よって, f (x) < f (x + 1).
(2) x が負の整数のとき, 2 x < 1 ≦ x2 より, 2 x , x2 .
x = 0 のとき, 20 = 1 , 0 = 02 より, 2 x , x2 .
よって, 2 x = x2 の整数解は f (n) = 1 なる正整数 n に限る.
8
< 1, f (4) = 1
9
であり, (1) より n ≧ 5 のとき f (n) > f (4) = 1 となるから,
求める解は x = 2, 4. 答 f (1) = 2 , 1, f (2) = 1, f (3) =
35
n
3.
進
法
問題 22 (p. 36)
十進法で各位が相異なる 5 桁の正整数のうち, 最小の 11 の倍数を求めよ.
補充 13 (p. 36)
十進法で表すと各位の数字が 1, 2 のみから成る正整数のうち, 最小の 36 の
倍数 m を求めよ.
問題 23 (p. 37)
(1) 任意の正整数 n に対して 1000n − (−1)n は 7 の倍数であることを示せ.
(2) 非負整数 a を千進法で
2m+1
∑
a=
ak 1000k
(n, ak : 整数, m ≧ 0, 0 ≦ ak < 1000)
∑
∑m
と表すとき, a が 7 の倍数であることと a′ = m
ℓ=0 a2ℓ −
ℓ=0 a2ℓ+1 が
k=0
7 の倍数であることは同値であることを示せ.
問題 24 (p. 38)
(1) a, b を正整数とする. 十進法で (10a + 1)(10b + 1) の下 2 桁の表示が 01
であるための必要十分条件を求めよ.
(2) 十進法で 20172017 の下 2 桁の値を求めよ.
補充 14 (p. 38)
十進法で 101100 の下 5 桁の値を求めよ.
問題 25 (p. 39)
3 倍すると 0.ḃcde f ȧ になるような循環小数 0.ȧbcde f˙ の最小値を求めよ.
補充 15 (p. 39)
逆数をとると循環小数 0.ȧḃ になるような正整数 x の最小値を求めよ.
補充 16 (p. 39)
任意の有理数は, 有限小数または循環小数であることを示せ.
n 進法 > 倍数の判定法
36
問題 22: 11 の倍数の判定法 (典型, 標準, 20 分)
十進法で各位が相異なる 5 桁の正整数のうち, 最小の 11 の倍数を求めよ.
∑n
k
方策 • 十進法で表された数 k=0 a k 10 が 11 の倍数であるためには, 各位
∑
の数字の交代和 nk=0 (−1) k a k が 11 の倍数であることが必要十分.
解答 求める数は, 各位が相異なる最小の 5 桁の正整数 10234 以上である.
そこで, x, y を 3 以上 9 以下の数字として 10200 + 10x + y が 11 の倍数
になる条件を考える.
これは 1−0+2− x+y = 3− x+y が 11 の倍数であることと同値である.
x, y の取り方より
−3 = 3 − 9 + 3 ≦ 3 − x + y ≦ 3 − 3 + 9 = 9
だから, これは 3 − x + y = 0 すなわち x − y = 3 と同値である.
(x, y) = (6, 3) のとき x は最小となるから, 求める数は 10263. 答 補充 13: 4, 9 の倍数の判定法 (典型, 標準, 20 分)
十進法で表すと各位の数字が 1, 2 のみから成る正整数のうち, 最小の 36 の
倍数 m を求めよ.
方策 十進法で表された数が
• 4 の倍数であるためには, 下 2 桁が 4 の倍数であることが必要十分.
• 9 の倍数であるためには, 各桁の和が 9 の倍数であることが必要十分.
解答 36 の因数 4, 9 は互いに素だから, m は 4 の倍数かつ 9 の倍数である.
m の下 2 桁は, 11, 12, 21, 22 のいずれかだが, m は 4 の倍数だから,
12 でなければならない.
m はこの条件を満たす最小の 9 の倍数だから, 各位の数字の和は 9.
よって, すべての正整数は 1, 2 の和で表せることに注意すると, m の
最高位から百の位までの数字和の和は 9 − (1 + 2) = 6.
6 を 1 または 2 の和で表す方法のうち, 項数が最小のものは 6 = 2+2+2.
以上より, m = 22212. 答 n 進法 > 倍数の判定法
37
問題 23: 7 の倍数の判定法 (有名, 標準, 20 分)
(1) 任意の正整数 n に対して 1000n − (−1)n は 7 の倍数であることを示せ.
(2) 非負整数 a を千進法で
2m+1
∑
a=
ak 1000k
(n, ak : 整数, m ≧ 0, 0 ≦ ak < 1000)
∑
∑m
と表すとき, a が 7 の倍数であることと a′ = m
ℓ=0 a2ℓ −
ℓ=0 a2ℓ+1 が
k=0
7 の倍数であることは同値であることを示せ.
策 1 (1) 1001 = 7 · 143 と次の恒等式を使えば直ちに示せる:
x n − y n = (x − y)(x n−1 + x n−2 y + · · · + y n−1 ).
(2) a − a′ が 7 の倍数であることを示せば良い. 一般に, 次が成り立つ:
整数 a, a′ を m で割った余りが一致 ⇐⇒ a − a′ は m の倍数.
解 1 (1) 1000 − (−1) = 1001 = 7 · 143 より,
1000n − (−1)n = {1000 − (−1)} × {1000n−1 + · · · + (−1)n−1 }
は 7 の倍数である.
(2) a − a′ =
2m+1
∑
ak 1000k −
k=0
2m+1
∑
ak (−1)k =
k=0
2m+1
∑
ak {1000k − (−1)k }
k=0
の右辺の各項は 7 の倍数だから, a − a′ は 7 の倍数である.
ゆえに, 題意が示された. 終 †
策 2 1001 = 7 · 143 と合同式 を用いる.
解 2 (1) 1001 = 7 · 143 だから, 1000 = 1001 − 1 ≡ −1 (mod 7).
よって, 任意の正整数 n に対して 1000n ≡ (−1)n (mod 7).
ゆえに, 1000n − (−1)n は 7 の倍数である.
(2) (1) より,
2m+1
∑
ak 1000k ≡
ak (−1)k = a′ (mod 7).
k=0
k=0
ゆえに, 題意が示された. 終 注 • 問題 1 のように帰納法による (1) の証明も可能であるが, 省略.
a=
2m+1
∑
• この判定法によれば, 789 − 012 = 777 より, 789012 は 7 の倍数.
• 1001 = 7 · 11 · 13 より, 13 の倍数も同様に判定できる.
背景 • 本問で示した方法以外にも, さまざまな 7 の倍数の判定法がある.
∑
例えば, 十進法で 2 桁以上の整数 a = nk=0 ak 10k に対し,
n
∑
a が 7 の倍数 ⇐⇒
ak 10k−1 − 2a0 は 10 の倍数.
k=1
w参
これによれば, 258 − 2 · 3 − 252, 25 − 2 · 2 = 21 より, 2583 は 7 の倍数.
(1) の類題: 問題 1.
n 進法 > 累乗数の下位
38
問題 24: 累乗数の下位 I (典型, 実戦, 30 分)
(1) a, b を正整数とする. 十進法で (10a + 1)(10b + 1) の下 2 桁の表示が 01
であるための必要十分条件を求めよ.
(2) 十進法で 20172017 の下 2 桁の値を求めよ.
2017
を 100 で割った余りを計算するため, 合同式 † を使う.
方策 • 2017
• 17n ≡ 1 (mod 100) なる整数 n が見つかれば, 指数法則 a n1 +n2 = a n1 a n2
と合同式の性質 a ≡ a′ , b ≡ b′ (mod m) =⇒ ab ≡ a′ b′ (mod m)
により, 合同式で 172017 の指数を小さくできる.
• (1) を活用するために, 17 の累乗の中で, 下 2 桁が 10a + 1 の形になる
ものをいくつか計算してみる.
解答 (1) (10a+1)(10b+1) = 100ab+10(a+b)+1 ≡ 10(a+b)+1 (mod 100).
よって, (10a + 1)(10b + 1) の下 2 桁の表示が 01 であるための
必要十分条件は, a + b が 10 の倍数であることである.
(2) 2017 ≡ 17 (mod 100) だから, 20172017 ≡ 172017 (mod 100)
一方,
1.
···⃝
172 = 289 ≡ 89 (mod 100),
174 = (172 )2 ≡ 892 = 7921 ≡ 21 (mod 100),
178 = (174 )2 ≡ 212 = 441 ≡ 41 (mod 100),
1716 = (178 )2 ≡ 412 = 1681 ≡ 81 (mod 100).
よって,
1720 = 1716 · 174 ≡ 81 + 21 = 101 ≡ 1 (mod 100).
ゆえに, 172017 = 1720·100+17 = (1720 )100 × 1717
≡ 1100 × 1716 · 17
2.
···⃝
≡ 77 (mod 100) だから, 求める値は 77. 答 ≡ 1 × 81 · 17 = 1377 ≡ 77 (mod 100)
⃝
1,⃝
2 より, 2017
2017
補充 14: 累乗数の下位 II (典型, 基本, 20 分)
十進法で 101100 の下 5 桁の値を求めよ.
100
100
5
方策 101 = (100 + 1) を二項定理で展開し, 10 で割った余りを求める.
つまり, 105 でくくれない項の総和を求める.
解答 二項定理により,
101100 = (100 + 1)100
= 100100 + · · · + 100 C3 1003 + 100 C2 1002 + 100 C1 100 + 1
= 10200 + · · · + 100 C3 106 + 4950 · 104 + 100 · 100 + 1
= 105 (10195 + · · · + 100 C3 10 + 495) + 10001.
ゆえに, 101100 の下 5 桁は 10001. 答 n 進法 > 循環小数
39
問題 25: 循環小数 I (典型, 標準, 20 分)
3 倍すると 0.ḃcde f ȧ になるような循環小数 0.ȧbcde f˙ の最小値を求めよ.
方策 10 倍することで循環節をずらして, 3 倍との差をとる.
˙
解答 x = 0.ȧbcde f とおく.
1.
両辺を 10 倍すると,
10x = a.ḃcde f ȧ · · · ⃝
条件より,
3x = 0.ḃcde f ȧ
2.
···⃝
⃝
1 −⃝
2 より,
7x = a.
a
3a
よって, x = となるから, 0 < 3x =
< 1 より, 0 < 3a < 7 となる.
7
7
a は 1 以上 9 以下の整数だから, a = 1, 2.
1 よって, x の最小性により, a = 1. ゆえに, 求める小数は x = . 答 7
補充 15: 循環小数 II (典型, 標準, 20 分)
逆数をとると循環小数 0.ȧḃ になるような正整数 x の最小値を求めよ.
方策 100 倍することで循環節を 1 周期ずらして, 差をとる.
1
100
解答 x = 0.ȧḃ の両辺を 100 倍すると x = ab.ȧḃ となる.
99
辺々の差をとると,
= 10a + b.
x
よって, (10a + b)x = 99 より 10a + b は 99 = 32 · 11 の正の約数 1, 3, 9,
11, 33, 99 のいずれかだから, a , b に注意すると, 10a + b = 1, 3, 9.
よって, x の最小性すなわち 10a + b の最大性により, 10a + b = 99.
99
= 11. 答 9
補充 16: 循環小数 III (有名, 実戦, 20 分)
ゆえに, 求める正整数は x =
任意の有理数は, 有限小数または循環小数であることを示せ.
†
方策 n での除法の筆算の余りから定まる数列に鳩の巣原理 (p. 50) を適用.
m
解答 与えられた有理数 a が整数 m と正整数 n の比 n で表されるとする.
分子 m を分母 n で割り算して, 割り切れない場合は, 余りの 10 倍を n
で割るという操作を繰り返す.
( i ) この操作が有限回で終了する場合. a は有限小数である.
(ii) この操作が無限に続く場合. a は循環小数になる.
実際, 整数が n で割り切れない場合, 余りの可能性は 1, · · · , n − 1
の n − 1 通りある. 上記の操作が無限に続くとしても, 鳩の巣原理
により最初の n 回の割り算の余り n 個のうち少なくとも 2 個は
等しくなって, a は循環小数となる. 終 40
4.
そ
の
他
問題 26 (p. 42)
実数係数 3 次多項式 f (x) について, 次の 2 条件は同値であることを示せ:
( i ) 任意の整数 n に対して, f (n) は整数である.
a
b
(ii) ある整数 a, b, c, d について, f (x) = x(x − 1)(x − 2) + x(x − 1) + cx + d.
6
2
補充 17 (p. 42)
実数係数 d 次多項式 f (x) について, 次の 3 条件は同値であることを示せ:
( i ) 任意の整数 n に対して, f (n) は整数である.
(ii)
f (0) は整数であり, 任意の整数 n に対して f (n + 1) − f (n) は整数である.
(iii) f (0), · · · , f (d) は整数である.
補充 18 (p. 43)
n が正整数ならば, f (n) =
n5 n4 n3
n
+
+
−
の値は整数であることを示せ.
5
2
3
30
以下, 与えられた実数 a 以下の最大の整数を [a] で表す.
また, 0 でない整数 a の素因数分解における素数 p の指数を v p (a) で表す.
問題 27 (p. 44)
(1) 0 < b ≦ c なる任意の実数 a, b, c に対して, 不等式
[a]
≦
[a]
を示せ.
b
(2) 十進法の 100! を六進法で表すとき, 末尾に並ぶ 0 の個数 e を求めよ.
各正整数 n, r について, pr ≦ n < pr+1 ならば
]
r [
∑
n
v p (n!) =
pk
k=1
···⃝
*
が成り立つことは証明なしに用いて良い.
補充 19 (p. 45)
(1) 0 でない任意の整数 a, b に対して, 次の等式を示せ:
v p (ab) = v p (a) + v p (b).
(2) 任意の正整数 m, n に対して, 次のことを示せ:
m ≦ n =⇒ v p (m!) ≦ v p (n!).
(3) 任意の正整数 r に対して, 次の等式を示せ:
v2 (2r !) = 2r − 1.
(4) v2 (n!) = 97 であるような正の偶数 n の値を求めよ.
問題 27 の等式 ⃝
* は証明なしに用いて良い.
c
41
問題 28 (p. 46)
1,⃝
2 を満たす実数 x, y, 正整数 m, n について, (1)∼(3) を示せ.
次の ⃝
1 1
2.
+ = 1 ···⃝
x y
1,
[mx] = [ny] = k · · · ⃝
(1)
[mx]
[mx] + 1
≦m<
.
x
x
(2) m + n = k.
(3) x, y は有理数である.
補充 20 (p. 46)
任意の実数 a, 正整数 n に対して,
n−1 [
∑
k=0
]
k
a+
= [na] が成り立つことを示せ.
n
問題 29 (p. 47)
正六十角形 P0 · · · P59 の頂点 P0 を発着点として長さがすべて等しい対角線
を右回りに繋げていくことで描ける図形のうち, 全頂点を通る図形の個数 N
を求めよ.
問題 30 (p. 48)
n を正整数とする. 次の連立不等式の整数解 (x, y) の個数を求めよ:
1,
0 < x ≦ 2n · · · ⃝
2.
0 < y ≦ log2 x · · · ⃝
補充 21 (p. 48)
n を 3 以上の奇数とする. 次を満たす正整数の組 (x, y, z) の個数を求めよ:
1,
x + y + z = n ···⃝
2,
x ≦ y + z ···⃝
3,
y ≦ z + x ···⃝
4.
z ≦ x + y ···⃝
補充 22 (p. 49)
√
3 が無理数であることは, 証明なしに用いて良い:
1
−−→
−−→
(1) △OPQ について, OP = (a, b), OQ = (c, d) のとき, △OPQ = |ad − bc|.
2
(2) 全頂点の各座標が整数である正三角形は存在しない.
次のことを示せ.
問題 31 (p. 50)
十進法で各位が 1 である d + 1 桁の整数
∑d
k=0
10k を f (d) で表す. 次のこと
を示せ.
(1) n が 10 と互いに素であるとき, n + 1 個の整数 f (d) (0 ≦ d ≦ n) の中に
n の倍数が存在する.
(2) 任意の整数 n は何倍かすると, 10e f (d) (d, e: 非負整数) の形になる.
補充 23 (p. 50)
(1) 連続する整数 a, a + 1 は互いに素であることを示せ.
(2) n を正整数とする. 2n 以下の n + 1 個の正整数の中には, 互いに素な 2 個
の整数が存在することを示せ.
その他 > 整数値をとる多項式
42
問題 26: 整数値をとる多項式 I (典型, 実戦, 30 分)
実数係数 3 次多項式 f (x) について, 次の 2 条件は同値であることを示せ:
( i ) 任意の整数 n に対して, f (n) は整数である.
a
b
(ii) ある整数 a, b, c, d について, f (x) = x(x − 1)(x − 2) + x(x − 1) + cx + d.
6
2
解答 f (x) を x(x−1)(x−2) で割った商を α, 余りを r(x) とおき, r(x) を x(x−1)
で割った商を β, 余りを γx + δ とおくと, 次のように表せる:
f (x) = αx(x − 1)(x − 2) + βx(x − 1) + γx + δ
• よって,
1.
···⃝
( i ) =⇒ f (0), f (1), f (2), f (3) は整数
=⇒ δ, γ + δ, 2β + 2γ + δ, 6α + 6β + 3γ + δ は整数
=⇒ δ, γ, 2β, 6α は整数
· · · (iii).
• 逆に, 各整数 n に対して n(n − 1) は偶数, n(n − 1)(n − 2) は 6 の倍数
1 より, (iii) ⇒ ( i ) も成り立つ.
であることに注意すると, ⃝
• a = 6α, b = 2β, c = γ, d = δ とおけば, (iii) ⇒ (ii) が成り立つ.
• (ii) を仮定すると, f (0) = d = δ, f (1) = c+d = γ+δ, f (2) = b+2c+d =
2β + 2γ + δ, f (3) = a + 3b + 3c + d = 6α + 6β + 3γ + δ となり, a = 6α,
b = 2β, c = γ, d = δ となるから, (iii) が成り立つ. 終 補充 17: 整数値をとる多項式 II (有名, 標準, 30 分)
実数係数 d 次多項式 f (x) について, 次の 3 条件は同値であることを示せ:
( i ) 任意の整数 n に対して, f (n) は整数である.
(ii)
f (0) は整数であり, 任意の整数 n に対して f (n + 1) − f (n) は整数である.
(iii) f (0), · · · , f (d) は整数である.
解答 • ( i ) ⇒ (ii) は明らか.
• (ii) を仮定すると, 任意の正整数 n に対して
f (n) = { f (n) − f (n − 1)} + · · · + { f (1) − f (0)} + f (0),
f (−n) = f (0) − { f (0) − f (−1)} − · · · − { f (−n + 1) − f (−n)}
は整数である. よって, (ii) ⇒ ( i ) が成り立つ.
• (a) d = 0 のとき. f (x) は定数関数だから, (ii) ⇔ (iii) が成り立つ.
(b) 与えられた非負整数 d について, 任意の d 次多項式に対して
(ii) ⇔ (iii) の成立を仮定する. この d で ( i ) ⇔ (iii) が成り立つ.
f (x) を d + 1 次多項式とすると, f (x + 1) − f (x) は d 次だから,
任意の整数 n に対して f (0), f (n + 1) − f (n) は整数
⇐⇒ f (0), f (1) − f (0), · · · , f (d + 1) − f (d) は整数
⇐⇒ f (0), · · · , f (d), f (d + 1) は整数.
(a), (b) より, 任意の非負整数 d に対して (ii) ⇔ (iii) が成り立つ. 終 その他 > 整数値をとる多項式
43
補充 18: 整数値をとる多項式 III (典型, 実戦, 30 分)
n が正整数ならば, f (n) =
n5 n4 n3
n
+
+
−
の値は整数であることを示せ.
5
2
3
30
策 1 f (n + 1) − f (n) をパスカルの三角形を利用して展開し, 整理してみる.
5
4
3
解 1 30 f (n) = 6n + 15n + 10n − n より
30{ f (n + 1) − f (n)}
= 6{(n + 1)5 − n5 } + 15{(n + 1)4 − n4 } + 10{(n + 1)3 − n3 } − {(n + 1) − n}
= 6(5n4 +10n3 +10n2 +5n+1)+15(4n3 +6n2 +4n+1)+10(3n2 +3n+1)−1
= 30n4 + 120n3 + 180n2 + 120n + 30
(x + y)n の展開式の係数
4
3
2
= 30(n + 4n + 6n + 4n + 1)
n=1
1 1
= 30(n + 1)4
n=2
1 2 1
となるから,
3
1
3
n=3
1
n=4
f (n + 1) − f (n) = (n + 1) .
1
1 5 10 10 5 1 n = 5
(6+15+10−1) = 14 .
また, f (1) =
30
∑
よって, 帰納法により, 任意の正整数 n に対して f (n) = nk=1 k4 である
こと, 特に f (n) は整数であることが従う. 終 4
1
4
6
4
1
策 1 通分し, 分母の素因数で割った余りで場合分けして示す.
30 f (n) = 6n5 + 15n4 + 10n3 − n
解 2 1.
= n(n + 1)(2n + 1)(3n2 + 3n − 1) · · · ⃝
が 30 の倍数であることを示せば良い.
1 は 2 の倍数である.
• n(n + 1) は 2! = 2 の倍数だから, ⃝
1 が 3 の倍数であることを示すため, n を 3 で割った余りで場合に
• ⃝
1 のある因数が 3 の倍数であることを示す.
分けて, ⃝
( i ) n ≡ 0 (mod 3) のとき, 示すべきことはない.
(ii) n ≡ 1 (mod 3) のとき, 2n + 1 ≡ 2 + 1 = 3 ≡ 0 (mod 3).
(iii) n ≡ 2 (mod 3) のとき, n + 1 ≡ 2 + 1 = 3 ≡ 0 (mod 3).
1 が 5 の倍数であることを示すため, n を 5 で割った余りで場合に
• ⃝
1 のある因数が 5 の倍数であることを示す.
分けて, ⃝
( i ) n ≡ 0 (mod 5) のとき, 示すべきことはない.
(ii) n ≡ 1 (mod 5) のとき, 3n2 + 3n − 1 ≡ 3 + 3 − 1 = 5 ≡ 0 (mod 5).
(iii) n ≡ 2 (mod 5) のとき, 2n + 1 ≡ 2 · 2 + 1 = 5 ≡ 0 (mod 5).
(iv) n ≡ 3 (mod 5) のとき, 3n2 +3n−1 ≡ 33 +32 −1 = 35 ≡ 0 (mod 5).
( v ) n ≡ 4 (mod 5) のとき, n + 1 ≡ 4 + 1 = 5 ≡ 0 (mod 5).
1 は 2 · 3 · 5 = 30 の倍数である.
2, 3, 5 は互いに素だから, ⃝
題意が示された. 終 その他 > ガウスの記号
44
以下, 与えられた実数 a 以下の最大の整数を [a] で表す.
また, 0 でない整数 a の素因数分解における素数 p の指数を v p (a) で表す.
問題 27: n! の p 進付値 I (典型, 実戦, 20 分)
(1) 0 < b ≦ c なる任意の実数 a, b, c に対して, 不等式
[a]
≦
[a]
を示せ.
b
(2) 十進法の 100! を六進法で表すとき, 末尾に並ぶ 0 の個数 e を求めよ.
c
各正整数 n, r について, pr ≦ n < pr+1 ならば
]
r [
∑
n
v p (n!) =
pk
k=1
···⃝
*
が成り立つことは証明なしに用いて良い.
[a]
a
a
(1)
が と の間にあるか, 外にあるかによって場合分けして,
方策
b
c
b
記号 [ ] で表された数の最大性をうまく利用する.
a a
解答 (1) 0 < b ≦ c を仮定する. このとき, c ≦ b .
[a] a
[a] [a]
a [a] a
(i)
<
≦ のとき.
≦ より,
≦
.
c
b
[ca ] ba ba
[ ac ] c
≦ ≦ のとき.
の最大性により
(ii)
b
c b
c
[a] [a] a a
≦
≦ ≦
b
c
[a]
[ca ] b [ a ]
となるから,
の最大性により,
=
.
b
c
b
( i ), (ii) より, すべての場合に求める不等式が成り立つ.
(2) e は 100! が 6 で割り切れる回数の最大値に等しい
[
] [ .]
100
100
また, (1) より, 各正整数 k に対して
≧
となるから,
2k
3k
⃝
* より v2 (100!) ≧ v3 (100!) となる. ゆえに,
[
] [
] [
] [
]
100
100
100
100
e = v3 (100!) =
+
+
+
(∵ ⃝
*)
3
9
27
81
= 33 + 11 + 3 + 1 = 48.
答 †
注 • [ ] をガウスの記号 と呼ぶ. 英語では Gaussian symbol と呼ばない.
• ⃝
* は, n 以下の各正整数の下に素因数分解における p の指数の値だけ
◦ を縦に並べて横に足すという発想で証明できる.
例えば, v2 (10!) = 8 は次表の右欄の合計として求まる.
1
2
◦
3
4
◦
◦
5
6
◦
7
8
◦
◦
◦
9
10
◦
5 = (21 の倍数の個数)
2 = (22 の倍数の個数)
1 = (23 の倍数の個数)
†
背景 v p (a) を a の p 進付値 と呼ぶ. 関数 v p は整数論で重要な役割を果たす.
その他 > ガウスの記号
45
補充 19: n! の p 進付値 II (有名, 実戦, 30 分)
(1) 0 でない任意の整数 a, b に対して, 次の等式を示せ:
v p (ab) = v p (a) + v p (b).
(2) 任意の正整数 m, n に対して, 次のことを示せ:
m ≦ n =⇒ v p (m!) ≦ v p (n!).
(3) 任意の正整数 r に対して, 次の等式を示せ:
v2 (2r !) = 2r − 1.
(4) v2 (n!) = 97 であるような正の偶数 n の値を求めよ.
問題 27 の等式 ⃝
* は証明なしに用いて良い.
方策 (1) 素因数分解を用いる.
(3) 等比数列の和の公式を用いる.
(4) まず, 仮定, (3) と (2) の対偶 v2 (m!) > v2 (n!) =⇒ m > n により
2r < n < 2r+1 なる r を求める. すると 26 < n < 27 となるので, ⃝
*
6
7
と (2) の対偶により n と (2 + 2 )/2 の大小を比較してみる.
解答 (1) 素因数分解を考えると,
a = pv p (a) a′ , b = pv p (b) b′
(a′ , b′ : p と互いに素な整数)
と表せる. このとき,
ab = 2v(a)+v(b) a′ b′
(a′ b′ : p と互いに素).
よって, v p (ab) = v p (a) + v p (b).
(2) m ≦ n ならば, (1) より
v p (m!) = v p (m)+· · ·+v p (1) ≦ v p (n)+· · ·+v p (m)+· · ·+v p (1) = v p (n!).
(3) ⃝
* より,
[
]
[ r]
2r
2
1(2r − 1)
v2 (2 !) =
+ · · · + r = 2r−1 + · · · + 1 =
= 2r − 1.
2
2
2−1
(4) 26 − 1 = 63 < 97 < 127 = 27 − 1 だから, (3) と条件より
r
v2 (26 !) < v2 (n!) < v2 (27 !).
よって, (2) の対偶より, 26 < n < 27 .
そこで, n と (26 + 27 )/2 = 96 の大小を比較してみると, ⃝
* より
[
]
[ ]
96
96
v2 (96!) =
+ · · · + 6 = 94 < 97
2
2
となるから, (2) の対偶より 96 < n となる. (1) より
v2 (97!) = v2 (97) + v2 (96!) = 94,
v2 (98!) = v2 (98) + v2 (97!) = 95,
v2 (99!) = v2 (99) + v2 (98!) = 95,
となるから, n = 100. 答 v2 (100!) = v2 (100) + v2 (99!) = 97
その他 > ガウスの記号
46
問題 28: 整数倍のガウス記号 (有名, 実戦, 20 分)
1,⃝
2 を満たす実数 x, y, 正整数 m, n について, (1)∼(3) を示せ.
次の ⃝
1,
[mx] = [ny] = k · · · ⃝
(1)
[mx]
[mx] + 1
≦m<
.
x
x
1 1
2.
+ = 1 ···⃝
x y
(2) m + n = k.
(3) x, y は有理数である.
方策 [a] ≦ a < [a] + 1 の等号成立条件に着目する.
k
k+1
3.
1 より k ≦ mx < k + 1 だから,
≦m<
···⃝
解答 (1) ⃝
x
x
k+1
k
4.
≦n<
···⃝
(2) (1) と同様にして,
y
y
(
)
(
)
1 1
1 1
⃝
3 +⃝
4 より, k
5.
+
≦ m + n < (k + 1)
+
···⃝
x y
x y
2 より, k ≦ m + n < k + 1 · · · ⃝
6.
よって, ⃝
m, n, k は整数だから, m + n = k.
3,⃝
6 すなわち ⃝
5 で等号が成り立つのは ⃝
4 で等号が成り立つと
(3) ⃝
k
k
k
k
きに限るから, = m, = n より, x = , y = .
x
y
m
n
ゆえに, x, y は有理数である. 終 †
背景 次のレイリーの定理 が背景になっている: 与えられた正の数 x, y に
ついて, すべての整数が [mx], [ny] (m, n: 整数) の形に重複なく表される
1 1
ためには, + = 1 が成り立ち x, y が無理数であることが必要十分
x y
である.
補充 20: ガウス記号の性質 (有名, 発展, 20 分)
任意の実数 a, 正整数 n に対して,
n−1 [
∑
k=0
]
k
a+
= [na] が成り立つことを示せ.
n
k
方策 不等式 [na] ≦ na < [na] + 1 から a + n の値を評価するために,
[na] = nq + r と表して代入し, 各辺を n で割る.
解答 除法の定理により, [na] = nq + r (q, r: 整数, 0 ≦ r ≦ n − 1) と表す.
r
r+1
[na] ≦ na < [na] + 1 に代入して n で割ると, q + ≦ a < q +
.
n
n
k
k+r+1
k+r
≦ a+ < q+
.
k を 0 ≦ k ≦ n−1 なる整数とすると, q+
n
n [
]n
k
k+r+1
(i)
≦ 1 すなわち 0 ≦ k ≦ n − r − 1 のとき, a +
= q.
n
[
] n
k+r
k
(ii)
≧ 1 すなわち n − r ≦ k ≦ n − 1 のとき, a +
= q + 1.
n
n
]
n−1 [
∑
k
( i ), (ii) より,
a+
= (n − r)q + r(q + 1) = nq + r = [na]. 終 n
k=0
その他 > オイラーの関数
47
問題 29: オイラーの関数 (有名, 発展, 30 分)
正六十角形 P0 · · · P59 の頂点 P0 を発着点として長さがすべて等しい対角線
を右回りに繋げていくことで描ける図形のうち, 全頂点を通る図形の個数 N
を求めよ.
7
を描くように, P0 , Pm , · · · , Pkm , · · · , と結んでいくのだが,
方策 • 五芒星
m > 1 のときは km > 60 となる k があるので, そのときは Pkm = Pr
(r は km を 60 で割った余り) と考える.
• m が 60 と互いに素なときに限り, 全頂点を通る. 左右の対称性に注意
すると, N は 60 と互いに素な 30 以下の正整数の個数に等しい.
• この個数は, 具体的に書き出して数える.
解答 頂点 P0 を出発点として右回りに長さが P0 Pm の対角線を 60 本繋げて
いくことで描ける図形を Fm で表す.
Fm = F60−m だから, 1 本目の対角線を P0 Pm
(0 < m < 30) として数えて良い.
k 本目の対角線は, km を 60 で割った余りを
P11 P0 P1
P2m
rk とおくと, Prk−1 Prk と表せる.
P3m
m が 60 と互いに素なとき, r0 , · · · , r59 は
Pm
(参考: 正十二角形の場合)
実際, 0 ≦ i ≦ j < 60, ri = r j ならば 0 ≦ m( j − i) < 60 は 60 の倍数と
すべて異なるので, Fm は全頂点を通る.
なるから, m( j − i) = 0 すなわち i = j となる.
逆に, m が 60 の最大公約数が g , 1 のとき, Fm は点 Pkg (0 ≦ k < 60/g)
しか通らず, 全頂点を通らない.
よって, Fm が全頂点を通るためには, m が 60 と互いに素であることが
必要十分である.
60 = 22 ·3·5 と互いに素な 30 以下の正整数は 1, 7, 11, 13, 17, 19, 23, 29
の 8 個だから, N = 8. 答 背景 • 与えられた正整数 n と互いに素な n 以下の正整数の個数を φ(n) で
表す. φ をオイラーの φ 関数 † と呼ぶ.
• 次の定理によれば, 2N = φ(60) = 60(1 − 2−1 )(1 − 3−1 )(1 − 5−1 ) = 16
と計算できる:
◦正整数 n = p1 e1 · · · pr er (pk : 相異なる素数, ek : 正整数) に対して,
φ(n) = n(1 − p1 −1 ) · · · (1 − pr −1 ).
◦互いに素な任意の正整数 m, n に対して,
φ(mn) = φ(m)φ(n).
その他 > 格子点
48
問題 30: 格子点の個数 I (典型, 実戦, 20 分)
n を正整数とする. 次の連立不等式の整数解 (x, y) の個数を求めよ:
1,
0 < x ≦ 2n · · · ⃝
2.
0 < y ≦ log2 x · · · ⃝
†
方策 • すべての座標が整数である点を格子点 と呼ぶ.
まず, y の値の範囲を求める. k をその範囲にある整数として直線
y = k 上で格子点を数えてから, k について足し合わせる.
• m 以上 n 以下の整数は m − n + 1 個であることに注意.
1,⃝
2 を満たすとする. y = k のとき, x は
解答 整数 x, y が ⃝
k
2 ≦ x ≦ 2n
y
なる 2n − 2k + 1 個のすべての整数値を
1,⃝
2 と log2 の単調性より,
とり得る. ⃝
n
k
0 < k ≦ n.
O
ゆえに, 求める整数解の個数は,
1
y = log2 x
2n
2k
n
∑
2(2n − 1)
= n(2n + 1) − 2n+1 + 2.
(2n − 2k + 1) = n(2n + 1) −
2
−
1
k=1
x
答 補充 21: 格子点の個数 II (典型, 実戦, 20 分)
n を 3 以上の奇数とする. 次を満たす正整数の組 (x, y, z) の個数を求めよ:
1,
x + y + z = n ···⃝
2,
x ≦ y + z ···⃝
3,
y ≦ z + x ···⃝
4.
z ≦ x + y ···⃝
方策 切断面 z = k (k: 整数) 上で格子点を数えて, k について足し合わせる.
1,⃝
4 を満たすとき,
解答 n = 2m + 1 (m: 正整数) とおく. 正整数 x, y, z が ⃝
1
2z ≦ x + y + z = n = 2m + 1 だから, z ≦ m + より 1 ≦ z ≦ m.
2
そこで, 1 ≦ k ≦ m なる整数 k を固定して, 平面 z = k 上で条件を満たす
1 ∼⃝
4 より,
整数の組に対応する点 (x, y) を数える. ⃝
5,
x + y = 2m + 1 − k · · · ⃝
6,
x − k ≦ y ≦ x + k ···⃝
7.
k ≦ x + y ···⃝
7 が定める領域内で直線 ⃝
6,⃝
5 上にある.
点 (x, y) は ⃝
右図のように, x は m − k + 1 ≦ x ≦ m なる
すべての整数値をとる.
y
y= x+k
2m+1−k
また, x が整数ならば y も整数であり, y の
値は x の値に応じて異なる値をとるから,
z = k 上で条件を満たす点の個数は k.
n−1
ゆえに, 求める個数は, m =
より,
2
1 + ··· + m =
y= x−k
k
O
m−k+ 12 k m+ 12
m(m + 1) (n + 1)(n − 1)
=
.
2
2
答 x
⃝
5
その他 > 格子点
49
補充 22: 格子点を結ぶ三角形 (有名, 実戦, 30 分)
√
3 が無理数であることは, 証明なしに用いて良い:
1
−−→
−−→
(1) △OPQ について, OP = (a, b), OQ = (c, d) のとき, △OPQ = |ad − bc|.
2
(2) 全頂点の各座標が整数である正三角形は存在しない.
次のことを示せ.
2
2
方策 (1) 三角形の面積の公式, 三角比の相互関係 cos θ+sin θ = 1, ベクトル
の内積の公式 ⃗a · ⃗b = |⃗a||⃗b| cos θ = a1 b1 + a2 b2 を組み合わせる.
(2) 背理法で示す. (1) を用いて, 三角形の面積の 2 通りに表す. それ
√
を用いて, 背理法の仮定の下で 3 を整数の比で表す.
1 −−→ −−→ √
1
2
解答 (1) △OPQ = 2 OP · OQ sin ∠POQ = 2 |OP||OQ| 1 − cos ∠POQ
v
u
u
−−→ −−→ 2
t
√
OP · OQ
1 −−→ −−→
1 −−→ 2 −−→ 2 −−→ −−→ 2
= |OP||OQ| 1 − −−→ −−→ =
|OP| |OQ| − (OP · OQ)
2
2
|OP||OQ|
1√
1
1√ 2
=
(a + b2 )(c2 + d2 ) − (ac + bd)2 =
(ad − bc)2 = |ad − bc|.
2
2
2
(2) 全頂点の各座標が整数である正三角形 OPQ の存在を仮定する.
−−→
−−→
1 が成り立つ.
OP = (a, b), OQ = (c, d) とおく. このとき, ⃝
また, △OPQ が正三角形であることから,
√
1 2
3 2
◦
△OPQ = OP sin 60 =
(a + b2 ).
2
4
√
√
2|ad − bc|
1
3 2
.
(1) より, |ad − bc| =
(a + b2 ) だから, 3 = 2
2
4
a + b2
a, b, c, d は整数だから, 右辺は整数である.
√
これは, 3 が無理数であることに反する.
注
ゆえに, 全頂点の各座標が整数である正三角形は存在しない. 終 (2) の別解: 三角形の辺長に着目, ラグランジュの恒等式を利用
全頂点の各座標が整数である正三角形の存在を仮定する. このとき,
必要に応じて各頂点を平行移動すると, ある整数 a, b, c, d について
O(0, 0), P(a, b), Q(c, d) を頂点とする正三角形が得られる.
OP = OQ より OP2 = OQ2 だから,
a2 + b2 = c2 + d2
1.
···⃝
OQ = PQ より OQ2 = PQ2 だから, c2 + d2 = (a − c)2 + (b − d)2 .
1
2.
右辺を展開し, ac + bd について解くと, ac + bd = (a2 + b2 ) · · · ⃝
2
⃝
1 ,⃝
2 をラグランジュの恒等式 (ac+bd)2 +(ad−bc)2 = (a2 +b2 )(c2 +d2 )
に 代 入, 整 理 し て 分 母 を 払 う と, 3(a2 + b2 )2 = 4(ad − bc)2 と な り,
√ 2
√
2|ad − bc|
3(a + b2 ) = 2|ad − bc| より 3 = 2
となる.
a + b2
√
右辺の分母, 分子は整数だから, 3 が有理数であるという矛盾が生じる.
ゆえに, 全頂点の各座標が整数である正三角形は存在しない. 終 その他 > 鳩の巣原理の応用
50
問題 31: 鳩の巣原理の応用 I (典型, 実戦, 30 分)
十進法で各位が 1 である d + 1 桁の整数
∑d
k=0
10k を f (d) で表す. 次のこと
を示せ.
(1) n が 10 と互いに素であるとき, n + 1 個の整数 f (d) (0 ≦ d ≦ n) の中に
n の倍数が存在する.
(2) 任意の整数 n は何倍かすると, 10e f (d) (d, e: 非負整数) の形になる.
方策 本問のような存在定理の証明には, 次の鳩の巣原理 (ディリクレの部屋
割り論法)† が有用である: m 個を n 種類に分けるとき, m > n ならば,
少なくとも 2 個は同じ種類に属する (どれがどの種類かは不明).
解答 (1)
f (0), f (1), · · · , f (n) を n で割った余りは n 個以下だから, 鳩の巣
原理により, 0 ≦ i < j ≦ n なるある番号 i, j に対して f (i), f ( j) を
n で割った余りは等しい.
f ( j) − f (i) = f ( j − i) は n の倍数である.
n, 10 は互いに素だから, f ( j − i) は n の倍数である.
(2) ( i ) n が 10 と互いに素であるとき. (1) より, 題意が成り立つ.
(ii) 一般の場合. 素因数分解を考えると, 次のように表せる:
n = 2i 5 j n′
(i, j: 非負整数, n′ : 10 と互いに素な整数).
( i ) より, ある整数 m に対して mn′ = 10e f (d) となる.
• i ≦ j のとき. 2 j−i mn = 2 j 5 j mn′ = 10e+ j f (d).
• i > j のとき. 5i− j mn = 2i 5i mn′ = 10e+i f (d). 終 補充 23: 鳩の巣原理の応用 II (典型, 標準, 20 分)
(1) 連続する整数 a, a + 1 は互いに素であることを示せ.
(2) n を正整数とする. 2n 以下の n + 1 個の正整数の中には, 互いに素な 2 個
の整数が存在することを示せ.
方策 (1) a + 1 を a の任意の約数 d で割った余りに着目.
(2) 与えられた数を連続 2 整数の組に分けて, 鳩の巣原理を適用.
解答 (1) 1 より大きい a の任意の約数 d に対して, a + 1 を d で割った余り
は 1 となるから, a + 1 は d で割り切れない.
よって, a, a + 1 は互いに素である.
(2) 2n 以下の正整数の集合を {2k − 1, 2k} (1 ≦ k ≦ n) の形の n 個の
集合に分割する.
鳩の巣原理により, 与えられた n + 1 個の整数の少なくとも 2 個は
同じ集合に属するから, (1) よりそれらの整数は互いに素である.
ゆえに, 題意が示された. 終 記号一覧表
51
記
号
一
覧
表
数学記号
記号
意味
∴
∵
A =⇒ B
A ⇐⇒ B
x∈A
A⊂B
{x ∈ A| . . . }
a±b
a∓b
∑n
k=m ak
ab
an
ゆえに
なぜならば
a ≡ b (mod m)
|a|
a0 .a1 · · · an ȧn+1 · · · ȧn+p
n!
n Cr
cos θ
sin θ
tan θ
loga b
A ならば B
A と B は同値である
x は A に属する
A は B の部分集合である
. . . を満たす A の要素 x 全体
a + b または a − b
a − b または a + b
数列 {ak } の第 m 項から第 n 項までの和
a×b
n > 0 のとき n 個の a の積,
n = 0 のとき a0 = 1,
n < 0 のとき an = 1/a|n|
m を法として a は b と合同, a − b は m の倍数である
a の絶対値, a の符号を取り除いた数
小数第 n 位までが a0 .a1 · · · an であり, 小数第 n + 1 位以下で
an+1 · · · an+p という表示を無限に繰り返す小数
n の階乗, 1 以上 n 以下のすべての整数の積
n 個から r 個を選ぶ組合せ, n!/r!(n − r)!
θ の余弦, ∠ABC = θ, ∠BCA = 90◦ のとき, BC/AB
θ の正弦, ∠ABC = θ, ∠BCA = 90◦ のとき, CA/AB
θ の正接, ∠ABC = θ, ∠BCA = 90◦ のとき, CA/BC
a を底とする b の対数, a x = b を満たす実数 x (a > 0, a , 1)
ギリシャ文字
大
小
読み方
大
小
A
B
Γ
∆
E
Z
H
Θ
α
β
γ
δ
ϵ
ζ
η
θ
アルファ
I
K
Λ
M
N
Ξ
O
Π
ι
κ
λ
µ
ν
ξ
o
π
ベータ
ガンマ
デルタ
エプシロン
ゼータ
エータ
シータ
読み方
大
小
読み方
イオタ
P
Σ
T
Υ
Φ
X
Ψ
Ω
ρ
σ
τ
υ
φ
χ
ψ
ω
ロー
カッパ
ラムダ
ミュー
ニュー
クシー
オミクロン
パイ
シグマ
タウ
ユプシロン
ファイ
カイ
プサイ
オメガ
問題一覧表
52
問
題
一
覧
倍数・約数
番号
題名
表
問題 11 問 + 補充 5 問 = 16 問
認知
難易
時間
′
論証
出題
問題 1
累乗和の倍数性
典型
基本
20
○
類名城大
問題 2
多項式で表された整数
有名
基本
20′
○
弘前大
問題 3
約数の和
典型
標準
10′
問題 4
最小公倍数と最大公約数
典型
基本
10′
′
愛知学院大
補充 1
約数の個数
典型
標準
20
問題 5
除法の定理
有名
実戦
40′
○
問題 6
ユークリッドの互除法
有名
標準
30′
△
′
問題 7
GCD と 1 次不定方程式 I
有名
実戦
20
△
補充 2
GCD と 1 次不定方程式 II
有名
発展
30′
○
問題 8
素数の性質
有名
実戦
20′
○
′
補充 3
多項式で表される素数
典型
基本
20
問題 9
メルセンヌ素数
有名
標準
20′
○
補充 4
公差 2 の「三つ子素数」
有名
基本
20′
○
早大
問題 10
数列の余りの周期性
有名
標準
20′
○
類東大
問題 11
フェルマーの小定理 I
有名
発展
30′
○
補充 5
フェルマーの小定理 II
有名
発展
30′
○
方程式の整数解
番号
題名
学習日
類星薬大
京都府医大
問題 10 問 + 補充 7 問 = 17 問
認知
難易
時間
論証
出題
′
問題 12
アイゼンシュタイン多項式
有名
標準
20
○
京大
補充 6
整数係数方程式の有理数解
典型
標準
20′
○
神戸大
問題 13
2 変数 1 次不定方程式
典型
標準
20′
補充 7
3 変数 1 次不定方程式
典型
実戦
20′
問題 14
2 変数 2 次不定方程式
有名
基本
20′
類東京薬大
補充 8
対称な高次不定方程式
典型
標準
20′
類同志社大
問題 15
対称な分数型方程式
典型
発展
20′
都立大
′
類大阪市大
補充 9
対称な分数型不等式
典型
発展
30
問題 16
原始ピタゴラス数 I
有名
実戦
30′
○
東北学院大
問題 17
原始ピタゴラス数 II
有名
実戦
30′
○
補充 10
原始ピタゴラス数 III
有名
発展
30′
○
′
同志社大
問題 18
ピタゴラス数の性質
有名
実戦
20
○
問題 19
ペル方程式 I
有名
発展
40′
○
類京大
補充 11
ペル方程式 II
有名
発展
20′
○
お茶女大
′
○
都立大
問題 20
有理点を持たない 2 次曲線
有名
標準
20
問題 21
指数方程式の整数解 I
特殊
標準
20′
補充 12
指数方程式の整数解 II
特殊
発展
30′
改学習院大
学習日
問題一覧表
53
n 進法
問題 4 問 + 補充 4 問 = 8 問
番号
題名
認知
難易
時間
問題 22
11 の倍数の判定法
典型
標準
20′
補充 13
4, 9 の倍数の判定法
典型
標準
20′
問題 23
7 の倍数の判定法
有名
標準
20′
問題 24
累乗数の下位 I
典型
実戦
30′
補充 14
累乗数の下位 II
典型
基本
20′
′
問題 25
循環小数 I
典型
標準
20
補充 15
循環小数 II
典型
標準
20′
補充 16
循環小数 III
有名
実戦
20′
論証
出題
学習日
○
お茶女大
○
その他
問題 6 問 + 補充 7 問 = 13 問
番号
題名
認知
難易
時間
論証
問題 26
整数値をとる多項式 I
典型
実戦
30′
○
補充 17
整数値をとる多項式 II
有名
標準
30′
○
補充 18
整数値をとる多項式 III
典型
実戦
30′
○
′
出題
改京大
問題 27
n! の p 進付値 I
典型
実戦
20
△
補充 19
n! の p 進付値 II
有名
実戦
30′
△
類千葉大
問題 28
整数倍のガウス記号
有名
実戦
20′
○
慶大
補充 20
ガウス記号の性質
有名
発展
20′
○
名市大
問題 29
オイラーの関数
有名
発展
30′
問題 30
格子点の個数 I
典型
実戦
20′
′
改大阪大
補充 21
格子点の個数 II
典型
実戦
20
補充 22
格子点を結ぶ三角形
有名
実戦
30′
○
東京工大
問題 31
鳩の巣原理の応用 I
典型
実戦
30′
○
補充 23
鳩の巣原理の応用 II
典型
標準
20′
○
学習日
COMPASS
整数有名問題集 第２版
著者
廣津 孝 (ひろつ たかし)
発行日
２０１６年４月１日
© Copyright 2024 ExpyDoc
