整数の性質(約数・ユークリッド・n進法)

整数の性質(約数・ユークリッド・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 モッド ma と 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⁰ = 13¹ = 33² = 9
2⁰ = 1139
2¹ = 22618
2² = 441236
2³ = 882472

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 で式の値が変わらない。

kxy3x + 5y
−1−32−9 + 10 = 1
02−16 − 5 = 1
17−421 − 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 が出てきたら計算ミス。

練習してみよう

  1. 143 と 91 の最大公約数 → 13
  2. 156 と 84 の最大公約数 → 12
  3. 500(= 2² × 5³)の正の約数の個数 → 12
  4. を 10 進法で → 19
  5. 13 を 2 進法で(数字だけ)→ 1101
  6. 3^5 を 7 でわった余り → 5
  7. 5x + 8y = 2 の整数解で、x が正で最小のときの x → 2
  8. 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

よくある間違い

練習の前に

互除法、約数の個数、n 進 ↔ 10 進、累乗の余り、不定方程式の最小の正の x が 20 問。答えは整数(n 進法の答えは数字だけ)。
互除法は「わる数と余り」を次の行に持っていく。わからなくなったら、上の「この単元の前に」の単元に戻ろう。