数学と人間の活動(整数)

2つの整数 $a$、$b$ について、$a = bk$ となる整数 $k$ が存在するとき、$b$ は $a$ の約数、$a$ は $b$ の倍数であるといいます。たとえば $12 = 3 \times 4$ なので、$3$ は $12$ の約数、$12$ は $3$ の倍数です。

ある数が何の倍数かは、実際に割らなくても各位の数字から判定できます。テストでも頻出なので、次の判定法は確実に覚えましょう。

3の倍数の判定法が成り立つ理由を、3桁の数で確かめてみましょう。百の位が $a$、十の位が $b$、一の位が $c$ の数は $100a + 10b + c$ と表せます。これを

と変形すると、$3(33a+3b)$ は必ず3の倍数なので、全体が3の倍数になるかどうかは $a+b+c$(各位の数字の和)だけで決まることが分かります。

$2$ 以上の自然数のうち、$1$ とその数自身以外に約数を持たない数を素数といいます($2, 3, 5, 7, 11, \dots$)。自然数を素数だけの積の形に表すことを素因数分解といい、その表し方は積の順序を除いてただ1通りです。素因数分解は、この章のすべての話題の土台になります。

2つの整数に共通な約数を公約数、共通な倍数を公倍数といい、公約数のうち最大のものを最大公約数、正の公倍数のうち最小のものを最小公倍数といいます。最大公約数が $1$ である2つの整数は互いに素であるといいます。

素因数分解ができれば、最大公約数は「共通する素因数を、小さい方の指数だけ集めた積」、最小公倍数は「現れる素因数を、大きい方の指数だけ集めた積」として求められます。

数が大きくなると素因数分解は大変です。そこで活躍するのがユークリッドの互除法です。これは次の原理にもとづきます。

$a$ を $b$ で割った商を $q$、余りを $r$ とする($a = bq + r$)と、$a$ と $b$ の最大公約数は、$b$ と $r$ の最大公約数に等しい。

つまり「大きい2数の最大公約数」を「より小さい2数の最大公約数」の問題にどんどんおき換えられるのです。余りが $0$ になったとき、そのときの割る数が最大公約数です。

$a$、$b$、$c$ を整数の定数とするとき、$ax + by = c$ を満たす整数 $x$、$y$ の組をすべて求める問題を1次不定方程式といいます。解は1組ではなく、無数にあるのが特徴です。

$a$ と $b$ が互いに素のとき、$ax + by = c$ は必ず整数解を持ちます。逆に、$a$ と $b$ の最大公約数が $c$ の約数でないときは、整数解は存在しません(左辺が必ず最大公約数の倍数になるからです)。

右辺が $1$ でない $ax + by = c$ の場合も、まず $ax + by = 1$ の解を1組見つけて両辺を $c$ 倍すれば、$ax + by = c$ の解が1組得られます。また、係数が大きくて解が見つけにくいときは、ユークリッドの互除法の計算を逆にたどると必ず1組の解を作れます(発展問題で扱います)。

私たちが普段使う10進法は、$0$ から $9$ の10種類の数字を使い、10集まるごとに位が1つ上がる記数法です。同じように、$n$ 種類の数字を使い、$n$ 集まるごとに位が上がる表し方を $n$ 進法といい、$n$ 進法で表された数を $1101_{(2)}$ のように書きます。コンピュータの内部では、$0$ と $1$ だけを使う2進法が使われています。

たとえば2進法の $1101_{(2)}$ は、右から順に $1$ の位、$2$ の位、$2^2$ の位、$2^3$ の位を表すので

となります。

小数も同じ考え方で表せます。2進法の小数第1位は $\dfrac{1}{2}$ の位、小数第2位は $\dfrac{1}{2^2}$ の位、… を表します。たとえば

逆に、10進法の小数を2進法に直すには、小数部分に $2$ を掛けて整数部分を取り出す操作を、小数部分が $0$ になるまで繰り返します。取り出した整数部分を上から順に並べたものが2進小数です。