3章:整数の性質

各種SNSで記事を共有

🔄 最終更新日 2021年7月21日 by takara_semi

3章:整数の性質

本章では「約数と倍数」「ユークリッドの互除法」「整数の性質の活用」について学習する.

第1節 約数と倍数


約数と倍数
(a) 約数・倍数
ある2つの整数 $a,b$ について,ある整数 $k$ を用いて $a,b$ の関係が $a=bk$ と表されるとき,$b$ を $a$ の「約数」($a$ は $b$ で割り切れる),$a$ を $b$ の「倍数」($a$ は $b$ の定数倍)という.約数,倍数は,これまで使用してきた言葉であるが,先述のような数学的な定義ができる(言い換えができる)ことは正確に理解しておくこと.

(b) 倍数の判定法
例えば$31721$という数字が$9$の倍数かどうか,すぐに判断できると便利な場合がある.このような時に,$31721$が$9$で割り切れるかどうかを計算して確かめてもよいのだが「$2$の倍数」「$3$の倍数」「$4$の倍数」「$5$の倍数」「$9$の倍数」であるかどうかの判定法として,以下の関係が知られている.

倍数の判定法

(i) $2$の倍数 $\cdots$ 1の位が偶数 ($0,2,4,6,8$のいずれか)
(ii) $3$の倍数 $\cdots$ 各位の数の和が$3$の倍数
(iii) $4$の倍数 $\cdots$ 下$2$桁が$4$の倍数
(iv) $5$の倍数 $\cdots$ 1の位が $0,5$ のいずれか
(v) $9$の倍数 $\cdots$ 各位の数の和が$9$の倍数


(*) その他の倍数についても,(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)についても証明可能であるが,ここでは省略する.良い演習問題となるので,各自証明してみることが望ましい.


(c) 素因数分解
素因数分解とは「自然数を素数だけの積の形に表す」という数学的操作である.素数とは「2以上の自然数で,正の約数が1とその数自身のみである数」であり,素数でない数は「合成数」という(2以上の自然数で,素数でない数).また因数とは「整数がいくつかの整数の積で表されるとき,そのそれぞれの整数」のことであり,その因数の中で,素数であるものを「素因数」という.また,素因数分解を利用することで,以下のようにして,約数の個数を求めることができる.

約数の個数

自然数 $N$ の素因数分解が $N= p^a \cdot q^b \cdot r^c \cdots \cdots$ となるとき,$N$ の正の約数の個数は

$(a+1)(b+1)(c+1) \cdots \cdots $


(*)これは,次のようにして考えることで証明できる.ある自然数 $N$ が,$N= p^a \cdot q^b \cdot r^c \cdots \cdots$ と素因数分解できるとき,$N$ の約数は $p^{0~a}$, $q^{0~b}$, $r^{0~c}$, $\cdots \cdots$ の積の組合せで表される(例えば $pq,q^br,p^a$ などは $N= p^a \cdot q^b \cdot r^c \cdots \cdots$ の約数であることが分かる).よって,$p$ の取り出し方は $p^0$~$p^a$ の $a+1$ 通り,$q$ の取り出し方は $q^0$~$q^b$ の $b+1$ 通り,$r$ の取り出し方は $r^0$~$r^c$ の $c+1$ 通り,$\cdots$ となるので,その組み合わせを考えると,$(a+1)(b+1)(c+1) \cdots \cdots $通りとなり,約数の個数の関係が導かれた.

最大公約数・最小公倍数
(a) 最大公約数と最小公倍数
ここでは最大公約数と最大公約数について学ぶ.公約数(Common Diviser)とは2つ以上の整数に共通する約数のことであり,特に「最大公約数(GCD:Greatest Common Divisor)」は公約数のうち最大のものをいう.また,公倍数(Common Multiple)とは2つ以上の整数に共通する倍数のことであり,特に「最小公倍数(LCM:Least Common Multiple)」は正の公倍数のうち最小のものをいう.公約数は最大公約数の約数,公倍数は最小公倍数の倍数となることも,それぞれの定義を正確に理解するために確認しておくことが望ましい.

(b) 互いに素
互いに素である2数は以下のように定義される.

互いに素

2つの整数 $a,b$ の最大公約数が$1$であるとき,$a,b$ は「互いに素」であるという.

また「互いに素」な数について,以下の関係が成り立つ.

互いに素な数の関係

$a,b,c$ は整数で,$a,b$ が互いに素であるとき,以下の関係が成り立つ.
① $ac$ が $b$ の倍数であるとき,$c$ は $b$ の倍数となる.
② $a$ の倍数であり,$b$ の倍数でもある整数は,$ab$ の倍数となる.

