整数の基本性質
整数の除法
整数の割り算の復習
まず，小学校以来慣れ親しんできた，整数の除法(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$ をそれぞれ，商と余りと呼ぶのである．
約数と倍数
約数と倍数
余りが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の約数であり因数である．
倍数の和と積
- 整数 $a$ の倍数の和は $a$ の倍数であることを示せ．
- 整数 $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である．
最大公約数と最小公倍数
次の各組の多項式の最大公約数と最小公倍数を求めよ． ただし，答えの式は展開しなくてもよい．
- $x^2-1,x+1$
- $x^2-4x+4,x^2-4$
- $x^2+2x-3,x^2+x-6$
- $x^3-27,x^2-2x-3$
- $x^2-1=(x+1)(x-1)$ なので，
- $x^2-4x+4=(x-2)^2,$
- $x^2+2x-3=(x-1)(x+3),$
- $x^3-27=(x-3)(x^2+3x+9),$
最大公約数は $\boldsymbol{x+1}$ ，
最小公倍数は $\boldsymbol{(x+1)(x-1)}$ である．
$x^2-4=(x-2)(x+2)$ なので，
最大公約数は $\boldsymbol{x+2}$ ，
最小公倍数は $\boldsymbol{(x+2)(x-2)^2}$ である．
$x^2-x+6=(x+3)(x-2)$ なので，
最大公約数は $\boldsymbol{x+3}$ ，
最小公倍数は $\boldsymbol{(x-1)(x+3)(x-2)}$ である．
$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\]と因数分解できる．
素因数分解
次の数を素因数分解せよ．
なし
上の例題から経験的に次のことがわかる．
素因数分解の一意性
合成数の素因数分解は，積の順序を考えなければ１通りに定まる．
ある数の約数の個数については次のことが成り立つ．
約数の個数
自然数 $N$ の素因数分解が， $N=p^q\cdot q^b\cdot r^c\cdots$ であるとき， $N$ の正の約数の個数は
\[(a+1)(b+1)(c+1)\cdots\]となる．
素数の個数
素数の個数
素数は無数にあることを示すことができる．
暗記素数が無数にあることの証明
素数を小さい方から並べると
\[2,3,5,7,\cdots\]である．
- $2\cdot3+1,2\cdot3\cdot5+1,2\cdot3\cdot5\cdot7+1$ が素数であることを確認せよ．
- 素数が無数にあることを示せ．
不定方程式の整数解
$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$ の整数解
次の方程式の整数解をすべて求めよ．
積の形の不定方程式
積の形の不定方程式