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

整数の性質（約数・ユークリッド・n 進法）― 整数だけの世界のルール

まず、身近なところから

コンピュータは 0 と 1 だけ（2 進法）で数を表す。時計は 60 でくり上がる。暗号は「大きな数を素因数分解するのが難しい」ことを使う。
整数には、実数にはない わり算の余り・約数・倍数 の構造がある。それを扱うのが整数の性質。

約数の個数 ― 素因数分解から数える

N = p^a × q^b（p、q は素数）のとき

$約数の個数 = (a + 1) (b + 1)$

例 1　72 = 2³ × 3² → (3 + 1)(2 + 1) = 12 個
理由: 約数は 2 を 0〜3 個（4 通り）、3 を 0〜2 個（3 通り）選んでかけたもの。4 × 3 = 12。

 2⁰ 2¹ 2² 2³   ← 4 通り
 ×
 3⁰ 3¹ 3²      ← 3 通り      → 12 個

約数の総和も同じ発想で (1 + 2 + 4 + 8)(1 + 3 + 9) = 15 × 13 = 195。

ユークリッドの互除法 ― 大きな数の最大公約数

221 と 91 の最大公約数を素因数分解なしで求める。
大きい数を小さい数でわり、「わる数」と「余り」で同じことをくり返す。余りが 0 になったときの「わる数」が答え。

 221 = 91 × 2 + 39
  91 = 39 × 2 + 13
  39 = 13 × 3 + 0    ← 余り 0。直前のわる数 13 が最大公約数

なぜ？「221 と 91 の公約数」=「91 と 39 の公約数」（221 − 91 × 2 = 39 だから）。数が小さくなるまで続けられる。

一次不定方程式 ― ax + by = c の整数解

例 2　3x + 5y = 1 の整数解
x = 1, 2, … と入れて y が整数になるものを探す: x = 2 のとき 6 + 5y = 1 → y = −1。(2, −1) が 1 組。
一般解は x = 2 + 5k、y = −1 − 3k（k は整数）。x を 5 増やして y を 3 減らすと、3 × 5 − 5 × 3 = 0 でつり合う。

余りと合同式

a と b を m でわった余りが同じとき a ≡ b (mod m) と書く。
便利な性質: 余りどうしを計算してよい（積の余り = 余りの積の余り）。

例 3　7⁴ を 5 でわった余り
7 ≡ 2 (mod 5) → 7⁴ ≡ 2⁴ = 16 ≡ 1。7⁴ = 2401 を計算しなくてよい。

n 進法 ― 位取りの底を変える

10 進法は「10 でくり上がる」。2 進法は「2 でくり上がる」。

n 進 → 10 進

各位に n の累乗をかけてたす。
例 4　1011₍₂₎ = 1 × 8 + 0 × 4 + 1 × 2 + 1 × 1 = 11

 1    0    1    1
 2³   2²   2¹   2⁰
 8 +  0 +  2 +  1 = 11

10 進 → n 進

n でわり続けて、余りを下から 読む。
例 5　11 を 2 進法に

 2 ) 11   余り 1  ↑
 2 )  5   余り 1  │ 下から読む
 2 )  2   余り 0  │
 2 )  1   余り 1  │
      0           → 1011

練習してみよう

143 と 91 の最大公約数 → 143 = 91 + 52、91 = 52 + 39、52 = 39 + 13、39 = 13 × 3 → 13
2² × 5³ の約数の個数 → 3 × 4 = 12
201₍₃₎ を 10 進で → 2 × 9 + 0 + 1 = 19
13 を 2 進法で → 1101
3⁵ を 7 でわった余り → 243 = 7 × 34 + 5 → 5（3² ≡ 2、3⁴ ≡ 4、3⁵ ≡ 12 ≡ 5）
5x + 8y = 2 で x が正で最小 → x = 2: 10 + 8y = 2 → y = −1 → x = 2

よくある間違い

× 約数の個数を指数の積 a × b にする → (a + 1)(b + 1)（0 個の場合を数える）
× 互除法で余りが 0 になったときの「余り」を答える → 0 の直前の わる数
× n 進 → 10 進で桁の順を逆にする → 右端が n⁰
× 10 進 → n 進で余りを上から読む → 下から

練習の前に

互除法、約数の個数、n 進 ↔ 10 進、累乗の余り、不定方程式の最小の正の x が 20 問。答えは整数（n 進法の答えは数字だけ）。
互除法は「わる数と余り」を次の行に持っていく。