最大公約数を表す式
177 と 52 に互除法の計算を行うと, 次のようになる。
互除法
177=52·3+21
移項すると 21=177-52·3
52=21·2+10
移項すると 10=52-21·2
5
21=10·2+1
移項すると
1=21-10-2
10=1·10+0
よって、177 と 52 の最大公約数は1である。
上の互除法の計算を利用すると, 最大公約数1を, 177 と 52 で表すこ
10 とができる。 ③, ②, ① の式から
1=21-10-2
10 に2の右辺を代入
=21-(52-21.2).2
=215+52-G2)
21に0の右辺を代入
=(177-52-3).5+52·(-2)
よって
1=177·5+52 (117)
このように,互除法の計算を利用すると, 2つの整数a, bの最大公約
数gを,適当な整数p, qを用いて g=ap+bqと表すことができる。
特に, aとbが互いに素であるならば,
ap+bq=1
を満たす整数p、 gが存在する。 両辺に整数cを掛けると
a(cp)+6(cq)=c
このことから, 次のことがいえる。
第3章