(c) 最大公約数と最小公倍数の性質
2つの自然数 $a,b$ の最大公約数(GCD:Greatest Common DivisorもしくはGCM:Greatest Common Measure)を $G$,最小公倍数(LCM:Least Common Multiple)を $L$ とする(これは一般的な置き換えであるため,覚えておくと便利である.小文字 $g,l$ で表される場合も多い).この時,以下の性質が成り立つ.

最大公約数と最小公倍数の性質

$a=Ga’$,$b=Gb’$ である場合,以下のことが成り立つ.
(i) $a’,b’$ は互いに素である自然数
(ii) $L=Ga’b’$
(iii) $ab=GL$

上記関係は整数問題を解く上で強力な武器となる場合もあるため,正確に理解しておくことが望ましい.証明は以下の通り.


【(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}


割り算と商・余り
(a) 割り算における商・余り
ここでは整数の割り算と商,余りについて学習する.割り算 $\frac{a}{b}$ より明らかであるが,整数 $a$ と正の整数 $b$ について,$a=bQ+R$,$(0<R<b)$ となる整数 $Q$,$R$ は1通りに定まる.$Q$ を,$a$ を $b$ で割ったときの商(Quotient),$R$ を余り(Remainder)という.$R=0$ のとき,$a$ は $b$ で割り切れるという.他方 $R≠0$ のとき,$a$ は $b$ で割り切れないという.

(b) 余りを用いた整数の分類
余りを用いることで,全ての整数は以下のように分類できる.この考え方は,整数問題を考える上で重要となってくるため,きちんと理解しておくことが望ましい(具体的には,整数についての性質を証明するときに,整数をある正の整数で割ったときの余りで分類すると示しやすいことがある).

余りによる整数の分類

$k$ を整数,$m$ を正の整数とする.
(i) 2で割ったときの余りで分類 : $2k$,$2k+1$ (偶数,奇数)
(ii) 3で割ったときの余りで分類 : $3k$,$3k+1$,$3k+2$
(iii) $m$ で割ったときの余りで分類 : $mk$,$mk+1$,$\cdots \cdots$,$mk+(m-1)$

理解しにくい,イメージしにくい場合は,上記の $k,m$ に値を代入して,実際にすべての整数を表現できていることを一度確認しておくとよい.

(c) 「連続する整数の積」の性質
連続する整数の積には,以下のような性質がある.

連続する整数の積

(i) 連続する2つの整数の積は2の倍数となる.
(ii) 連続する3つの整数の積は6の倍数となる.


