最大公約数と最小公倍数
最大公約数と最小公倍数とは何か
最大公約数と最小公倍数とは何か
最大公約数と最小公倍数
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である．
ユークリッドの互除法の利用
なし