Greatest Common Divisors of powers - 1?

Question

Prove the following: $$ gcd(n^a-1, n^b-1) = n^{gcd(a, b)}-1 $$ I am not even sure where to start. I tried some stuff, but I always reach dead ends.

How should I go about proving this?

Answer 1

Hint:

Let $q$ be the quotient if the Euclidean division of $a$ by $b$, $r=a\bmod b$ its remainder. Prove the remainder in the division of $n^a-1$ by $n^b-1$ is $n^r-1$, in other words: $$(n^a-1) \bmod (n^b-1)=n^{a\bmod b}-1.$$ Deduce that performing the Euclidean algorithm on $\; n^a-1\;$ and $\;n^b-1$ performs the Euclidean algorithm on $a$ and $b$ in parallel.

Answer 2

Can you factor $n^k - 1$? How many ways? Does it make any difference if $k$ is prime or composite.

What are the factors of $n^a - 1 = n^{\frac a{\gcd(a,b)}\gcd(a,b)}-1$ and what are the factors o $n^b - 1 = n^{\frac b{\gcd(a,b)}\gcd(a,b)} - 1$. Is $n^{\gcd(a,b)} -1$ a common factor? Is there any larger common factor?

====

hint:

$n^k - 1 = (n-1)(n^{k-1} + ..... + n + 1)$.

And $n^{am} - 1 = (n^a)^m - 1 = (n^a - 1)(n^{a(m-1)} + ..... + n^a + 1)$.

So......

If $a = a'\gcd(a,b)$ and $b=b'\gcd(a,b)$ then $n^a - 1 = (n^{\gcd(a,b)})^{a'} - 1) = .....$ and $n^b -1 =(n^{\gcd(a,b)})^{b'} - 1)$.

So.....