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

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

互除法に現れる計算を、行列を使って書き直すと

[1027]=[1,1][712]

[ 712] {1,0][315]

[1027]=[1,1][2,1][315]

[ 712] {1,0][1,0][ 82]

[1027]=[1,1][2,1][3,1][82]

[ 712] {1,0][1,0][1,0][69]

[1027]=[1,1][2,1][3,1][1,1][69]

[ 712] {1,0][1,0][1,0][1,0][13]

[1027]=[1,1][2,1][3,1][1,1][5,1][13]

[ 712] {1,0][1,0][1,0][1,0][1,0][ 4]

[1027]=[1,1][2,1][3,1][1,1][5,1][3,1][4]

[ 712] {1,0][1,0][1,0][1,0][1,0][1,0][1]

[1027]=[1,1][2,1][3,1][1,1][5,1][3,1][4,1][1]

[ 712] {1,0][1,0][1,0][1,0][1,0][1,0][1,0][0]

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