ユークリッドの互除法では２つの正整数ｍ，ｎがあるとき，その最大公約数ｄとの間で

　　ａｍ＋ｂｎ＝ｄ

を成り立たせることができることを示している．

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

［１］ｍ＝１７６９，ｎ＝５５１

　　１７６９÷５５１＝３・・・１１６

　　５５１÷１１６＝４・・・８７

　　１１６÷８７＝１・・・２９

　　８７÷２９＝３・・・０

　　５・１７６９−１６・５５１＝２９

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