gcd proof

**r0r0trog** · November 9th 2008, 06:11 PM

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

**PaulRS** · November 10th 2008, 04:46 AM

This is what I'd do:

First try showing that any common divisor of $p^a-1$ and $p^b-1$ must divide $<br /> p^{\left( {a,b} \right)} - 1<br />$ ( 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)

**r0r0trog** · November 10th 2008, 06:02 AM

Originally Posted by PaulRS

First try showing that any common divisor of $p^a-1$ and $p^b-1$ must divide $<br /> p^{\left( {a,b} \right)} - 1<br />$ ( 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).

**r0r0trog** · November 10th 2008, 01:54 PM

please anyone?

**Opalg** · November 11th 2008, 03:01 AM

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.

**ThePerfectHacker** · November 12th 2008, 12:35 PM

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.

Thread: gcd proof

LinkBack

Thread Tools

Display

gcd proof

Similar Math Help Forum Discussions

Proof theory: example of an existence proof of a proof?

Convert the following equational proof into a Hilbert Proof

[SOLVED] direct proof and proof by contradiction

Proof with algebra, and proof by induction (problems)

proof that the proof that .999_ = 1 is not a proof (version)

Search Tags