Finding gcd using euclid's algorithm

Question

Find $\gcd(47,6)$ using euclid's algorithm

I know that if $\gcd(a,b)=\gcd(b,r)$ where $a=qb+r$

So in there case $47=7\cdot6+5$ or $47=8\cdot6-1$ should I prefer finding prime numbers decomposition? will it make the process shorter?

Answer 1

Except for the cases where prime factor decomposition is readily available, Euclid's algorithm should be preferred, as it is much more computational efficient. Euclid's algorithm is at most linear in the number of digits of the smaller number $O(\log n)$, while integer factorization is a notoriously harder problem, best published running time is $O\left(exp\sqrt[3]{\frac{64}{9}\log n (\log\log n)^2}\right)$. The difficulty of integer factorization is the basis for the RSA public key algorithms.

Answer 2

If the question is to find GCD, you can use the one you find will get you quicker to the answer. If they want you to find two numbers such that $ax+by=gcd(a,b)$, then you have to use Euclid's algorithm..

Answer 3

It depends on what the initial numbers are. Try $\gcd(F_{n + 1}, F_n)$, where $F_n$ is the $n$th Fibonacci number.

Generally, though, the Euclidean algorithm is faster, or it's just a tiny bit slower than prime factorization so that the performance penalty is hardly worth being concerned about.

In the specific case of $\gcd(47, 6)$, prime factorization seems faster only because we already know 47 is prime and 6 is a semiprime, so it feels like we immediately know the two numbers are coprime.

It seems to me like the Euclidean algorithm is usually implemented to first do $\frac{a}{b}$ with $a > b$ and both numbers positive. So after $47 = 7 \times 6 + 5$, we do $6 = 1 \times 5 + 1$ and there we have our answer in two steps.

Now try $\gcd(100459, 14351)$. I have a feeling Euclid's algorithm gives you the answer in two steps. To find if 100459 is prime, you might have to do 316 trial divisions.