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)
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
Now let . It follows from the above that divides both and .
For the converse, use the fact (consequence of Euclid's algorithm) that there are natural numbers m, n such that . Thus . After a bit of rearrangement, this tells you that . You can see from that equation that any integer that divides and also divides .
As PaulRS points out, there is no need for p to be prime.
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.