最大公約数の性質


$ここでは、自然数 \ a,\ b\ の最大公約数を \ (a,\ b)\ と表すことにします。$

$\quad 定理 \ 1 \quad (ユークリッドの互除法)$

$\qquad a > b \ \ のとき \quad a\ を \ b\ で割った余りを \ r\ とすると \quad (a,\ b)=(b,\ r)$


$証明$

$(a,\ b)=g_1,\quad (b,\ r)=g_2 \quad とおく$

$(1)\ \ g_1 \ は \ g_2 \ の約数であること$

$\quad g_1\ は \ a\ と \ b\ の公約数だから \quad a=g_1k,\ \ b=g_1l \ \ (k,\ l\ は整数)\ \ とおける。$

$\quad また、a\ を \ b\ で割った商を \ q\ とすると除法の原理より \quad a=bq+r \ \ (0 \leqq r < b) \ \ とおける。$

$\quad r=a-bq=g_1k-g_1lq=g_1(k-lq) \quad より \quad g_1 \ は \ r\ の約数である。$

$\quad g_1\ は \ b\ の約数でもあるから、b\ と \ r\ の公約数となる。$

$\quad g_2\ は \ b と \ r\ の最大公約数だから、g_1\ は \ g_2\ の約数である。ゆえに \quad g_1 \leqq g_2$


$(2)\ \ g_2 \ は \ g_1 \ の約数であること$

$\quad g_2\ は \ b\ と \ r\ の公約数だから \quad b=g_2m,\ \ r=g_2n \ \ (m,\ nは整数)\ \ とおける。$

$\quad a=bq+r =g_2mq+g_2n=g_2(mq+n) \quad より \quad g_2 \ は \ a\ の約数である。$

$\quad g_2 \ は \ b\ の約数でもあるから、a\ と \ b\ の公約数となる。$

$\quad g_1\ は \ a と \ b\ の最大公約数だから、g_2\ は \ g_1\ の約数である。ゆえに \quad g_2 \leqq g_1$


$(1),(2)\ より \quad g_1=g_2$


$補足　ユークリッドの互除法による最大公約数の求め方$

$\quad a\ を \ b\ で割った余りを \ r_1\ とすると \quad 0 \leqq r_1 < b \quad で \quad (a,b)=(b,r_1)$

$\quad b\ を \ r_1\ で割った余りを \ r_2\ とすると \quad 0 \leqq r_2 < r_1 \quad で \quad (b,r_1)=(r_1,r_2)$

$\quad r_1\ を \ r_2\ で割った余りを \ r_3\ とすると \quad 0 \leqq r_3 < r_2 \quad で \quad (r_1,r_2)=(r_2,r_3)$

$\hspace{5em} \vdots $

$r_1 > r_2 > r_3 > \cdots \geqq 0 \quad であるから \quad 　r_{n+1}=0 \ \ となる \ n\ が存在する。$

$このとき、r_n=(r_{n-1},r_n)=\cdots =(r_1,r_2)=(b,r_1)=(a,b)$

$すなわち、割り切れたときの除数が最大公約数となる。$

$例 \quad 999\ と \ 370\ の最大公約数$

$\quad 999=370 \times 2 + 259$
$\quad 370=259 \times 1 +111$
$\quad 259=111 \times 2 +37$
$\quad 111=37 \times 3$

$\quad よって \quad (999,370)=37$


$\quad 定理 \ 2 \quad 任意の整数 \ k\ について \quad (a,\ ka+b)=(a,\ b)$


$証明$

$(1)\ \ (a,\ ka+b) \ は \ (a,\ b)\ の約数であること$

$\quad (a,\ ka+b)=d \quad とすると \quad a=ld, \quad ka+b=md \ \ (l,\ m\ は整数)\ とおける。$

$\quad kld+b=md \quad より \quad b=(m-kl)d \quad となって \ d\ は \ b\ の約数である。$

$\quad もともと\ d\ は\ a\ の約数だから \quad d\ は\ a,\ b\ の公約数となり$

$\quad したがって \quad d\ は \ (a,\ b)\ の約数である。ゆえに \quad d \leqq (a,\ b)$


$(2)\ \ (a,\ b)\ は \ (a,\ ka+b)\ の約数であること$

$\quad (a,\ b)=e \quad とおくと \quad a=pe,\ \ b=qe \ \ (p,\ q\ は整数) \ とおける。$

$\quad ka+b=kpe+qe=(kp+q)e \quad となって \quad e\ は \ \ ka+b\ \ の約数である。$

$\quad もともと \ e\ は \ a\ の約数だから \quad e\ は \ a \ と \ ka+b \ の公約数となり$

$\quad したがって \quad e\ は \ (a,\ ka+b)\ の約数である。ゆえに \quad (a,\ b) \leqq d$


$(1),(2)\ より \qquad (a,\ ka+b)=(a,\ b)$


$\quad 定理 \ 3 \quad 3数の最大公約数 \qquad (a,\ b,\ c)=((a,\ b),\ c)=(a,\ (b,\ c))$


$((a,\ b),\ c)=(a,\ b,\ c)\ \ を示すが、(a,\ (b,\ c))=(a,\ b,\ c)\ \ も全く同様です。$

$証明$

$\quad (a,\ b)=g_1,\ \ (g_1,\ c)=g_2,\ \ (a,\ b,\ c)=g \quad とする。$

$(1)\ \ ((a,\ b),\ c)\ は \ (a,\ b,\ c)\ \ の約数であること$

$\quad g_2\ は \ g_1\ と \ c\ の公約数だから \quad g_1=g_2k,\ \ c=g_2l \ \ (k,\ l\ は整数)\ \ とおける。$

$\quad また、g_1 \ は \ a\ と \ b\ の公約数だから \quad a=g_1m,\ \ b=g_1n \ \ (m,\ n\ は整数)\ \ とおける。$

$\quad a=(g_2k)m=g_2(km),\quad b=(g_2k)n=g_2(kn),\quad c=g_2l \quad となるから$

$\quad g_2\ は \ a,\ b,\ c\ の公約数となり、したがって \quad g\ の約数である。ゆえに \quad g_2 \leqq g$


$(2)\ \ (a,\ b,\ c)\ \ は \ ((a,\ b),\ c)\ \ の約数であること$

$\quad g\ は \ a,\ b,\ c\ の公約数だから、a,\ b\ の公約数、すなわち \quad g_1\ の約数である。$

$\quad また、g\ は \ c\ の約数でもあるので、g_1\ と \ c\ の公約数となり、$

$\quad (g_1,c)=g_2 \ の約数である。ゆえに \quad g \leqq g_2 $


$(1),(2)\ より \quad g=g_2 \quad すなわち \quad (a,\ b,\ c)=((a,\ b),\ c)$


ページの先頭へ↑




メインメニュー　に戻る