# GCD of two big numbers [duplicate]

How to find $gcd(5^{100}-1, 5^{120}-1)$?
The problem is numbers are really big ($5^{100}$ is 70 digits). None of the numbers is prime.
I ran Euclid's algorithm on Python and found the answer in less than a second, however it seems that there is no on-paper approach to this problem, is it?

• math.stackexchange.com/questions/235641/… – 1123581321 Mar 14 '18 at 15:33
• Well, the gcd of 100 and 120 is 20 so $5^{20}-1$ is a common divisor. So need the gcd of $5^{80}+...+1$ and $5^{100}+..+1$. And by taking the difference that is clearly 1. So the gcd is $5^{20}-1$ – fleablood Mar 14 '18 at 15:34

If $$d\mid 5^{100}-1\;\;\;\;{\rm and}\;\;\;\;d\mid 5^{120}-1$$ then $\gcd (d,5)=1$ and $$d\mid (5^{120}-1) - (5^{100}-1) = 5^{100}(5^{20}-1)$$

so $d\mid 5^{20}-1$. Since $5^{20}-1\mid 5^{100}-1$ and $5^{20}-1\mid 5^{120}-1$

so $\gcd (...) = 5^{20}-1$.

There is. G.C.D. = $5^{\gcd(100,120)} -1$
and you can verify this easily.

• Maybe you could give some references or a sketch of the proof ? – Zubzub Mar 14 '18 at 15:31

Because $\frac {x^{mk} - 1}{x^k - 1} = x^{(m-1)k} + x^{(m-2)k} + .... + 1$. then then $x^{\gcd(m,n)} -1$ is a common divisor of $x^m - 1$ and $x^n - 1$ and :

$\gcd(x^m - 1,x^n - 1) = (x^{\gcd(m,n)} - 1)*\gcd(x^{(\frac m{\gcd(m,n)} - 1)\gcd(m,n)}+... +1, x^{(\frac n{\gcd(m,n)} - 1)\gcd(m,n)}+... +1)$

And by Euclids algorithm the GCD of $x^k + x^{k-1} + 1$ and $x^{j} + ... + 1$ can be found be subtracting an factoring out powers of $x$. As $k,j$ are relatively prime (I think), the gcd will be $1$.

So:

$\gcd(5^{120} -1 , 5^{100} - 1) = (5^{20} -1)\gcd(a=5^{100} + 5^{80}+.... + 5^{20} + 1, b=5^{80} + 5^{60} + .. + 5^20 + 1) =$

$(5^{20} -1)\gcd(a-b, b) = (5^{20}-1)\gcd(5^{100}, 5^{80} + ... + 1)$

And as the only prime factors of $5^{20}$ are not prime factors of $1$ more than the sum of powers of $5$, the $\gcd(5^{100}, 5^{80} + ... + 1)=1$.

So $\gcd(5^{120} -1, 5^{100} -1) = 5^{20}-1$.

I think we can extend that to $\gcd(x^m - 1,x^n - 1) = x^{\gcd(m,n)} - 1$ but I haven't completely verified that by euclid algorithm that $x^{k*d} + ....+1$ and $x^{m*d} + .... + 1$ where $\gcd(k,m)=1$ are relatively prime. But I'm almost certain that that must be true. We keep subtracting and factorin out powers of $x$ and $m$ and $k$ are relatively prime the final result will be a single power.