質問＜２７９７＞２００５／１２／３０
from=yasu
「ユークリッドの互助法」

(1)① a,b∈Nに対し,aをbで割った余りをrとする。
　　　次を示せ。

　　　　1°　r=0⇒(a,b)=b
　　　　2°　r≧1⇒(a,b)=(b,r)

　 ② １８ｘ－４３ｙ＝１を満たす整数(x,y)を全て求
　　　めよ。

★希望★完全解答★

お便り２００６／１／４
from=風あざみ

①の(a,b)はaとbの最大公約数ですね。
そう思って解答します。

①の1.の解答
「rは0ということはaはbで割り切れる。
bはbで割り切れるから、bはaとbの公約数

公約数≦最大公約数だからb≦(a,b)･･･☆

bはbより大きな自然数では割り切れない。
実際、bをbより大きな自然数mで割ると
b=0*m+bとなるので、bはmで割り切れません。
したがって、(a,b)＞bとはなりえない。
よって、(a,b)≦b･･･★

☆と★より(a,b)=bが示された。 」

①の2.の解答
「aをbで割った商をqとしますと
a=bq+rと書くことができます。

(a,b)=d、(b,r)=eとおきます
a=da'、b=db'=e=b"、c=ec'と書けます。

r=a-bq=d*(a'-b'q)だからrはdで割り切れる。
b=d*b'だから、dはbとrの公約数でもある

公約数≦最大公約数だからd≦eとなる･･･●

a=bq+r=e*(b"q+r')だからaはeで割り切れる
b=e*b"だからeはaとbの公約数でもある

公約数≦最大公約数だからe≦dとなる。･･･◎

●と◎よりd=eとなります。
よって、(a,b)=(b,r)がいえました。」

②
18x-43y=1･･･◆
18*12-43*5=1･･･◇
式◆-式◇を計算すると
18(x-12)-43(y-5)=0
18(x-12)=43(y-5)･･･□
ですから43(y-5)が18で割り切れる
43と18は互いに素ですから、y-5が18で割り切れる。
y-5=18k･･･■
(kは任意の整数)と書ける
■を□に代入して整理すると
x=43k+12

よって18x-43y=1を満たす任意の整数(x,y)は任意の整数kをとると、
(43k+12,18k+5)と書ける。