単純にみえるものほど難しい
整数というのは算数，数学において初期から扱うとても身近な数だし，見た目も綺麗だから複素数を扱うより簡単だと感じるんじゃないかな？
でも実際にはかなり奥深く，考えなければいけないことがたくさんあって，数学を学んでいる多くの人がつまずく分野でもあるんだ。
その原因は，整数特有の表現しにくい性質と，文字での実感のしにくさ。
例えば，2つの整数 $a$ ， $b$ が $a<b$ を満たすと， $a \leqq b-1$ が成り立つ。
( $a=2$ ， $b=3$ のとき， $2<3 \Leftrightarrow 2 \leqq 3-1 <3$ $\Leftrightarrow$ $a \leqq b-1<b$ )
よく考えれば当たり前のことだと気づけるんだけど，瞬時に理解するのは難しいんじゃないかな？
整数に慣れているからこそ当たり前のことを説明するのが難しいし，文字式に慣れているからこそ文字が整数に見えづらいんだ。
$ab=3$ を満たす整数 $a$ ， $b$ は？と聞かれて即答できるかな？
掛けて $3$ になる整数の組は， $(a, b)=(1, 3),(3, 1),(-1, -3),(-3, -1)$ 。
ただ，訓練だと思えばこんなに魅力的な教材はない。
当たり前のことこそ，誰にでも伝わるように説明できるようになるというのは，数学においてとても大事なことだからね。
さらに，整数の問題では，論理的に範囲を絞り具体的に確認していく，という計算一発で解けない問題が多いから，論理的思考力も鍛えられるよ。
数学においては，単純に見えるものほど難しいということを覚えておこう。
この講ではそんな整数の性質を扱うから，すでに知っていることと照らし合わせながら，知識の隙間ができないように注意しよう。
約数と倍数
【定義】
約数，倍数：2つの整数 $a$，$b$ について，ある整数 $k$ を用いて $a=bk$ と表されるとき，$b$ は $a$ の約数であるといい，$a$ は $b$ の倍数であるという。
※ $a=bk$ のとき，$a=(-b) \cdot (-k)$ でもあるから，$b$ が $a$ の約数ならば $-b$ も $a$ の約数である。
公約数：2つ以上の整数について，共通する約数
最大公約数：公約数のうち最大のもの
※最大公約数を gcd (英語の greatest common divisor より)で，値を $g$ で表すことがある。
公倍数：2つ以上の整数について，共通する倍数
最小公倍数：正の公倍数のうち最小のもの
※最小公倍数を lcm (英語の least common multiple より)で，値を $l$ で表すことがある。
※0でない2つ以上の整数の最大公約数は常に正の数であるから，最大公約数，最小公倍数を求めるときは，正の数に限定して考えればよい。
互いに素：2つの整数の最大公約数が $1$ であること ※再掲
【定理】互いに素な2数の性質
$a$，$b$，$c$ は整数で，$a$，$b$ は互いに素であるとすると，次のことが成り立つ。
- $ac$ が $b$ の倍数であるとき，$c$ は $b$ の倍数である。
- $a$ の倍数であり，$b$ の倍数でもある整数は，$ab$ の倍数である。
【定理】最大公約数と最小公倍数の性質
2つの自然数 $a$，$b$ の最大公約数を $g$ ，最小公倍数を $l$ とすると，自然数 $a’$ ， $b’$ を用いて $a=ga’$ ， $b=gb’$ と表され，次のことが成り立つ。
- $a’$，$b’$ は互いに素である。
- $l=ga’b’$
- $ab=gl$
また，公約数は最大公約数の約数，公倍数は最小公倍数の倍数である。
それぞれの言葉は小学校ですでに習っているけど，こうして文字で表されるとどうかな？
焦らなくていいから，自分の中にあるものと結びつけてしっかり覚えよう。
自然数の倍数判定法
その自然数がどの自然数の倍数であるか判定する方法がある。
$2$ の倍数(偶数)や $5$ の倍数は有名だけど，それ以外の数にもあるんだ。
$7$ の倍数の判定法はないけど，関連して $7 \cdot 11 \cdot 13=1001$ というのは3つの連続する素数の積としても有名だよ。
自然数の倍数判定法
- 2の倍数：一の位が偶数
- 3の倍数：各位の数の和が3の倍数
- 4の倍数：下2桁が4の倍数
- 5の倍数：一の位が0または5
- 6の倍数：2の倍数かつ3の倍数
- 8の倍数：下3桁が8の倍数
- 9の倍数：各位の数の和が9の倍数
整除法
【定義】
整除法：除法の原理を前提に，被除数と除数に対する商と剰余を求める演算
※整数 $a$ ， $b$ ， $q$ ， $r$ とすると，「 $a \div b=q$ 余り $r$ 」 $\Leftrightarrow$ 「 $a=bq+r$ 」において， $a$ を被除数， $b$ を除数， $q$ を商， $r$ を剰余という。
※ $r=0$ のとき $a$ は $b$ で割り切れるといい， $r \neq 0$ のとき $a$ は $b$ で割り切れないという。
【定理】自然数に対する除法の原理
与えられた2つの自然数 $a$ および $b \neq 0$ に対して， $a=bq+r$ ( $r<m$ ) が成立するような自然数 $q$ および $r$ が一意的に存在する。
【定理】整数に対する除法の原理
与えられた2つの整数 $a$ および $b \neq 0$ に対して， $a=bq+r$ ( $0 \leqq r<|m|$ ) が成立するような整数 $q$ および $r$ が一意的に存在する。
【定理】剰余の性質
$a=mq+r$，$b=mq’+r’$ とおくと
- $a+b$ を $m$ で割った剰余は，$r+r’$ を $m$ で割った剰余に等しい。
- $a-b$ を $m$ で割った剰余は，$r-r’$ を $m$ で割った剰余に等しい。
- $ab$ を $m$ で割った剰余は，$rr’$ を $m$ で割った剰余に等しい。
- $a^k$ を $m$ で割った剰余は，$r^k$ を $m$ で割った剰余に等しい。
除法と整除法
第6講までは除法の商は分数で被除数と除数の比を表すとしていたけど，剰余を求める除法ももちろんあって，自然数，または，整数の商と剰余を求める除法を整除法というんだ。
小学校で最初に習った割り算は自然数の整除法だったんだよ。
ちなみに，第5講で扱った整式の除法でも使っていたけど，「余り」と「剰余」は同じことだからね。
整除法は定理に基いた演算
整除法というのは除法の一部ではあるんだけど，上の定義にもある通り，四則演算で唯一定理に基づいて行われる演算なんだ。
その定理を剰余の原理といって，被除数，除数に対して剰余の条件を設定すると$(被除数)=(除数) \times (商)+(剰余)$を満たす商と剰余は1通りに決まるというもの。
自然数か整数かによって剰余の条件が違うから注意が必要だよ。
定理の中に「一意的に存在する」という難しい表現があるんだけど，単純に「満たすものは1つ」だと考えよう。
「割り切れない」$\neq$「小数点以下が無限に続く」
「割り切れない」を「小数点以下が無限に続く」という意味で使うことがあるけどそれは間違い。
もちろん「小数点以下が無限に続く」ならば「割り切れない」は正しいんだけど，整除法においては， $3 \div 2=1 余り 1$ となって，これも剰余が $0$ でないから「割り切れない」ということになる。
整除法でなければ $3 \div 2=2.5$ だから「割り切れる」となるからね。
整数の分類
整数の分類
整数を自然数 $m$ で割ったときの剰余に着目すると，すべての整数は整数 $k$ を用いて次のいずれかの形に表される。
$\begin{array}{cccc} mk， & mk+1， & ……， & mk+(m-1) \\ 剰余0 & 剰余1 & …… & 剰余m-1 \end{array}$
すべての整数が偶数と奇数に分けられる，というのは理解していると思うんだけど，整除法の剰余に着目することでその考えを拡張できる。
例えば， $3$ で割った剰余に着目すると，すべての整数を3個のグループに分けられる。
$3m:…, -6, -3, 0, 3, 6, …$ ， $3m+1:…, -5, -2, 1, 4, 7, …$ ， $3m:…, -4, -1, 2, 5, 8, …$
同じように，自然数 $m$ で割った剰余に着目すれば， $m$ 個のグループに分けられるよ。
整数全体を一気に考えるのが難しいような問題では，この方法でグループ分けすることによって解けることがあるんだ。
ユークリッドの互除法
【定理】整除法と最大公約数の性質
自然数 $a$，$b$ について，$a$ を $b$ で割ったときの剰余を $r$ とすると，$a$ と $b$ の最大公約数は，$b$ と $r$ の最大公約数に等しい。
最大公約数は素因数分解することによっても求められるけど，数が大きくなると素因数を探すのが難しくなる。
そこで登場するのがユークリッドの互除法。
これは，上の定理を使うことで，自然数であればどんな2数でも最大公約数を求めることができるんだ。
ユークリッドの互除法
整数 $a$，$b$ の最大公約数を求める。
- $a$ を $b$ で割ったときの剰余を $r$ とする。
- $r=0$ ならば，$b$ が $a$ と $b$ の最大公約数である。
$r>0$ ならば，$a$ を $b$ で，$b$ を $r$ でおきかえて，1に戻る。
この手順を繰り返すと，剰余 $r$ が小さくなり，$r$ が0になって必ず終了する。
合同式
【定義】
$m$ は正の整数，$a$，$b$ は整数とする。
$a$，$b$ が $m$ を法として合同：$a-b$ が $m$ の倍数であること
合同式：$a$，$b$ が $m$ を法として合同を $a \equiv b$ ( $\bmod m$ )と表したもの
※$a$ と $b$ が $m$ を法として合同であるとき，次の関係が成り立つ。
$a \equiv b$ ( $\bmod m$ )
$\Leftrightarrow$ $a-b$ が $m$ の倍数 [$a-b=mk$ ( $k$ は整数)] ：定義
$\Leftrightarrow$ ( $a$ を $m$ で割った剰余) $=$ ( $b$ を $m$ で割った剰余)
【定理】合同式の性質Ⅰ
- $a \equiv a$ ( $\bmod m$ )
- $a \equiv b$ ( $\bmod m$ )のとき $b \equiv a$ ( $\bmod m$ )
- $a \equiv b$ ( $\bmod m$ )，$b \equiv c$ ( $\bmod m$ )のとき $a \equiv c$ ( $\bmod m$ )
※$a \equiv b$ ( $\bmod m$ )，$b \equiv c$ ( $\bmod m$ )を $a \equiv b \equiv c$ ( $\bmod m$ )と書いてもよい。
【定理】合同式の性質Ⅱ
$a \equiv b$ ( $\bmod m$ )，$c \equiv d$ ( $\bmod m$ )のとき，次のことが成り立つ。
- $a+c \equiv b+d$ ( $\bmod m$ )
- $a-c \equiv b-d$ ( $\bmod m$ )
- $ac \equiv bd$ ( $\bmod m$ )
- 自然数 $m$ に対し $a^n \equiv b^n$ ( $\bmod m$ )
整数を扱うときに，除数や商ではなく剰余に着目することで見えてくることがある。
それを効率的に考えられるのが合同式。
上で扱った「整数の分類」の考え方を式化したものなんだ。
2つの整数が同じグループに属することを $=$ ではなく， $\equiv$ を使って表すよ。
合同式自体は中高で習わないんだけど，整数の問題を処理するときに有用だから押さえておこう。
特に「合同式の性質Ⅱ」は，具体的に考えなければ分かりづらかったことが定理化されているよ。
$n$ 進法
【定義】
底：位取りの基礎となる数
$\boldsymbol{n}$ 進法：底を $n$ として数を表す記数法( $n$ は2以上の整数)
$\boldsymbol{n}$ 進数：$n$ 進法で表された数
※$n$ 進数では，その数の右下に${}_{(n)}$ と書く。(10進数は省略する)
※$n$ 進数の各位の数字は0以上 $n-1$ 以下の整数。
小中高の算数，数学では，基本的に数字は0，1，…，8，9の10個で，ある位において数が10になると1つ上の位に繰り上がる10進法を使っている。
なんてややこしい説明をしなくても，今まで普通に使ってきたのが10進法なんだ。
とはいえ，身の回りにも10進法以外の記数法がたくさんある。
例えば，時間は60秒で1分という60進法だったり，パソコンやゲーム機では0～9にA~Fの6つを加えた16進法だったりね。
これらの記数法を総称して $n$ 進法というんだけど，まずは $n$ 進法の位を一般化するとこうなる。
$\boldsymbol{n}$ 進法の位
……， $n^3$ の位， $n^2$ の位， $n^1$ の位， $n^0$ の位， $\frac{1}{n^1}$ の位，$\frac{1}{n^2}$ の位，$\frac{1}{n^3}$ の位，……
10進法であれば，…，1000の位，100の位，10の位，1の位，0.1の位，0.01の位，0.001の位…となり，2進法であれば，…，8の位，4の位，2の位，1の位， $\frac{1}{2}$ の位， $\frac{1}{4}$ の位， $\frac{1}{8}$ の位…となる。
$n$ 進法というのは，この位の数を使うことで相互に変換することができる。
例えば，2進法の $1111_{(2)}$ を10進法に変換すると，
$1111_{(2)}=1 \times 2^3 +1 \times 2^2 +1 \times 2^1 +1 \times 2^0 =8+4+2+1=15=1 \times 10^1 +5 \times 10^0$
となり，逆に，10進法の $1111$ を2進法に変換すると，
$1111=1 \times 2^10 +0 \times 2^9 +0 \times 2^8 +0 \times 2^7 +1 \times 2^6 +0 \times 2^5 +1 \times 2^4 +0 \times 2^3 +1 \times 2^2 +1 \times 2^1 +1 \times 2^0 =10001010111_{(2)}$
となる。
当然だけど， $n$ 進法の $n$ が多いほうが，少ない桁で多くの数字を表すことができるんだ。
ここで，扱われることが多い2進法の計算についてまとめておくね。
2進法の四則計算
2進法の四則計算では，次の計算が基本となる。
- 足し算：$0+0=0$，$0+1=1$，$1+0=1$，$1+1=10$
- 引き算：$0-0=0$，$1-0=1$，$1-1=0$，$10-1=1$
- 掛け算：$0 \times 0=0$，$0 \times 1=0$，$1 \times 0=0$，$1 \times 1=1$
2進法の割り算は，10進法の割り算と同様に，掛け算と引き算を組み合わせて行う。
10進法であれば10になったら繰り上がるけど，2進法だと2で繰り上がるから繰り上がり，繰り下がりが激しくなる。
不安であれば，簡単な例を使って練習してみよう。
2進法のまま計算してみて，計算前後を10進法に直して合っているか確認するといいよ。
ちなみに，2進法を使えば，10本の指で1024まで数えることができるんだ。
右手の親指から順に $2^0$ の位， $2^1$ の位，…と考えると左手の親指は $2^9$ の位になり，指を伸ばしている状態を $0$ ，曲げている状態を $1$ とすればいい。
実際に $1$ から順に指を曲げて試してみてね。
両手で1000以上数えられるってすごくない？
第7講のまとめ
整数って奥深いでしょ？
数としてはシンプルなんだけど，その分考え方や論理の過程が重要になる。
それに，整数に限定しているから他の単元との結びつきがなさそうだけど，実際にはそんなことはない。
問題の種類も豊富だから，いろんな問題にチャレンジしてみよう。
第8項ではここまでの知識を前提に，最初から $=$ の入った式について考えていくよ。