整数の性質(約数・ユークリッド・n 進法)― 整数だけの世界のルール
まず、身近なところから
コンピュータは 0 と 1 だけ(2 進法)で数を表す。時計は 60 でくり上がる。暗号は「大きな数を素因数分解するのが難しい」ことを使う。
たとえば「今日は月曜日。100 日後は何曜日?」は、100 を 7 でわった 余り だけ見ればわかる。
100 ÷ 7 = 14 あまり 2 ← 14 週間と 2 日
月曜日から 2 日進む → 水曜日
整数には、実数にはない わり算の余り・約数・倍数 の構造がある。それを扱うのが整数の性質。
この単元で使う記号・ことば
| 記号・ことば | 読み方 | 意味 |
|---|---|---|
| 約数(やくすう) | ― | その数をわり切る正の整数。12 の約数は 1, 2, 3, 4, 6, 12 |
| 倍数(ばいすう) | ― | その数に整数をかけた数。3 の倍数は 3, 6, 9, … |
| 素数(そすう) | ― | 約数が 1 と自分だけの数(2, 3, 5, 7, 11, …)。1 は素数でない |
| 素因数分解 | そいんすうぶんかい | 数を素数だけのかけ算にすること。 |
| ピー の エー じょう | p を a 回かけたもの。問題文では 2^3 のようにも書く | |
| 最大公約数 | さいだいこうやくすう | 2 つの数の共通の約数のうち、いちばん大きいもの |
| 互除法(ごじょほう) | ― | わり算をくり返して最大公約数を求める方法 |
| 商(しょう)・余り | ― | の 2 が商、39 が余り |
| 不定方程式 | ふていほうていしき | のように、解が 1 つに決まらない方程式 |
| a ごうどう b モッド m | a と b は、m でわった 余りが同じ | |
| いち れい いち いち(2 しんほう) | 右下の (2) は「2 進法で書いた数」という印 | |
| n 進法(しんほう) | ― | n ずつでくり上がる数の書き方 |
1. 約数の個数 ― 素因数分解から数える
基本
(p、q は素数)のとき
例 1 72 の正の約数の個数
72 = 2 × 36
= 2 × 2 × 18
= 2 × 2 × 2 × 9
= 2³ × 3² ← 素因数分解(a = 3、b = 2)
約数の個数 = (3 + 1)(2 + 1)
= 4 × 3
= 12 個
答え: 12 個
もっとくわしく: なぜ (a + 1)(b + 1)? / 書き出して確かめる / 例題
約数は「2 を 0〜3 個、3 を 0〜2 個」選んでかけたもの。2 の選び方 4 通り、3 の選び方 3 通り。
| × | 3⁰ = 1 | 3¹ = 3 | 3² = 9 |
|---|---|---|---|
| 2⁰ = 1 | 1 | 3 | 9 |
| 2¹ = 2 | 2 | 6 | 18 |
| 2² = 4 | 4 | 12 | 36 |
| 2³ = 8 | 8 | 24 | 72 |
4 行 × 3 列 = 12 個。「+1」は 0 個選ぶ(2⁰ = 1) 場合の分。
例 500 = 2² × 5³ → (2 + 1)(3 + 1) = 12 個
例 98 = 2 × 7² → (1 + 1)(2 + 1) = 6 個(1, 2, 7, 14, 49, 98)
約数の総和 も同じ発想で、72 なら (1 + 2 + 4 + 8)(1 + 3 + 9) = 15 × 13 = 195。
2. ユークリッドの互除法 ― 大きな数の最大公約数
基本
大きい数を小さい数でわり、「わる数」と「余り」で同じことをくり返す。余りが 0 になったときの「わる数」が答え。
例 2 221 と 91 の最大公約数
221 = 91 × 2 + 39 ← 221 ÷ 91 = 2 あまり 39
91 = 39 × 2 + 13 ← わる数 91 と余り 39 で同じことをする
39 = 13 × 3 + 0 ← 余り 0。このときのわる数 13 が答え
答え: 13(確かめ: 221 = 13 × 17、91 = 13 × 7)
もっとくわしく: なぜこれでよいの? / 例題をもう 2 つ
221 と 91 の両方をわり切る数は、221 − 91 × 2 = 39 もわり切る。逆に 91 と 39 をわり切る数は、221 = 91 × 2 + 39 もわり切る。
だから「221 と 91 の公約数」=「91 と 39 の公約数」。数がどんどん小さくなるので、最後は答えが見える。
例 143 と 91
143 = 91 × 1 + 52
91 = 52 × 1 + 39
52 = 39 × 1 + 13
39 = 13 × 3 + 0 → 13
例 156 と 84
156 = 84 × 1 + 72
84 = 72 × 1 + 12
72 = 12 × 6 + 0 → 12
つまずきポイント: 答えは最後の 余り 0 ではなく、そのときの わる数。
3. 一次不定方程式 ― ax + by = c の整数解
基本
x = 1, 2, 3, … と順に入れて、y が 整数 になるものを探す。
例 3 3x + 5y = 1 の整数解のうち、x が正で最小のもの
y = (1 − 3x) ÷ 5 ← y について解く
x = 1: (1 − 3) ÷ 5 = −2/5 ← 整数でない
x = 2: (1 − 6) ÷ 5 = −1 ← 整数!
答え: x = 2(y = −1)。確かめ 3 × 2 + 5 × (−1) = 6 − 5 = 1 ✓
もっとくわしく: ほかの解 / 例題
一般解は x = 2 + 5k、y = −1 − 3k(k は整数)。x を 5 増やして y を 3 減らすと、3 × 5 − 5 × 3 = 0 で式の値が変わらない。
| k | x | y | 3x + 5y |
|---|---|---|---|
| −1 | −3 | 2 | −9 + 10 = 1 |
| 0 | 2 | −1 | 6 − 5 = 1 |
| 1 | 7 | −4 | 21 − 20 = 1 |
例 5x + 8y = 2
x = 1: (2 − 5) ÷ 8 → 整数でない
x = 2: (2 − 10) ÷ 8 = −1 → 整数 → x = 2
例 7x + 4y = 1
x = 1: (1 − 7) ÷ 4 = −6/4 → ×
x = 2: (1 − 14) ÷ 4 = −13/4 → ×
x = 3: (1 − 21) ÷ 4 = −5 → ○ → x = 3
4. 余りと合同式
基本
a と b を m でわった余りが同じとき と書く。
便利な性質: 余りどうしを計算してよい(積の余り = 余りの積の余り)。
例 4 7⁴ を 5 でわった余り
7 を 5 でわると余り 2 → 7 ≡ 2 (mod 5)
7⁴ ≡ 2⁴ ← 7 のかわりに余り 2 を使う
= 16
16 を 5 でわると余り 1 → 16 ≡ 1 (mod 5)
答え: 1。7⁴ = 2401 を計算しなくてよい(実際 2401 = 5 × 480 + 1)。
もっとくわしく: 1 回ずつ余りをとる方法 / 例題
大きくなりそうなら、1 回かけるごとに余りにしてよい。
例 3⁵ を 7 でわった余り
3¹ = 3 → 余り 3
3² ≡ 3 × 3 = 9 → 9 ÷ 7 あまり 2
3³ ≡ 2 × 3 = 6 → 余り 6
3⁴ ≡ 6 × 3 = 18 → 18 ÷ 7 あまり 4
3⁵ ≡ 4 × 3 = 12 → 12 ÷ 7 あまり 5
答え 5(確かめ: 3⁵ = 243 = 7 × 34 + 5 ✓)
例 4³ を 9 でわった余り → 64 = 9 × 7 + 1 → 1
つまずきポイント: 数が小さいうちは、そのまま計算して最後にわってもよい。余りは必ず 0 以上 m 未満。
5. n 進法 ― 位取りの底を変える
基本
10 進法は「10 でくり上がる」。2 進法は「2 でくり上がる」。
n 進 → 10 進
各位に n の累乗をかけてたす。右端が の位。
例 5 を 10 進法に
位: 2³ 2² 2¹ 2⁰
数字: 1 0 1 1
かける: 8 4 2 1
8 + 0 + 2 + 1 = 11
答え: 11
10 進 → n 進
n でわり続けて、余りを下から 読む。
例 6 11 を 2 進法に
2 ) 11 余り 1 ↑
2 ) 5 余り 1 │ 下から読む
2 ) 2 余り 0 │
2 ) 1 余り 1 │
0 → 1011
答え: 1011
もっとくわしく: 3 進法・5 進法の例 / 確かめ方
例 → 2 × 3² + 0 × 3 + 1 × 1 = 18 + 0 + 1 = 19
例 → 3 × 5 + 4 × 1 = 19
例 20 を 3 進法に
3 ) 20 余り 2 ↑
3 ) 6 余り 0 │
3 ) 2 余り 2 │
0 → 202
確かめ: 202₍₃₎ を 10 進に戻す → 2 × 9 + 0 + 2 = 20 ✓。変換したら 逆向きに戻して 確かめる。
つまずきポイント: n 進法では数字は 0 〜 n − 1 しか使わない。2 進法に 2 が出てきたら計算ミス。
練習してみよう
- 143 と 91 の最大公約数 → 13
- 156 と 84 の最大公約数 → 12
- 500(= 2² × 5³)の正の約数の個数 → 12
- を 10 進法で → 19
- 13 を 2 進法で(数字だけ)→ 1101
- 3^5 を 7 でわった余り → 5
- 5x + 8y = 2 の整数解で、x が正で最小のときの x → 2
- 7x + 4y = 1 の整数解で、x が正で最小のときの x → 3
もっとくわしく: 練習の途中式
1. 143 = 91 × 1 + 52 → 91 = 52 × 1 + 39 → 52 = 39 × 1 + 13 → 39 = 13 × 3 + 0 → 13
2. 156 = 84 × 1 + 72 → 84 = 72 × 1 + 12 → 72 = 12 × 6 + 0 → 12
3. (2 + 1)(3 + 1) = 12
4. 2 × 9 + 0 × 3 + 1 = 19
5. 13 ÷ 2 = 6 あまり 1、6 ÷ 2 = 3 あまり 0、3 ÷ 2 = 1 あまり 1、1 ÷ 2 = 0 あまり 1 → 下から 1101
6. 3² ≡ 2、3⁴ ≡ 2 × 2 = 4、3⁵ ≡ 4 × 3 = 12 ≡ 5(mod 7)
7. x = 2 で 10 + 8y = 2 → y = −1
8. x = 3 で 21 + 4y = 1 → y = −5
よくある間違い
- × 約数の個数を指数の積 a × b にする → (a + 1)(b + 1)(0 個の場合を数える)
- × 互除法で余りが 0 になったときの「余り」を答える → 0 の直前の わる数
- × n 進 → 10 進で桁の順を逆にする → 右端が n⁰
- × 10 進 → n 進で余りを上から読む → 下から
- × 素因数分解で 72 = 8 × 9 のまま (1 + 1)(1 + 1) とする → 8 と 9 は素数でない。2³ × 3² まで分ける
- × 不定方程式で y が分数のまま x を答える → y が 整数 になる x を探す
練習の前に
互除法、約数の個数、n 進 ↔ 10 進、累乗の余り、不定方程式の最小の正の x が 20 問。答えは整数(n 進法の答えは数字だけ)。
互除法は「わる数と余り」を次の行に持っていく。わからなくなったら、上の「この単元の前に」の単元に戻ろう。