Results 1 to 3 of 3

Math Help - Find all positive integers less than 50 which divide 5^29 − 1

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    31

    Find all positive integers less than 50 which divide 5^29 − 1

    I can show that if q is a prime number which divides x=5^29−1, then either q is 2 or q ≡ 1 mod 29.

    So the only prime <50 which divides x is 2. The numbers I need to check for divisibility are powers of 2 up to 32.

    I think I can show that x is div. by 4 using divisibility laws and the fact that x is congruent to 24 mod 25 but I'm sure there's a better way.

    Can anyone help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Josh146 View Post
    I can show that if q is a prime number which divides x=5^29−1, then either q is 2 or q ≡ 1 mod 29.

    So the only prime <50 which divides x is 2. The numbers I need to check for divisibility are powers of 2 up to 32.

    I think I can show that x is div. by 4 using divisibility laws and the fact that x is congruent to 24 mod 25 but I'm sure there's a better way.

    Can anyone help?
    So the only prime less than  50 that divides  x is  2 . So all we need to check are the powers of  2 .

    Let's look at  x modulo  4 :  x=5^{29}-1\equiv1^{29}-1=0 \bmod{4} . So  4\mid x .

    Let's look at  x modulo  8 : Note that  5^2\equiv 1 \bmod{8} , so  5^{29}-1 = (5^2)^{14}\cdot5-1\equiv 4\not\equiv0\bmod{8} .

    Thus only  2,4\mid x with regards to powers of  2 . So  2 and  4 (and  1 ) are the only numbers less than  50 to divide  x .
    Last edited by chiph588@; May 7th 2010 at 06:28 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    As an alternative, factorize 5^{29} - 1 (done using msieve here) :

    5^{29} - 1 = 2 \times 2 \times 59 \times 35671 \times 22125996444329

    The solution to your problem trivially follows
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: October 3rd 2011, 03:40 AM
  2. How many positive integers divide 3^3*5^5*7^7
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 3rd 2011, 06:13 AM
  3. find triples of positive integers.
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: September 17th 2009, 09:02 AM
  4. Find positive integers
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: April 22nd 2009, 02:37 PM
  5. Find all positive integers such that...?
    Posted in the Algebra Forum
    Replies: 3
    Last Post: July 20th 2008, 11:20 AM

Search Tags


/mathhelpforum @mathhelpforum