整数の基本性質

整数の除法

整数の割り算の復習

まず,小学校以来慣れ親しんできた,整数の除法(integer division)について復習する.

説明文
説明文

たとえば,右図のような計算により,17を3で割ると,商は5で余りは2とわかる.この関係を式で表すと \[17=3\times5+2\]

となる.

このとき,17を割られる数,3を割る数と呼ぶので,一般的には次のような関係が成り立つ.

\[(割られる数)=(割る数)\times(商)+(余り)\]

また,(割る数) $\gt$ (余り) $\geqq0$ の関係がある.

整数の除法とは何か,つまり整数 $a$ を整数 $b$ で割ったときの商と余りを求めるとはどういうことなのかを きちんと定義すると

\[a=b\cdot Q+r\quad(0\leqq{r}\lt{Q})\]

を満たす整数 $Q$ と $r$ を求めることとなる.そして,この求まった値 $Q$ と $r$ をそれぞれ,商と余りと呼ぶのである.

$\blacktriangleleft$ 普段割り算で行う筆算は,この $Q$ や $r$ を求めるための手段に過ぎない.

約数と倍数

約数と倍数

余りが0になるような割り算を考える. 例えば,12を3で割ると,商は4余りは0となる. このとき,3は12の約数であり,12は3の倍数であるという.

一般には次のように表すことができる.

約数と倍数

2つの整数 $a,b$ が,ある整数 $k$ を用いて

\[a=bk\]

と表せる時, $b$ は $a$ の約数であるといい, $a$ は $b$ の倍数であるという。

文脈によっては約数のことを,因数と呼ぶこともある. 例えば

\[60=3\cdot4\cdot5\]

なので,3や4や5は,60の約数であり因数である.

倍数の和と積

  1. 整数 $a$ の倍数の和は $a$ の倍数であることを示せ.
  2. 整数 $a$ の倍数の積は $a$ の倍数であることを示せ.

整数 $a$ の倍数は,適当な整数 $m,n$ を用いて, $am,an$ と表すことができる.

このとき,倍数の和は

\begin{align} &am+an\\ =&a(m+n) \end{align}

であり, $m+n$ は整数であるから, $a$ の倍数である.

また,倍数の積は

\begin{align} &am\cdot an\\ =&a\cdot amn \end{align}

であり, $amn$ は整数であるから, $a$ の倍数である.

倍数の和と積

ある整数の倍数の和はある数の倍数である.

また,ある整数の倍数の積はある数の倍数である.

割り算の一意性

割り算の一意性

割り算の一意性

なし

最大公約数と最小公倍数

最大公約数と最小公倍数とは何か

最大公約数と最小公倍数とは何か

最大公約数と最小公倍数

2つ以上の整数において,それらに共通する約数を公約数といい,公約数のうち最大のものを最大公約数という.

最大公約数が1であるとき,その2つ以上の整数は互いに素であるという.

また,2つ以上の整数において,それらに共通する倍数を公倍数といい,正の公倍数のうち最小のものを最小公倍数という.

2つの整数 $a$ と $b$ の最大公約数は,英語表記のgreatest common divisorの頭文字をとって $\text{gcd}(a,b)$ などと表す. また,最小公倍数(least common multiple)も同様に, $\text{lcm}(a,b)$ などと表す.

最大公約数や最小公倍数を求めるには,素因数分解を使う.例えば,42と60をそれぞれ素因数分解すると

\begin{align} 42&=2\cdot3\cdot7\\ 60&=2^2\cdot3\cdot5 \end{align}

となる.

これら2つの数に共通する素因数は2と3であり,1はすべての数の約数となるので,公約数はこれら自身と積で組み合わせたもの,すなわち

\[1,2,3,6\]

が公約数となる.最大公約数は6である.

また,これら2つの数を共に因数にもつ $2^2\cdot3\cdot5\cdot7=420$ の倍数が公倍数である.最小公倍数は420である.

最大公約数と最小公倍数

