整数の性質の練習問題

考え方

2つの数の最大公約数を、ユークリッドの互除法で素早く求められるようになります。タイルや板の割り付け、同じ数ずつの箱詰め、分数の約分、コンピュータの2進法の理解に役立ちます。

最大公約数

2つの数の両方をわり切る数（公約数）のうち、最も大きいものです。

ユークリッドの互除法

わり算の余りをくり返し求めて、最大公約数を見つける方法です。

不定方程式

$3x + 5y = 1$ のように、解が1組に決まらない方程式です。整数の解を探します。

n 進法

n ごとに位が1つ上がる数の表し方です。コンピュータは2進法を使います。

横 132 cm、縦 48 cm の板に、同じ大きさの正方形のタイルをすき間なく敷きつめるとき、タイルの1辺は縦と横の両方をわり切る長さ（公約数）でなければなりません。できるだけ大きいタイルなら、最大公約数です。

大きい数では素因数分解が大変なので、わり算をくり返します。132 を 48 でわると余り 36、48 を 36 でわると余り 12、36 を 12 でわると余り 0 です。余りが 0 になったときのわる数 12 が最大公約数です。

なぜこれでよいかは図で分かります。長方形から短い辺を1辺とする正方形をできるだけ切り取ると、残りの長方形も同じタイルで敷きつめられるはずです。これをくり返して最後に余りなく並んだ正方形が、全体を敷きつめられる最大のタイルです。

互除法を逆にたどると、$ax + by =$（最大公約数）を満たす整数 x, y が見つかり、不定方程式を解く手がかりになります。また n 進法では、各位が $1, n, n^{2}, \ldots$ を表します。2進法の $1011_{(2)}$ は $8 + 0 + 2 + 1 = 11$ です。

ポイント

$a = bq + r$ のとき、（a と b の最大公約数）=（b と r の最大公約数）

余りが 0 になったときのわる数が最大公約数

最大公約数 × 最小公倍数 = $a \times b$

n 進法: $abc_{(n)} = a \times n^{2} + b \times n + c$

解き方の手順

1. 大きい数を小さい数でわり、余りを求めます。
2. 「わる数」を「余り」でわる、をくり返します。
3. 余りが 0 になったときの「わる数」が最大公約数です。
4. 文章題では、最大公約数（いちばん大きい共通の長さ）を聞かれているのか、最小公倍数（いちばん小さい共通の倍数）を聞かれているのかを確かめます。