Results 1 to 3 of 3

Thread: 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 $\displaystyle 50 $ that divides $\displaystyle x $ is $\displaystyle 2 $. So all we need to check are the powers of $\displaystyle 2 $.

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

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

    Thus only $\displaystyle 2,4\mid x $ with regards to powers of $\displaystyle 2 $. So $\displaystyle 2 $ and $\displaystyle 4 $ (and $\displaystyle 1 $) are the only numbers less than $\displaystyle 50 $ to divide $\displaystyle 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 $\displaystyle 5^{29} - 1$ (done using msieve here) :

    $\displaystyle 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: Oct 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: Feb 3rd 2011, 06:13 AM
  3. find triples of positive integers.
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Sep 17th 2009, 09:02 AM
  4. Find positive integers
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: Apr 22nd 2009, 02:37 PM
  5. Find all positive integers such that...?
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Jul 20th 2008, 11:20 AM

Search Tags


/mathhelpforum @mathhelpforum