ユークリッドの互除法
【ユークリッドの互除法】
自然数\(a\)を自然数\(b\)で割ったときの商を\(q\)、余りを\(r\)とする。
\(a=bq+r\)
このとき、
・\(a,b\)の最大公約数
・\(b,r\)の最大公約数
は一致する。
解法の手順は、
(1)\(a\)を\(b\)で割った余り\(r\)を求める。
(2)このときの割った数\(b\)を余り\(r\)で割る。
(3)これを繰り返して、割り切れるまで割る。
(4)割り切れたときの割った数が最大公約数になる。
【例題】次の最大公約数を求めなさい。
(1)\(260,117\)
\(260=117\times2+26\)
\(117=26\times4+13\)
\(26=13\times2+0\)
よって、最大公約数は\(13\)
(2)\(391,299\)
\(391=299\times1+92\)
\(299=92\times3+23\)
\(92=23\times4+0\)
よって、最大公約数は\(23\)
(3)\(1914,858\)
\(1914=858\times2+198\)
\(858=198\times4+66\)
\(198=66\times3+0\)
よって、最大公約数は\(66\)
互除法の活用
【例題】次の等式を満たす整数\(x,y\)の組を\(1\)つ求めなさい。
(1)\(23x+17y=1\)
\(23,17\)の互除法を行う。
\(23=17\times1+6\ \)移項すると、\(6=23-17\times1\)
\(17=6\times2+5\ \)移項すると、\(5=17-6\times2\)
\(6=5\times1+1\ \)移項すると、\(1=6-5\times1\)
\(1=6-5\times1\)
\(\ \ =6-(17-6\times2)\times1\)
\(\ \ =6\times3-17\)
\(\ \ =(23-17\times1)\times3-17\)
\(\ \ =23\times3+17\times(-4)\)
よって、求める整数\(x,y\)は
\(x=3,y=-4\)
(2)\(51x+19y=3\)
\(51,19\)の互除法を行う。
\(51=19\times2+13\ \)移項すると、\(13=51-19\times2\)
\(19=13\times1+6\ \)移項すると、\(6=19-13\times1\)
\(13=6\times2+1\ \)移項すると、\(1=13-6\times2\)
\(1=13-6\times2\)
\(\ \ =13-(19-13\times1)\times2\)
\(\ \ =13\times3-19\times2\)
\(\ \ =(51-19\times2)\times3-19\times2\)
\(\ \ =51\times3+19\times(-8)\)
両辺を\(3\)倍して
\(3=51\times9+19\times(-24)\)
よって、求める整数\(x,y\)は
\(x=9,y=-24\)