can someone help me prove that gcd(p^a - 1, p^b - 1) = p^gcd(a, b) - 1, plz?
a and b are positive integers and p is a prime
this is how far i've come til i got stuck:
assume b >= a.
gcd(p^a - 1, p^b - 1) | (p^b - 1) - (p^a - 1) <=>
<=> gcd(p^a - 1, p^b - 1) | p^b - p^a <=>
<=> gcd(p^a - 1, p^b - 1) | p^a * (p^(b-a) - 1) <=>
<=> gcd(p^a - 1, p^b - 1) | p^(b-a) - 1 .. (since neither p^a - 1 or p^b - 1 divise p^a they must divise the other factor)
i don't know if i'm on the right track but it feels good, anyhow i'm stuck and would really appreciate a push (Crying)
This is what I'd do:
First try showing that any common divisor of and must divide ( hint: use the order of p mod the common divisor)
Then show that is a common divisor
( in fact p need not be prime)
didn't manage to show this. still get to the same as before, that any common divisor of p^a - 1 and p^b - 1 must divide p^(b-a) - 1. i know gcd(a, b) | b-a, but b-a doesnt necessarily divide gcd(a, b).
Originally Posted by PaulRS
Here is a similar problem: .
To solve this problem we will use roots of unity. Let where .
The key fact is that if for positive integers then for some positive integer .
As an illustration consider .
We can write .
One example is in that case we end up with .
Notice that we end up with where and .
This happens to be true in general.
Let , monic, divide both and .
Since is monic we can write for .
But and .
Thus we see that each linear factor, , of must divide and .
Therefore, for some positive integers .
But by the above statement it means for some .
Consequently each linear factor of has this form.
Therefore, divides .
Since divides for we see that it is the gcd of the two polynomials.