3章：整数の性質

---

(＊) その他の倍数についても，(i)～(v)を組み合わせることで判定することができる．例えば「$12$の倍数」かどうかは「$3$の倍数かつ$4$の倍数」かどうかを調べればよいので，与えられた数が(ii)と(iii)の両方を満たすかどうかを調べればよい．

---

(＊＊) (i)～(v)の判定法は容易に証明可能である．(i)は自明，(ii)の証明は次の通り．ある $N$ 桁の整数 $M$ は，1の位の数を $a_1$, 10の位の数を $a_2$, $\cdots$, $10^N$ の位の数を $a^N$ とすることで $M=10^N a_N + \cdots + 10 a_2+a1$ と表すことができる．ここで，$9$を $k$ 個並べた数を $q_k$ とすることで，$10^k a_k=(q_k+1)a_k=q_k a_k+a_k$ という関係より，$M$ は次のように変形できる．

$\begin{eqnarray}
M &=& 10^N a_N+\cdots+10a_2+a1\\
&=& (q_N a_N+a_N)+\cdots+(q_2a_2+a_2)+a1\\
&=& (q_N a_N+\cdots+q_2 a_2)+(a_N+\cdots+a_2+a1)
\end{eqnarray}$

となり，各位の数の和 $(a_N+\cdots+a_2+a1)$ が$3$の倍数であれば，$M$ は$3$の倍数となることが分かる．(iii)～(v)についても証明可能であるが，ここでは省略する．良い演習問題となるので，各自証明してみることが望ましい．

---

【(i)の証明】：以下のようにして証明可能．
$a’$, $b’$ が $1$ より大きな公約数 $d$ を持つと仮定する．$a’$, $b’$を $d$ 割った商をそれぞれ $a”, b”$ とすると $a=Ga’=Gda”$, $b=Gb’=Gdb”$ となり $Gd$ も $a, b$ の公約数となる．$d＞1$ より $Gd＞G$ なので $Gd$ が $G$ より大きな $a, b$ の公約数となるが，これは $a, b$ の最大公約数が $G$ であることに反する．よって，$a’$, $b’$ は $1$ より大きな公約数 $d$ を持たないことがいえる．ゆえに $a’,b’$ は互いに素であることが証明された．

---

【(ii)の証明】：以下のようにして証明可能．
$a, b$ の最小公倍数 $L$ を $a, b$ で割ったときの商(Quotient)をそれぞれ $Q_a, Q_b$ とすると $L$ は

\begin{eqnarray}
L = aQ_a = bQ_b \cdots (*)
\end{eqnarray}

と表すことができる．また $a’b’G$ を $L$ で割ったときの商を $Q_L$ 余り(Remainder)を $R_L$ とすると

\begin{eqnarray}
a’b’G = LQ_L + R_L \cdots (**)
\end{eqnarray}

と表すことができる．このとき $0≦R_L＜L$ である．ここで $a’b’G$ が $L$ で割り切れないと仮定する．このとき $0＜R_L＜L$ となる．したがって $(*)(**)$ より

\begin{eqnarray}
R_L &=& a’b’G – LQ_L\\
&=& a’b’G – (aQ_a)Q_L\\
&=& ab’ – a(Q_aQ_L)\\
&=& a(b’-Q_aQ_L)
\end{eqnarray}

\begin{eqnarray}
R_L &=& a’b’G-LQ_L\\
&=& a’b’G-(bQ_b)Q_L\\
&=& ba’-b(Q_bQ_L)\\
&=& b(a’-Q_bQ_L)
\end{eqnarray}

よって $R_L$ は $a, b$ で割り切れることが分かる．また $(**)$ より $0＜R_L＜L$ であるため $R_L$ は $L$ より小さな $a, b$ の公倍数となる．しかし $L$ が $a,b$ の最大公約数であるため，この結果は仮定に反する．ゆえに $a’b’G$ は $L$ で割り切れることが分かり，$R_L=0$ となる．つまり $(**)$ は

\begin{eqnarray}
a’b’G=LQ_L \cdots (***)
\end{eqnarray}

したがって $(*)$ より

\begin{eqnarray}
a’b’G &=& ab’\\
&=& ba’\\
&=& LQ_L\\
&=& aQ_aQ_L\\
&=& bQ_bQ_L
\end{eqnarray}

であり

\begin{eqnarray}
ab’ &=& aQ_aQ_L \\
ba’ &=& bQ_bQ_L
\end{eqnarray}

ゆえに

\begin{eqnarray}
b’ &=& Q_aQ_L \\
a’ &=& Q_bQ_L \cdots (****)
\end{eqnarray}

したがって $(****)$ より $Q_L$ は $a’, b’$ の公約数であることが分かる．$Q_L≧2$ を仮定すると $Q_L$ は $a’,b’$ の $2$ 以上の公約数となって矛盾．よって

