4
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

The algorithm computes the greatest common divisor, or gcd for short. You are correct that the output is the product of common factors, since the gcd is known to be equivalent to it.

In fact, this algorithm is known as Euclid's algorithm.

Improve this answer
$\endgroup$
2
  • $\begingroup$ gcd is the greatest common divisor. What do you mean "the product of common factors"? It should be the greatest of the common factors $\endgroup$
    – Jim
    Jul 27, 2021 at 7:33
  • $\begingroup$ 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) $\endgroup$
    – nir shahar
    Jul 27, 2021 at 10:44

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.