次の各組の多項式の最大公約数と最小公倍数を求めよ. ただし,答えの式は展開しなくてもよい.

  1. $x^2-1,x+1$
  2. $x^2-4x+4,x^2-4$
  3. $x^2+2x-3,x^2+x-6$
  4. $x^3-27,x^2-2x-3$

  1. $x^2-1=(x+1)(x-1)$ なので,
  2. 最大公約数は $\boldsymbol{x+1}$ ,

    最小公倍数は $\boldsymbol{(x+1)(x-1)}$ である.

  3. $x^2-4x+4=(x-2)^2,$
  4. $x^2-4=(x-2)(x+2)$ なので,

    最大公約数は $\boldsymbol{x+2}$ ,

    最小公倍数は $\boldsymbol{(x+2)(x-2)^2}$ である.

  5. $x^2+2x-3=(x-1)(x+3),$
  6. $x^2-x+6=(x+3)(x-2)$ なので,

    最大公約数は $\boldsymbol{x+3}$ ,

    最小公倍数は $\boldsymbol{(x-1)(x+3)(x-2)}$ である.

  7. $x^3-27=(x-3)(x^2+3x+9),$
  8. $x^2-2x-3=(x-3)(x+1)$ なので,

    最大公約数は $\boldsymbol{x-3}$ ,

    最小公倍数は $\boldsymbol{(x-1)(x+3)(x^2+3x+9)}$ である.

公倍数は最小公倍数の倍数

2つ以上の整数の公倍数は最小公倍数の倍数である.

公約数は最大公約数の約数

2つ以上の整数の公約数は最大公約数の約数である.

最大公約数と最小公倍数の積

整数 $a,b$ の最大公約数を $g$ ,最小公倍数を $l$ とすると

\[ab = gl\]

が成り立つ.

互いに素な数の性質

互いに素な数の性質

互いに素な数については,次のような性質がある.

互いに素な数の性質

$a,b$ が互いに素であるとき,

$bc$ が $a$ で割り切れるならば, $c$ が $a$ で割り切れる.

が成り立つ.ただし, $c$ は整数である.

【証明】

$a$ と $b$ は互いに素であるから,最大公約数と最小公倍数の積より, $a$ と $b$ の最小公倍数は $ab$ である.

$bc$ は $b$ の倍数であり,仮定より $a$ の倍数でもあるから, $ab$ の公倍数である.

公倍数は最小公倍数の倍数より, $bc$ は $ab$ の公倍数である.すなわち,適当な整数 $m$ を使って

\[bc = abm\]

と表せる.この両辺を $b$ で割って, $c=am$ ,すなわち $c$ は $a$ で割り切れる.

ユークリッドの互除法

ユークリッドの互除法

最大公約数を求めるには素因数分解を行えばよいが, $1961$ のように大きな数を素因数分解するのは難しい( $1961=37\cdot53$ ).

素因数分解しにくい大きな数の最大公約数を求めるには,次の定理を使うと良い.

ユークリッドの互除法

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

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

すなわち

\[\text{gcd}(a,b)=\text{gcd}(b,r)\]

が成り立つ.

暗記ユークリッドの互除法

ユークリッドの互除法を証明せよ.

例として1071と1029の最大公約数を求めてみよう.

1071を1029で割ると,商は1余りは42,すなわち

\[1071=1029\cdot1+42\]

となるので,1071と1029の最大公約数は,1029と42の最大公約数と等しい. ここで得られた,1029と42に関して,再び割り算を行うと

\[1029=42\cdot24+21\]

となるので,1029と42の最大公約数は,42と21の最大公約数と等しい.同様にして

\[42=21\cdot2+0\]

となるので,42と21の最大公約数は21であることがわかる.すなわち,1071と1029の最大公約数は21である.

ユークリッドの互除法の利用

なし

素数

素数とは何か

素数とは何か

素数

2以上の自然数で,正の約数が1とその数自体のみである数を,素数という.

例えば,次のような数はみな素数である.

\[2,3,5,7,11,13,17\]

吹き出し無題

1は素数に含まれないので注意しよう.

合成数

2以上の自然数で素数でないものを,合成数という.

例えば,14や60は

\begin{align} 14&=2\cdot7\\ 60&=3\cdot4\cdot5 \end{align}

なので,合成数である.

素数の性質

