Results 1 to 2 of 2

Math Help - Proof of integers

  1. #1
    Newbie
    Joined
    Dec 2009
    Posts
    1

    Proof of integers

    Let a,b and n be positive integers with n ≥ 2. Prove that:

    gcd((n^a) - 1, (n^b) - 1)= n^(gcd(a,b)) - 1.

    Help please!! I have no idea how to do this!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2
    A starting point might be similar to:
    <br />
x^6-1 = (x^2-1)(x^4+x^2+1)<br />
    so if n = dk, with d = gcd(n,m)
    <br />
x^n-1 = (x^d-1)(x^{d*(k-1)}+...)<br />
    and the same for m = dq
    <br />
x^m-1 = (x^d-1)(x^{d*(q-1)}+...)<br />
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof on Integers, sa+tb=n
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 9th 2010, 08:33 AM
  2. Proof about integers
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 14th 2010, 09:14 AM
  3. set of odd integers proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 25th 2010, 09:21 AM
  4. integers proof
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 7th 2010, 06:46 PM
  5. Integers and proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 18th 2009, 09:39 AM

Search Tags


/mathhelpforum @mathhelpforum