One common trick taught in competitive programming is the formula to calculate the greatest common divisor of two numbers. That is, for some integers $a \text{ and }b$, the largest integer $c$ such that $x \mid a \text{ and }x \mid b$. The algorithm can be thought of as the following: Given two integers $a, b$, we can say that

and

The latter follows from the fact that $a$ is the largest integer to divide itself, and everything divides 0 (because $0=an \text{ for any integer $a$ when }n=0$ ).

But how do we know this to be true? Well, let’s prove it. Take $x = gcd(a,b), y=gcd(b,a\%b)$. If we can show that $x <= y, y <= x$, then we it must be true that $x=y$, which means the GCDs are indeed equal.

By definition of GCD, $x \mid a, x \mid b$. This means that $a=xk$ for some integer k, and $b=xj$ for some integer j. To show that $x <= y$, we look to first show that $x \mid (a\%b)$, since it already divides b. By definition, $a=bq+(a\%b)$ for some integer q. Substituting in our earlier definitions for a and b, we get $xk=(xj)q+(a\%b)$. Rearranging the equation, we get $a\%b=xk-xjq=x(k-jq)$. By definition, $x \mid x(k - jq)$, and so we get that $x \mid b, x \mid (a\%b)$. Because y is their GCD, this means that $x <= y$ has been established.

Now, we want to show that $y <= x$. We will do something similar to the first part, and show that $y \mid a, y \mid b$. We’re given that $y \mid b, y \mid (a\%b)$. This give us $b=yk', (a\%b)=yj'$ for some integers k’, j’. By definition, $a=bq'+(a\%b)$ for some integer k. With substitutions, we get that $a=(yk')q' + yj'=yk'q' +yj'=y(k'q'+j')$. By definition, $y \mid y(k'q'+j')$, and thus y divides a. Since x is the gcd of a and b, and y divides both a and b, it must hold that $y <= x$.