2つの自然数a,bをa≦bとし, bをaで割った余りをr[1]とすると, 【a,bの最大公約数】＝【b,r[1]の最大公約数】
が成り立ちます（これは証明できます）、
同じようにbをr[1]で割ってその余りをr[2]とすると, 【b,r[1]の最大公約数】＝【r[1],r[2]の最大公約数】
同じようにr[1]をr[2]で割ってその余りをr[3]とすると, 【r[1],r[2]の最大公約数】＝【r[2],r[3]の最大公約数】
という感じになります。これを繰り返せば、最終的に r[n]=r[n+1]となるようなr[n]が現れますが,【a,bの最大公約数】＝【b,r[1]の最大公約数】＝【r[1],r[2]の最大公約数】＝…＝【r[n],r[n+1]の最大公約数】=r[n]となるので, r[n]＝【a,bの最大公約数】となります。
このとき, r[1]>r[2]>r[3]>…>r[n]となります。
こうやってどんどん最大公約数を絞っていくのがユークリッドの互除法の仕組みです。
よって、a,bが互いに素だとa,bの最大公約数が1となるので、r[n]=【a,bの最大公約数】となるので、ユークリッドの互除法を繰り返せばいつかはr[n]=1が出てきます。
このとき、a,b,r[1]の関係式、b,r[1],r[2]の関係式、r[1],r[2],r[3]の関係式、…、r[n-2],r[n-1],r[n]=1 の関係式を変形して
1をr[n-2]とr[n-1]の式で、 r[n-2]をr[n-4]とr[n-3]の式で、 r[n-1]をr[n-3]とr[n-2]の式で、というふうに逆算していくように元に戻すと
1をaとbの式で表すことができます。そのとき整数x,yを用いてxa+yb=1と表せるので, x,yは1をa,b式で表したときのそれぞれの係数となります。
