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

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

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

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

- Joined
- Nov 2010
- Posts
- 1,930
- Thanks
- 782

## Re: Problem with GCD

Let be an integer that divides both and . Then and for some pair of integers . So,

Similarly, .

So, clearly divides both and for any common divisor of . So, is a common divisor of both and . All that is left is to show that any other common divisor of and must divide

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

- Joined
- Jun 2013
- From
- Lebanon
- Posts
- 171
- Thanks
- 80

## 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 and are each congruent to 1 (mod u)

We need to show that 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 then

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

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