GCD and Eucldiean Algorithm
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$
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.