\begin{eqnarray}
Q_L=1 \cdots (*****)
\end{eqnarray}

つまり $(***)(*****)$ より

\begin{eqnarray}
L=a’b’G
\end{eqnarray}

と表せることが証明された．

---

【(iii)の証明】：これは(ii)の関係を用いれば容易に証明できる．$a=Ga’$，$b=Gb’$ であるから

\begin{eqnarray}
ab &=& G \times Ga’b’ \\
&=& GL
\end{eqnarray}

【(i)の証明】：$n$ を整数とすると，連続する2つの整数の積は $n(n+1)$ と表すことができる．また，整数 $n$ は $2k ,2k+1$ ($k$は整数)のいずれかで表される（2で割ったときの余りで分類する）．

(a) $n=2k$ の場合 $n+1 = 2k+1$ であり $n(n+1)$$=2k(2k+1)$$=2 \times (整数)$ となり，連続する2つの整数の積は2の倍数となる．

(b) $n=2k+1$ の場合 $n+1 = 2k+2 =2(k+1)$ であり $n(n+1)$$=2(2k+1)(k+1)$$=2 \times (整数)$ となり，連続する2つの整数の積は2の倍数となる．

(a)(b)より，すべての整数 $n$ について $n(n+1)$ は2の倍数となる．ゆえに，連続する2つの整数の積は2の倍数となる．

---

【(ii)の証明】：証明方針「6の倍数であることを示すために，2の倍数かつ3の倍数である」ということを示す．

(a) 2の倍数であることを示す．
整数 $n$ は $2k,2k+1$($k$は整数)のいずれかで表される（2で割ったときの余りで分類する）．

・$n=2k$ の場合，$n(n+1)(n+2)$$=2k(2k+1)(2k+2)$$=2 \times (整数)$ となり，連続する3つの整数の積は2の倍数となる．

・$n=2k+1$ の場合，$(2k+1)(2k+2)(2k+3)$$=2(k+1)(2k+1)(2k+3)$$=2 \times (整数)$ となり，連続する3つの整数の積は2の倍数となる．

ゆえに，すべての整数 $n$ について $n(n+1)(n+2)$ は2の倍数となる．

(b) 3の倍数であることを示す．
整数 $n$ は $3k,3k+1,3k+2$($k$は整数)のいずれかで表される（3で割ったときの余りで分類する）．

・$n=3k$ の場合，$n(n+1)(n+2)$$=3k(3k+1)(3k+2)$$=3 \times (整数)$ となり，連続する3つの整数の積は3の倍数となる．

・$n=3k+1$ の場合，$(3k+1)(3k+2)(3k+3)$$=3(k+1)(3k+1)(3k+2)$$=3 \times (整数)$ となり，連続する3つの整数の積は3の倍数となる．

・$n=3k+2$ の場合，$(3k+2)(3k+3)(3k+4)$$=3(k+1)(3k+2)(3k+4)$$=3 \times (整数)$ となり，連続する3つの整数の積は3の倍数となる．

ゆえに，すべての整数 $n$ について $n(n+1)(n+2)$ は3の倍数となる．

(a)(b)より $n(n+1)(n+2)$ は2の倍数かつ3の倍数であるため，連続する3つの整数の積は6の倍数となる．

【(i)の証明】：2つの整数 $a，b$ を $m$ で割った余りと商を，それぞれ $r,q$，$r’,q’$とすると，$a，b$ はそれぞれ $a=mq+r$, $b=mq’+r’$ と表せる．よって

\begin{eqnarray}
a+b &=& (mq+r)+(mq’+r’)\\
&=& m(q+q’)+(r+r’)
\end{eqnarray}

ゆえに $a+b≡r+r’ \pmod m$ となり，$a+b$ を $m$ で割った余りと，$r+r’$ を $m$ で割った余りが等しいことが証明された．

---

【(ii)の証明】：2つの整数 $a，b$ を $m$ で割った余りと商を，それぞれ $r,q$，$r’,q’$とすると，$a，b$ はそれぞれ $a=mq+r$, $b=mq’+r’$ と表せる．よって

\begin{eqnarray}
a-b &=& (mq+r)-(mq’+r’)\\
&=& m(q-q’)+(r-r’)
\end{eqnarray}

ゆえに $a-b≡r-r’ \pmod m$ となり，$a-b$ を $m$ で割った余りと，$r-r’$ を $m$ で割った余りが等しいことが証明された．

---

【(iii)の証明】：2つの整数 $a，b$ を $m$ で割った余りと商を，それぞれ $r,q$，$r’,q’$とすると，$a，b$ はそれぞれ $a=mq+r$, $b=mq’+r’$ と表せる．よって

