ユークリッドの互除法
2つ以上の整数に共通な約数を公約数といい，公約数のうち最大のものを最大公約数（G.C.M）といいました。最大公約数を求める方法に「ユークリッドの互除法」というのがあります。
AをBで割ったときの余りをRとするとき
AとBの最大公約数＝BとRの最大公約数
|
（例1）A＝7854，B＝2261の最大公約数を求めよ。
AとBの最大公約数を (A，B) とすると
7854÷2261＝3．．．1071 ∴ (7854，2261)＝(2261，1071)
2261÷1071＝2．．． 119 ∴ (2261，1071)＝(1071， 119)
1071÷ 119＝9．．． 0 ∴ (1071， 119)＝ 119
∴ 7854と2261の最大公約数は119
この計算を簡略化したのが右図になります。
このユークリッドの互除法から，最大公約数に関する次のような性質を導き出すことができます。
2つの自然数A，Bの最大公約数をGとするとき
AX＋BY＝G
を満たす整数X，Yが存在する。特にA，Bが互いに素ならば AX＋BY＝1
|
（例2）2261X＋7854Y＝119となる整数X，Yを求めよ。
（例1）のユークリッドの互除法の計算から
7854＝2261×3＋1071 ∴ 1071＝7854−2261×3・・・@
2261＝1071×2＋ 119 ∴ 119＝2261−1071×2・・・A
@Aより
119＝2261−1071×2
＝2261−(7854−2261×3)×2
＝2261×7＋7854×(−2)
∴ X＝7，Y＝−2