# gcd proof

• Nov 9th 2008, 07: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, 05:46 AM
PaulRS
This is what I'd do:

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

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

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

Originally Posted by PaulRS
First try showing that any common divisor of $p^a-1$ and $p^b-1$ must divide $
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, 02:54 PM
r0r0trog
• Nov 11th 2008, 04: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 $x^n-1$ for any natural number n. Put $x=p^d$ to see that $p^d-1$ divides $p^{nd}-1$.

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

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

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

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

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

This happens to be true in general.
---

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