Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prime or composite

  1. Sep 5, 2010 #1
    is (2^{58}+1)/5 a prime number or a composite number

    trust me this one has got an interesting solution
     
  2. jcsd
  3. Sep 5, 2010 #2

    phyzguy

    User Avatar
    Science Advisor

    Well, it appears that it is 107367629 * 536903681. Why is this of interest?
     
  4. Sep 5, 2010 #3
    If the result is fraction, it will make nonsense to discuss this question.
    So, the result must be integral number.
    Then, if (2^{58}+1) can be divided exactly by 5, the units of (2^{58}+1) must be 0 or 5. Science 2^{58} is even number, (2^{58}+1) must be odd number.
    So, the units of (2^{58}+1) must be 5.
    Then assume (2^{58}+1)=x+5, the units of x must be 0.
    And units of x/5 must be 2, namely x can be divided exactly by 5.
    So, (x+5)/5 can be divided exactly by 3.
    So ,the question solved, the (2^{58}+1)/5 is a composite number.
     
    Last edited: Sep 5, 2010
  5. Sep 5, 2010 #4
    And this question can be solved in this way:
    (2^{58}+1)=(4^{29}+1)=([5-1]^{29}+1)=C(29,0)*5^29*(-1)^0+C(29,1)*5^28*(-1)^1+C(29,2)*5^27*(-1)^2+……+C(29,29)*5^0*(-1)^29+1;
    C(29,29)*5^0*(-1)^29=-1, so C(29,29)*5^0*(-1)^29+1=0.
    And the other items can all be divided exactly by 5, and (2^{58}+1)/5 is a composite number.
     
  6. Sep 5, 2010 #5

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Okay, so far.
    You lost me at that step. Also, are you saying (2^{58}+1)/5 is divisible by 3?

    Okay so far.
    And again, I don't see how you arrived at that. What you have proved is that (2^{58}+1) is composite (specifically that it is divisible by 5).
     
  7. Sep 5, 2010 #6
    That means x+5 can be divide exactly by 15, so (x+5)/5 can be divided exactly by 3.

    the second derivation is something wrong, I'll get another method
     
  8. Sep 6, 2010 #7

    phyzguy

    User Avatar
    Science Advisor

    Not sure what you guys are arguing about. As I said in post #2, (2^{58}+1)/5 has only two prime factors, 107367629 and 536903681, so it is demonstrably not divisible by 3.
     
  9. Sep 6, 2010 #8

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    How do you arrive at that?

    See phyzguy's post. It is not divisible by 3.
     
  10. Sep 6, 2010 #9
    Here's the solution (I actually engineered it backwards, knowing the prime factors):

    [tex]2^{58}+1 = 2^{58} + 2*2^{29} + 1 - 2^{30} = (2^{29}+1)^2 - 2^{30} = (2^{29}-2^{15}+1)(2^{29}+2^{15}+1)[/tex]

    More generally, it follows that all [itex]2^{4n+2}+1[/itex] are composite.

    At the same time, as law&theorem showed, [itex]5|2^{58}+1[/itex], which is a special case of the fact that [itex]5|2^{2(2n+1)}+1[/itex], which, in turn, is a special case of the fact that [itex]a^k+1|a^{k(2n+1)}+1[/itex].

    So we can conclude that all [itex](2^{4n+2}+1)/5[/itex] are composite.
     
    Last edited: Sep 6, 2010
  11. Sep 6, 2010 #10
    Not true for n = 1
     
  12. Sep 6, 2010 #11
    Agreed. [itex] (2^{4n+2}+1)/5 [/itex] is composite as long as [itex]2^{2n+1}-2^{n+1}+1>5[/itex], which is true for [itex] n\geq 2[/itex].
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook