■ユークリッドの互除法(その7)

x・1027-y・712=1なるディオファントス解を求めたい。

(1702,712)=1となることを。ユークリッドの互除法で示したい。

1027=1・712+315

712=2・315+82

315=3・82+69

82=1・69+13

69=5・13+4

13=3・4+1

4=4・1

===================================

これを逆にたどると

315=1027-1・712

82=712-2・315

69=315-3・82

13=82-1・69

4=69-5・13

1=13-3・4

===================================

4=69-5・13を

1=13-3・4に代入すると

1=13-3・(69-5・13)=-3・69+16・13

===================================

13=82-1・69を

1=-3・69+16・13に代入すると

1=-3・69+16・(82-1・69)=16・82-19・69

===================================

69=315-3・82を

1=16・82-19・69に代入すると

1=16・82-19・(315-3・82)=-19・315+73・82

===================================

82=712-2・315を

1=-19・315+73・8269に代入すると

1=-19・315+73・(712-2・315)=73・712-165・315

===================================

315=1027-1・712を

1=73・712-165・315に代入すると

1=73・712-165・(1027-1・712)=-165・1027+238・712

===================================