素数の性質

素数の性質

$a,b$ を整数, $p$ を素数とする時

$ab$ が $p$ で割り切れるならば, $a$ または $b$ が $p$ で割り切れる

暗記素数の性質

素数の性質を証明せよ.

$a$ と $p$ の最大公約数は $p$ の約数であるから, $1$ または $p$ である.

もし,最大公約数が $p$ ならば, $a$ は $p$ で割り切れる.

もし,最大公約数が $1$ ならば,互いに素な数の性質より, $b$ が $p$ で割り切れる.

よって, $a,b$ のうち、少なくとも1つは $p$ で割り切れる.

素因数分解

素因数分解

素数である因数素因数といい,自然数を素数だけの積の形で表すことを素因数分解するという.

例えば,60は

\[60=2^2\cdot3\cdot5\]

と因数分解できる.

素因数分解

次の数を素因数分解せよ.

上の例題から経験的に次のことがわかる.

素因数分解の一意性

合成数の素因数分解は,積の順序を考えなければ1通りに定まる.

ある数の約数の個数については次のことが成り立つ.

約数の個数

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

\[(a+1)(b+1)(c+1)\cdots\]

となる.

素数の個数

素数の個数

素数は無数にあることを示すことができる.

暗記素数が無数にあることの証明

素数を小さい方から並べると

\[2,3,5,7,\cdots\]

である.

  1. $2\cdot3+1,2\cdot3\cdot5+1,2\cdot3\cdot5\cdot7+1$ が素数であることを確認せよ.
  2. 素数が無数にあることを示せ.

不定方程式の整数解

$ax+by=0$ の整数解

$ax+by=0$ の整数解

$2x+3y=0$ の整数解を求めてみよう.

$x,y$ を整数解とすると

\[2x=-3y\]

が成り立つ. $3y$ は3の倍数であるから, $2x$ も3の倍数である.

2と3は互いに素であるから,互いに素な数の性質より, $x$ は3の倍数であり,適当な整数 $k$ を用いて, $x=3k$ と表される.これを, $2x=−3y$ に代入すると

\begin{align} &2\cdot3k=-3y\\ \Leftrightarrow&y=-2k \end{align}

となるから,方程式の解は $x=3k,y=−2k$ と表される.

逆に,この形で表される整数 $x,y$ の組みは,方程式の解となる.

以上より,方程式の整数解は $x=3k,y=−2k$ となる.

一般に次のことが成立する.

$ax+by=0$ の整数解

$a,b$ を互いに素な整数とするとき, $ax+by=0$ を満たす整数解は

\[x=bk,y=−ak(kは整数)\]

である.

$ax+by=1$ の整数解

ax+by=1の整数解

次に,方程式 $2x+3y=1$ を満たす整数解を求めてみよう.

この場合,方程式 $2x+3y=1$ を満たす整数解のうち1つが発見すれば, $ax+by=0$ の整数解の問題に帰着できる.

暗記$ax+by=1$ の整数解

方程式 $2x+3y=1$ を満たす整数解を求めよ.

\[2x+3y=1\tag{1}\label{ax+by=1noseisukai1}\]

を満たす整数解として, $x=−1,y=1$ がある.つまり

\[2\cdot(-1)+3\cdot1=1\tag{2}\label{ax+by=1noseisukai2}\]

$\eqref{ax+by=1noseisukai1}-\eqref{ax+by=1noseisukai2}$ より

\begin{align} &2\{x-(-1)\}+3\{y-1\}=0\\ \Leftrightarrow&2(x+1)+3(y-1)=0\tag{3}\label{ax+by=1noseisukai3} \end{align}

2と3は互いに素であるから, $ax+by=0$ の整数解より $\eqref{ax+by=1noseisukai3}$ のすべての整数解は

$x+1=3k,y−1=−2k(kは整数)$ と表せる.

よって, $\eqref{ax+by=1noseisukai1}$ のすべての整数解は

\[x=3k−1,y=−2k+1(kは整数)\]

となる.

$ax+by=1$ の整数解

次の方程式の整数解をすべて求めよ.

積の形の不定方程式

積の形の不定方程式