【(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の倍数となる.


(d) 和・差・積の余り
ここでは,割り算の余りの性質について,より深く考える.$m$,$k$ を正の整数とする.2つの整数 $a,b$ を $m$ で割った余りを,それぞれ $r$,$r’$ とすると,次のことが成り立つ.(余りは $R,r$ 商は $Q,q$ で表されることが多い.それぞれ英語にしたときの頭文字である.大文字か小文字か(もしくは他のアルファベットを使用するか)は,設問中に特別表記がない場合は,自由に設定してよいが,式の意味を出題者側に伝えやすくするためにも,よく用いられる変数を選んで解答することが望ましい.)

和・差・積の余りの性質

(i) 「$(a+b)$ を $m$ で割った余り」=「$(r+r’)$ を $m$ で割った余り」
(ii) 「$(a-b)$ を $m$ で割った余り」=「$(r-r’)$ を $m$ で割った余り」
(iii) 「$ab$ を $m$ で割った余り」=「$rr’$ を $m$ で割った余り」
(iv) 「$a^k$ を $m$ で割った余り」=「$r^k$ を $m$ で割った余り」


【(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$ で割った余りが等しいことが証明された.


合同式
ここでは,合同式について学習する.$m,k$ は正の整数,$a,b,c,d$ は整数とする.$(a-b)$ が $m$ の倍数であるとき,$a$ と $b$ は $m$ を法として合同であるといい $a≡b \pmod m$ と表す.このような式を「合同式」という.$a≡b \pmod m$ は,$a$ を $m$ で割った余りと $b$ を $m$ で割った「余りが等しい」ことと同じ意味となる.合同式について,次のことが成り立つ.

合同式の性質①

(i) $a≡a \pmod m$
(ii) $a≡b \pmod m$ のとき $b≡a \pmod m$
(iii) $a≡b \pmod m$,$b≡c \pmod m$ のとき $a≡c \pmod m$

合同式の性質②

$a≡c \pmod m$,$b≡d \pmod m$ のとき
(i) $a+b≡c+d \pmod m$
(ii) $a-b≡c-d \pmod m$
(iii) $ab≡cd \pmod m$
(iv) $a^k≡c^k \pmod m$

これらの性質は,先述した「和・差・積の余りの性質」と同様の手順で証明可能である.合同式を利用すれば,一見難解な整数問題を簡単に解くことができる場合もある.

【例】$36^{2021}$ を $7$ で割った余りを求めよ.
【解】$36≡1 \pmod 7$ より
\begin{eqnarray}
36^{2021} &≡& 1^{2021} \pmod 7 \\
&≡& 1 \pmod 7
\end{eqnarray}
となり,答えは1となる.(ポイントは,1と合同になるようにすること.今回は36を7で割った余りが1だったが,そうでない場合でも,1と合同になるよう計算を工夫することで,一見複雑な問題を容易に解ける場合がある.)

第2節 ユークリッドの互除法


割り算と最大公約数
(a) 割り算と最大公約数
ここでは,割り算と最大公約数について学ぶ.割り算と最大公約数の関係について,以下の定理が知られている.この定理は後述する「ユークリッドの互除法」を正確に理解する上で欠かせないものであるので,きちんと理解しておくことが望ましい.

割り算と最大公約数の関係

自然数 $a,b$ について,$a$ を $b$ で割ったときの余りを $r$ とすると

$a$ と $b$ の最大公約数は,$b$ と $r$ の最大公約数に等しい.


【証明】:$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$ の最大公約数に等しいことが証明された.(つまり「割られる数と割る数の最大公約数と割る数とあまりの最大公約数は一致する」ということが示された.)


(b) ユークリッドの互除法
ここでは,ユークリッドの互除法について解説する.2つの自然数 $a,b$ の最大公約数 $G$ を求めるには,次の手順を繰り返せばよい.

ユークリッドの互除法

(I) $a$ を $b$ で割った余りを $r$ とする.
(II) $r=0$ ならば,$b$ が最大公約数 $G$ である.$r≠0$ ならば,$a$ を $b$ で,$b$ を $r$ でおき換えて (I) に戻る.
(I)(II)の操作を繰り返すと,必ず $r=0$ となるため,そのときの割る数が $G$ である.

「割り算と最大公約数の関係」では「割られる数と割る数の最大公約数と割る数とあまりの最大公約数は一致する」ということが示された.言い換えると,「ユークリッドの互除法の操作を何回行っても,割られる数と割る数の最大公約数は一致する」ということになり,ユークリッドの互除法の操作により「割り切れた」とき,そのときの「割る数」が「求める最大公約数」となることは自明だと理解できる.

(c) 互いに素である整数の性質
互いに素である2つの整数について,次のような性質が知られている.

互いに素である整数の性質

2つの整数 $a,b$ が互いに素であるとき,整数 $c$ について $ax+by=c$ を満たす整数 $x, y$ が存在する.


【証明】:「$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$ で割った余りは全て異なる」ことが証明された.


(d) 1次不定方程式と整数解
ここでは,1次不定方程式と整数解について学習する.$a,b,c$ は整数の定数で,$a≠0$,$b≠0$ とする.$x$, $y$ の1次方程式 $ax+by=c$ が成り立つ整数 $x, y$ の組 $(x, y)$ を,この方程式の「整数解」といい,この方程式の整数解を求めることを「1次不定方程式を解く」という.また2つの整数 $a,b$ は互いに素であるとすると,以下の関係が成り立つことが知られてる.

1次不定方程式と整数解

(a) 1次不定方程式 $ax+by=0$ のすべての整数解:$x=bk$, $y=-ak$ ($k$は整数)
(b) 1次不定方程式 $ax+by=c$ のすべての整数解:$ax+by=1$ の整数解の1つを $x=p$, $y=q$ とすると $x=bk+cp$, $y=-ak+cq$ ($k$は整数)

(a)は解を代入して確かめると成立することは自明.(b)について確認すると,$ax+by=1$ の整数解の1つが $x=p$, $y=q$ であることから $ap+bq=1$ となり,両辺に $c$ をかけると $cap+cbq=c$.よって与式 $ax+by=c$ との差をとると $a(x-cp)+b(y-cq)=0$ となり,$a, b$ は互いに素であるため,この方程式が成り立つための条件は $(x-cp)=kb$,$(y-cq)=-ka$($k$は整数) となる.ゆえに1次不定方程式 $ax+by=c$ の整数解は,確かに $x=bk+cp$,$y=-ak+cp$($k$は整数) となることが確かめられた.(つまり1次不定方程式 $ax+by=c$ を解く場合,まずは $ax+by=1$ の整数解 $(p,q)$ を「ユークリッドの互除法」などを用いて求め,与式との差をとった式から,整数解を求めることができることが分かる.)

第3節 整数の性質の活用


分数と小数
(a) 分数と有限小数,循環小数
小数は「有限小数」「無限小数」「循環小数」に分類される.また$m$ を整数,$n$ を正の整数とするとき,分数 $\frac{m}{n}$ は「整数」「有限小数」「循環小数」のいずれかで表すことができる.

(i) 有限小数:小数第何位かで終わる小数.例)$2.25$
(ii) 無限小数:小数点以下が限りなく続く小数.例)$3.1415 \cdots$
(iii) 循環小数:無限小数のうち,ある位以下では数字の同じ並びが繰り返される小数(より詳細には,小数第一位から循環が始まるものを「純循環小数」,小数第二位以降から始まるものを「混合循環小数」 ともいう).例)$0.1111 \cdots = 0.\dot{1}$, $2.5151 \cdots = 2.\dot{5}\dot{1}$, $1.5123123 \cdots = 1.5\dot{1}2\dot{3}$

