# Math Help - Problem with GCD

1. ## Problem with GCD

if gcd(n,m) = d then prove that gcd((a^n)-1,(a^m)-1)=(a^d)-1.

Help would be very appreciated.

2. ## Re: Problem with GCD

Let $d$ be an integer that divides both $n$ and $m$. Then $n = rd$ and $m = sd$ for some pair of integers $r,s$. So,

\begin{align*}a^n-1 & = a^{rd}-1 \\ & = (a^{rd} - a^{(r-1)d}) + (a^{(r-1)d} - a^{(r-2)d}) + \cdots (a^{2d}-a^d) + (a^d-a^0) \\ & = a^{(r-1)d}(a^d-a^0) + a^{(r-2)d}(a^d-a^0) + \cdots + a^d(a^d-a^0) + a^0(a^d-a^0) \\ & = (a^d - a^0)\sum_{k = 0}^{r-1}a^{kd}\end{align*}

Similarly, $a^m-1 = (a^d-1)\sum_{k=0}^{s-1}a^{kd}$.

So, $(a^d-1)$ clearly divides both $a^n-1$ and $a^m-1$ for any common divisor of $m,n$. So, $a^{\gcd(m,n)}-1$ is a common divisor of both $a^n-1$ and $a^m-1$. All that is left is to show that any other common divisor of $a^n-1$ and $a^m-1$ must divide $a^{\gcd(m,n)}-1$

3. ## Re: Problem with GCD

..... to show that any other common divisor of a^n-1 and a^m-1 must divide a^{\gcd(m,n)}-1

If u is such a divisor then $a^n$ and $a^m$ are each congruent to 1 (mod u)

We need to show that $a^d$ is congruent to 1 (mod u) where d=gcd(m,n)

This follows from the fact that d is a linear combination of m and n

For example, say there are positive integers x and y such that $x m + d = y n$ then

$\left(a^m\right)^xa^d=\left(a^n\right)^y$

$a^d=1 (\text{mod} u)$

4. ## Re: Problem with GCD

Thanks I've finally figured it out!