Results 1 to 6 of 6

Thread: gcd proof

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    55

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2008
    Posts
    55
    Quote Originally Posted by PaulRS View Post
    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).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2008
    Posts
    55
    please anyone?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    10
    Quote Originally Posted by r0r0trog View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: Oct 19th 2010, 10:50 AM
  2. Replies: 0
    Last Post: Jun 29th 2010, 08:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 01:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: Apr 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum