15
a=3,6=8,c=1 すなわち 3x+8y=1の場合を考察してみよう。
3と8に互除法を用いると
互除法-
8=3・2+2
3=2・1+1
2=1・2+0
余り2について解くと
余りについて解くと
2=8-3・2 ①
1=3-2.1
2
3と8の最大公約数は1であるから、 互除法の余りに1が出てくる。
20 この余り1は, ②, ① の式を使って 3x+8yの形に表すことができる。
13-2・1
② より 13, 2の式で表す。
=3-(8-3・2)・1
① より 2 を 8, 3 の式で表す。
= 3.3+8.(-1)
8, 3 について整理する。
互いに素である整数α, bに互除法を行うと、余りに1が出てきて, 上
25 と同様な方法で1をax+by の形に表すことができる。