Introduction and Proof
Lemma: \(gcd(a - n, n) = gcd(a, n)\).
Proof: Let \(g = gcd(a, n)\), therefore from the definition of gcd, \(g\) is the largest
number which divides both \(a\) and \(n\).
Now, as \(g|a\) and \(g|n\) therefore \(g|(a-n)\). Now to be sure that \(g\) is
the largest such number, let’s assume there exist another \(d\) such that it is
the largest one rather than \(g\) that is \(d > g\), in this case \(d|n\) and
\(d|(a-n)\).
From this, \(d\) must also divide \(n\). But it can not happen because \(g\) is
the \(gcd\) of \(a\) and \(n\) and any other number such as \(d > g\) can not divide
both \(a\) and \(n\).
Generalisation
\(g(a-n, n) = gcd(a, n)\) can be generalised to \(g(a\ mod(n), n) = gcd(a, n)\)
as we can subtract \(n\) from \(a\) as many times as possible atleast when \(a -
k \times n \geq 0\)
Youtube Video
Eucliedian Algorithm
Using the above number theoretical fact one can prove the correctness of
Euclidean Algorithm which
is used to calculate \(gcd\) of two number in \(O(\log(min(a, b)))\) time
complexity.
Inspiration
This post is inspired from the problem Product 1 Modulo N from recent codeforces contest.