Results 1 to 6 of 6

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

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: October 19th 2010, 11:50 AM
  2. Replies: 0
    Last Post: June 29th 2010, 09:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 11:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02: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: April 14th 2008, 05:07 PM

Search Tags


/mathhelpforum @mathhelpforum