\begin{eqnarray}
ab &=& (mq+r)(mq’+r’)\\
&=& m^2qq’+m(q’r+qr’)+rr’
\end{eqnarray}

ゆえに $ab≡rr’ \pmod m$ となり，$ab$ を $m$ で割った余りと，$rr’$ を $m$ で割った余りが等しいことが証明された．

---

【(iv)の証明】：整数 $a$ を $m$ で割った余りと商を $r,q$ とすると，$a$ は $a=mq+r$ と表せる．よって二項定理を利用して

\begin{eqnarray}
a^k &=& (mq+r)^k\\
&=& (mq)^k+{}_kC_1(mq)^{(k-1)}r \\
& & + \cdots \cdots + {}_kC_{k-1}(mq)r^{(k-1)}+r^k
\end{eqnarray}

ゆえに $a^k≡r^k \pmod m$ となり，$ab$ を $m$ で割った余りと，$rr’$ を $m$ で割った余りが等しいことが証明された．

---

---

【証明】：$a$ を $b$ で割った商と余りを $q,r$, $a, b$ の最大公約数を $G_{ab}$, $b, r$ の最大公約数を $G_{br}$ とすると

\begin{eqnarray}
a &=& bq+r \cdots (*)\\
a &=& G_{ab}a’, b=G_{ab}b’　(a’, b’ は互いに素) \cdots (**)\\
b &=& G_{br}a’, r=G_{br}r’　(b’, r’ は互いに素) \cdots (***)
\end{eqnarray}

$(*)(**)$より

\begin{eqnarray}
a &=& bq+r \\
G_{ab}a’ &=& G_{ab}b’q+r \\
G_{ab}a’-G_{ab}b’q &=& r \\
G_{ab}(a’-b’q) &=& r
\end{eqnarray}

よって $G_{ab}$ は $r$ の約数となる．ゆえに $G_{ab}$ は $r$ と $b$ の公約数となる．$G_{br}$ が $r$ と $b$ の最大公約数であるため

\begin{eqnarray}
G_{ab}≦G_{br} \cdots (****)
\end{eqnarray}

また$(*)(***)$より

\begin{eqnarray}
a &=& bq+r \\
a &=& G_{br}b’q+G_{br}r’ \\
a &=& G_{br}(b’q+r’)
\end{eqnarray}

よって $G_{br}$ は $a$ の約数となる．ゆえに $G_{br}$ は $a$ と $b$ の公約数となる．$G_{ab}$ が $a$ と $b$ の最大公約数であるため

\begin{eqnarray}
G_{br}≦G_{ab} \cdots (*****)
\end{eqnarray}

$(****)(*****)$より

\begin{eqnarray}
G_{br}=G_{ab}
\end{eqnarray}

ゆえに $a$ と $b$ の最大公約数は，$b$ と $r$ の最大公約数に等しいことが証明された．（つまり「割られる数と割る数の最大公約数と割る数とあまりの最大公約数は一致する」ということが示された．）

---

---

【証明】：「$a,b$ が互いに素 ⇔ $ax+by=1$ が整数解 $(x,y)$ を持つ」を証明する（$ax+by=1$ について証明できれば，両辺に $c$ をかけて $a(cx)+b(cy)=c$ として $cx=x’$, $cy=y’$ と置換することで $ax’+by’=c$ についても証明できる）.

(a) まず 「$ax+by=1$ が整数解を持つ ⇒ $a,b$ が互いに素」を証明する.「$ax+by=1$ が整数解を持つならば，$a, b$が互いの素」の命題の対偶は，「$a, b$が互いの素でないならば，$ax+by=1$ は整数解を持たない」となる.これを証明する（対偶が真なら命題も真となるため）．$a,b$ が互いに素ではないので，$a, b$ の公約数を $k$ とすると $a=ck$,$b=dk$ と表せる．すると $ax+by=1$ は $ckx+dky=1$ となるため

\begin{eqnarray}
ckx-1 &=& dky\\
ckx-1 &≡& 0 \pmod k\\
ckx &≡& 1 \pmod k
\end{eqnarray}

左辺は，$k$ の倍数，右辺は $k$ で割って1余る数となる．$k$ の倍数であれば，$k$ で割り切れるため，1余ることはない.したがって，これを満たす整数 $x$ は存在しない．以上より，「$a,b$ が互いの素でないならば，$ax+by=1$ は整数解を持たない」の命題は，真であるので，その対偶である「$ax+by=1$ が整数解を持つならば，$a,b$ が互いの素である」の命題も，真となる.（対偶証明法）

(b) 次に「$a,b$ が互いに素ならば，$ax+by=1$ が整数解を持つ」ことを証明する.

$a,b$ が互いに素であるとき $a, 2a, 3a, 4a \cdots (b-1)a$ を $b$ で割った余りはすべて異なり， $a, 2a, 3a, 4a \cdots (b-1)a$ の中に余りが1となるものが存在する${}^{(*)}$.そこで $ma ≡ 1 \pmod b$（$m$ は正の整数） となる数 $ma$ を考える．$ma$ を $b$ で割った商を $q$ とおくと

\begin{eqnarray}
am=bq+1　(am≡1 \pmod b)
\end{eqnarray}

よって

\begin{eqnarray}
ma-bq=1
\end{eqnarray}

ゆえに $ax+by=1$ は $x=m,y=-q$ の整数解を持つ.

(a)(b)より「$a,b$ が互いに素 ⇔ $ax+by=1$ が整数解 $(x,y)$ を持つ（$a,b$ が互いに素 ⇔ $ax+by=c$ が整数解 $(x,y)$ を持つ）」という関係が証明された．

---

$(*)$ は背理法で証明できる．この「$a$ と $b$ が互いに素なとき $a, 2a, 3a, \cdots, (b-1)a$ を $b$ で割った余りは全て異なる」という定理は非常に有名であるため，理解しておくことが望ましい．

【証明】：$ia$ と $ja$ $(i＞j)$ を $b$ で割った余り $r_{ib}, r_{jb}$ が同じ $(r_{ib}=r_{jb})$ だと仮定し，商をそれぞれ $q_{ib}, q_{jb}$ とすると $(i-j)a$ は

\begin{eqnarray}
(i-j)a &=& ia-ja \\
&=& (bq_{ib}+r_{ib}) – (bq_{jb}+r_{jb})\\
&=& b(q_{ib}-bq_{jb}) + (r_{ib}-r_{jb})\\
&=& b(q_{ib}-bq_{jb})
\end{eqnarray}

となり $(i-j)a$ は $b$ の倍数となるが，$1≦i-j＜b$ かつ $a$ と $b$ は互いに素なのでこれは矛盾する．ゆえに $ia$ と $ja$ $(i＞j)$ を $b$ で割った余り $r_{ib}, r_{jb}$ は異なる．したがって，「$a$ と $b$ が互いに素なとき $a, 2a, 3a, \cdots, (b-1)a$ を $b$ で割った余りは全て異なる」ことが証明された．

---

【(i)の証明】
(a)「$n$ の素因数は $2, 5$ だけからなる ⇒ $\frac{m}{n}$ は有限小数で表される」を証明する．分母 $m$ の素因数は $2，5$ だけからなる場合，$0$ 以上の整数 $a，b$ を用いて $n = 2^a \times 5^b$ と表せる．このとき $\frac{m}{n}$$=\frac{m}{2^a \times 5^b}$$=\frac{2^b \times 5^a \times m}{2^b \times 5^a \times 2^a \times 5^b}$$=\frac{2^a \times 5^b \times m}{(2 \times 5)^a \times (2 \times 5)^b}$$=\frac{2^a \times 5^b \times m}{10^{a+b}}$ となる．$2^a \times 5^b \times m$ は整数なので $\frac{m}{n}$ は有限小数であることが確かめられた．

(b)「$\frac{m}{n}$ は有限小数で表される ⇒ $n$ の素因数は $2, 5$ だけからなる」を証明する．$\frac{m}{n}$ は有限小数で表されことから $\frac{m}{n} \times 10^k$ が整数となるような自然数 $k$ が必ず存在する．（$\frac{m}{n}$ は既約分数であるため）$m$ と $n$ は互いに素なので，$\frac{m}{n} \times 10^k$ が整数となるためには $n$ は $10^k$ つまり $2^k \times 5^k$ の約数である必要がある．ゆえに, 分母 $n$ の素因数は $2, 5$ だけからなることが確かめられた．

(a)(b)より命題が証明された．

---

【(ii)の証明】
(a)「$n$ の素因数に $2，5$ 以外のものがある ⇒ $\frac{m}{n}$ は循環小数で表される」を証明する．分母 $n$ に $2, 5$ 以外の素因数が含まれるとき，その分数は $\frac{m}{10^k}$ の形で表現できない．つまり，$\frac{m}{n} \times 10^k$ が整数となるような自然数 $k$ が存在しないこととなり，$\frac{m}{n}$ は循環小数となることが分かる．

(b)「$\frac{m}{n}$ は循環小数で表される ⇒ $n$ の素因数に $2，5$ 以外のものがある」を証明する．$\frac{m}{n}$ は循環小数で表されことから $\frac{m}{n} \times 10^k$ が整数となるような自然数 $k$ は存在しない．つまり分母 $n$ は $10^k=2^k \times 5^k$ 以外の素因数が必要となる．ゆえに, 分母 $n$ の素因数は $2, 5$ 以外のものがあることが確かめられた．

(a)(b)より命題が証明された．