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

Help would be very appreciated.

Results 1 to 4 of 4

- Nov 14th 2013, 05:57 AM #1

- Joined
- Feb 2013
- From
- US
- Posts
- 37
- Thanks
- 1

- Nov 14th 2013, 07:29 AM #2

- Joined
- Nov 2010
- Posts
- 3,325
- Thanks
- 1291

## Re: Problem with GCD

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

$\displaystyle \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, $\displaystyle a^m-1 = (a^d-1)\sum_{k=0}^{s-1}a^{kd}$.

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

- Nov 16th 2013, 08:35 AM #3

- Joined
- Jun 2013
- From
- Lebanon
- Posts
- 820
- Thanks
- 374

## 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 $\displaystyle a^n$ and $\displaystyle a^m$ are each congruent to 1 (mod u)

We need to show that $\displaystyle 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 $\displaystyle x m + d = y n$ then

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

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

- Nov 17th 2013, 05:58 AM #4

- Joined
- Feb 2013
- From
- US
- Posts
- 37
- Thanks
- 1