(b) 有限小数・循環小数で表される分数
分母と分子が互いに素である分数を「既約分数」という.整数でない既約分数 $\frac{m}{n}$ について,次のことが成り立つことが知られている.

小数の分類と素因数

(i) $\frac{m}{n}$ は「有限小数」で表される ⇔ $n$ の素因数は $2, 5$ だけからなる
(ii) $\frac{m}{n}$ は「循環小数」で表される ⇔ $n$ の素因数に $2, 5$ 以外のものがある


【(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)より命題が証明された.


$n$ 進法
(a) $n$ 進法
ここでは $n$ 進法について学習する.各位の数字を上の位から並べて数を表す方法を「位取り記数法」といい,位取りの基礎となる数を「底」という.$n$ を $2$ 以上の自然数とするとき,底を $n$ として数を表す方法を「$n$ 進法」といい,$n$進法で表された数を「$n$進数」という.$n$進数の各位の数字は,$0,1,\cdots , (n-1)$ となる.10進数以外の場合,$n$進数は右下に ${}_{(n)}$をつけて表記する.例えば,2進数 $10011$ は ${10011}_{(2)}$ と表記する.

(b) 底の変換
底の変換方法について,$10$進数を$n$進数で表すには,以下の手順をとればよい.

底の変換

(I) 割る数を $n$ として割り算を行い,商と余りを求める.
(II) 得られた商について同様の割り算を繰り返し,商が$0$になるまで行う.
(III) 得られた余りを逆順に並べる.

手順だけを読むとイメージしにくいかもしれないので,実際に手を動かして計算してみることが望ましい.

(c) $n$進法の小数
$n$ 進法における小数について,小数点以下の位は $\frac{1}{n^1}$ の位,$\frac{1}{n^2}$ の位,$\frac{1}{n^3}$ の位,$\cdots$ となる.$n$進法の小数 (1未満)を$10$進法の小数に直す方法は以下の通り.

$n$進法の小数

(I) $n$ を掛けて得られる整数部分を取り出す.
(II) 小数部分の数に対して $n$ を掛ける.
(III) (II) で得られた積について (I) と (II) を繰り返し,(II)の積が整数になるまで行う.
(IV) (I)で得られた整数部分を順に並べる.

これも手順だけを読むとイメージしにくいかもしれないので,実際に手を動かして計算してみることが望ましい.

(d) $2$進法の四則演算
$2$進法の足し算,引き算,掛け算の計算は,以下が基本となる.割り算は,$10$進法の割り算と同様,掛け算と引き算を組み合わせて行う.

$2$進法の四則演算

(i) 足し算
$0_{(2)} + 0_{(2)} = 0_{(2)}$
$0_{(2)} + 1_{(2)} = 1_{(2)}$
$1_{(2)} + 0_{(2)} = 1_{(2)}$
$1_{(2)} + 1_{(2)} = 10_{(2)}$

(ii) 引き算
$0_{(2)} – 0_{(2)} = 0_{(2)}$
$1_{(2)} – 0_{(2)} = 1_{(2)}$
$1_{(2)} – 1_{(2)} = 0_{(2)}$
$10_{(2)} – 1_{(2)} = 1_{(2)}$

(iii) 掛け算
$0_{(2)} \times 0_{(2)} = 0_{(2)}$
$0_{(2)} \times 0_{(2)} = 0_{(2)}$
$1_{(2)} \times 0_{(2)} = 0_{(2)}$
$1_{(2)} \times 1_{(2)} = 1_{(2)}$


>>目次に戻る

各種SNSで記事を共有
takara_semi
著者紹介 旧帝大卒.自然科学/社会学/教育学/健康増進医学/工学/数学などの分野、および学際的な研究領域に興味があります.

コメントする

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA


このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください

error: