【高校数学A】2-2-1 ユークリッドの互除法｜問題集

\(665=551\times1+114\)
\(551=114\times4+95\)
\(114=95\times1+19\)
\(95=19\times5+0\)
よって、最大公約数は\(19\)

\(799=357\times2+85\)
\(357=85\times4+17\)
\(85=17\times5+0\)
よって、最大公約数は\(17\)

\(1771=667\times2+437\)
\(667=437\times1+230\)
\(437=230\times1+207\)
\(230=207\times1+23\)
\(207=23\times9+0\)
よって、最大公約数は\(23\)

\(1606=1111\times1+495\)
\(1111=495\times2+121\)
\(495=121\times4+11\)
\(121=11\times11+0\)
よって、最大公約数は\(11\)

\(42,11\)の互除法を行う。
\(42=11\times3+9\ \)移項すると、\(9=42-11\times3\)
\(11=9\times1+2\ \)移項すると、\(2=11-9\times1\)
\(9=2\times4+1\ \)移項すると、\(1=9-2\times4\)
\(1=9-2\times4\)
\(\ \ =9-(11-9\times1)\times4\)
\(\ \ =9\times5-11\times4\)
\(\ \ =(42-11\times3)\times5-11\times4\)
\(\ \ =42\times5+11\times(-19)\)
よって、求める整数\(x,y\)は
\(x=5,y=-19\)

\(75,13\)の互除法を行う。
\(75=13\times5+10\ \)移項すると、\(10=75-13\times5\)
\(13=10\times1+3\ \)移項すると、\(3=13-10\times1\)
\(10=3\times3+1\ \)移項すると、\(1=10-3\times3\)
\(1=10-3\times3\)
\(\ \ =10-(13-10\times1)\times3\)
\(\ \ =10\times4-13\times3\)
\(\ \ =(75-13\times5)\times4-13\times3\)
\(\ \ =75\times4+13\times(-23)\)
両辺を\(2\)倍して
\(2=75\times8+13\times(-46)\)
よって、求める整数\(x,y\)は
\(x=8,y=-46\)