# gcd proof

• Nov 9th 2008, 06:11 PM
r0r0trog
gcd proof
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)
• Nov 10th 2008, 04:46 AM
PaulRS
This is what I'd do:

First try showing that any common divisor of $\displaystyle p^a-1$ and $\displaystyle p^b-1$ must divide $\displaystyle p^{\left( {a,b} \right)} - 1$ ( hint: use the order of p mod the common divisor)

Then show that $\displaystyle p^{(a,b)}-1$ is a common divisor

( in fact p need not be prime)
• Nov 10th 2008, 06:02 AM
r0r0trog
Quote:

Originally Posted by PaulRS
First try showing that any common divisor of $\displaystyle p^a-1$ and $\displaystyle p^b-1$ must divide $\displaystyle p^{\left( {a,b} \right)} - 1$ ( hint: use the order of p mod the common divisor)

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).
• Nov 10th 2008, 01:54 PM
r0r0trog
• Nov 11th 2008, 03:01 AM
Opalg
Quote:

Originally Posted by r0r0trog
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

First, note that x-1 is a factor of $\displaystyle x^n-1$ for any natural number n. Put $\displaystyle x=p^d$ to see that $\displaystyle p^d-1$ divides $\displaystyle p^{nd}-1$.

Now let $\displaystyle d = \text{gcd}\{a,b\}$. It follows from the above that $\displaystyle p^d-1$ divides both $\displaystyle p^a-1$ and $\displaystyle p^b-1$.

For the converse, use the fact (consequence of Euclid's algorithm) that there are natural numbers m, n such that $\displaystyle d=ma-nb$. Thus $\displaystyle p^{ma} = p^{nb}p^d$. After a bit of rearrangement, this tells you that $\displaystyle p^{ma}-1 = p^d(p^{nb}-1) +(p^d-1)$. You can see from that equation that any integer that divides $\displaystyle p^a-1$ and $\displaystyle p^b-1$ also divides $\displaystyle (p^d-1)$.

As PaulRS points out, there is no need for p to be prime.
• Nov 12th 2008, 12:35 PM
ThePerfectHacker
Here is a similar problem: $\displaystyle \gcd(x^n - 1,x^m - 1) = x^{\gcd(n,m)} - 1$.

To solve this problem we will use roots of unity. Let $\displaystyle \alpha = e^{2\pi i/n},\beta = e^{2\pi i/m}, \gamma= e^{2\pi i/d}$ where $\displaystyle d=\gcd(n,m)$.
---
The key fact is that if $\displaystyle \alpha^{A} = \beta^{B}$ for positive integers $\displaystyle A,B$ then $\displaystyle \alpha^A = \gamma^C = \beta^B$ for some positive integer $\displaystyle C$.

As an illustration consider $\displaystyle \left( e^{2\pi i/6} \right)^A = \left( e^{2\pi i/8} \right)^B$.
We can write $\displaystyle \left( e^{2\pi i/24} \right)^{4A} = \left( e^{2\pi i/24} \right)^{3C}$.
One example is $\displaystyle A=3,B=4$ in that case we end up with $\displaystyle \left( e^{2\pi i/6} \right)^A = \left( e^{2\pi i/8} \right)^B = e^{2\pi i/2}$.
Notice that we end up with $\displaystyle \left( e^{2\pi i/d} \right)^C$ where $\displaystyle d=\gcd(6,8)$ and $\displaystyle C=1$.

This happens to be true in general.
---

Let $\displaystyle f(x)\in \mathbb{Q}[x]$, monic, divide both $\displaystyle x^n-1$ and $\displaystyle x^m-1$.
Since $\displaystyle f(x)$ is monic we can write $\displaystyle f(x) = (x-\omega_1)...(x-\omega_t)$ for $\displaystyle \omega_1,...,\omega_t \in \mathbb{C}$.
But $\displaystyle x^n - 1 = \prod_{k=1}^n (x - \alpha^k)$ and $\displaystyle x^m -1 = \prod_{k=1}^m (x-\beta^k)$.
Thus we see that each linear factor, $\displaystyle x-\omega_j$, of $\displaystyle f(x)$ must divide $\displaystyle x^n-1$ and $\displaystyle x^m - 1$.
Therefore, $\displaystyle \alpha^A = \omega_j = \beta^B$ for some positive integers $\displaystyle A,B$.
But by the above statement it means $\displaystyle \omega_j = \gamma^C$ for some $\displaystyle C$.
Consequently each linear factor of $\displaystyle f(x)$ has this form.
Therefore, $\displaystyle f(x)$ divides $\displaystyle (x - \gamma)(x - \gamma^2)...(x-\gamma^d) = \prod_{k=1}^d (x-\gamma^k) = x^d - 1$.
Since $\displaystyle x^d - 1$ divides $\displaystyle x^n-1,x^m-1$ for $\displaystyle d|n,d|m$ we see that it is the gcd of the two polynomials.