# What is this algorithm computing and how to prove it?

On Hackerrank I found a test that asks to check what the following algorithm computes:

1. If $$x > y$$ then $$x = x - y$$
2. If $$y > x$$ then $$y = y - x$$
3. If $$x \neq y$$ then goto 1
4. Print $$x$$

Constraints: $$x$$ and $$y$$ are greater than $$0$$

So I think/guess this algorithm returns the product of common factors, so 1 when they do not have any in common. I just guessed it by computation and by intuition, but I would like to prove it in a formal way.

How can this be proved?

• It is the largest number dividing both $x$ and $y$. If you write $x=p_1^{r_1}\dots p_k^{r_k}\cdot q_1^{i_1}\dots q_m^{i_m}$, and write $y=p_1^{e_1}\dots p_k^{e_k} \cdot t_1^{j_1}\dots t_n^{j_n}$ then $gcd(x,y)=p_1^{\min(r_1,e_1)}\dots p_k^{\min(r_k, e_k)}$. So in some sense, it is the multiple of all common prime factors (with respect also to their exponent) Jul 27, 2021 at 10:44