0
$\begingroup$

One can use the extended Euclidean algorithm to calculate the modular multiplicative inverse of a number, as it will be in the form $a x + b y = 1$, and if you take mod $b$ of both sides you get the inverse of $a$ in mod $b$. However, why does the Euclidean algorithm work? Specifically, why is the last non-zero remainder gcd(a,b)? And how come you can just substitute everything back and it magically give you gcd(a,b) in terms of integers? Thanks so much.

$\endgroup$
  • 3
    $\begingroup$ What have you read about the algorithm? What don't you understand? $\endgroup$ – marty cohen Nov 15 '16 at 1:12
  • $\begingroup$ @martycohen I read how to use it to find the inverse, but I have no idea why it works and how the substitution process with the remainders can get it in terms of a and b. $\endgroup$ – ConfusedMathStudent Nov 15 '16 at 2:46
2
$\begingroup$

That is because it relies on the following easy lemma:

The set of common divisors of $a$ and $b$ is the same as the set of common divisors of $b$ and $b\bmod a$. Hence $\gcd(a,b)=\gcd(b, b\bmod a)$.

The extended Euclidean algorithm relies on a more precise analysis of the successive divisions: if we denote by $r_0=a$, $r_1=b$, $r_2=r_0\bmod r_1$, … , $r_{n+1}=r_n\bmod r_{n-1}$, … , the $n$-th division equality: $$r_{n-1}=q_nr_n+r_{n+1}$$ can be rewritten as $$r_{n+1}=r_{n-1}-q_nr_n.$$ An easy induction shows that, not only the last non-zero remainder satisfies a Bézout's identity, but that all intermediate remainders satisfy such an identity: $$r_n=u_n a+v_nb.$$ The sequences of coefficients $(u_n)$ and $(v_n)$ are initialised as $$u_0=1,~v_0=0,\qquad u_1=0,~v_1=0,$$ and they satisfy the same recurrence relation as the remainders: $$u_{n+1}=u_{n-1}-q_nu_n, \qquad v_{n+1}=v_{n-1}-q_nv_n.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.