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

Prove that this number is not a prime number

  1. Jul 6, 2012 #1
    Hello all. I came across this question which is "prove that (5^125-1)/(5^25-1) is composite". I am not even getting a clue as to how I can attack this problem. Any help would be greatly appreciated.

    Please note that we need to prove (5^125-1)/(5^25-1)=1+5^25+5^50+5^75+5^100 as composite and not 5^125-1.
     
    Last edited: Jul 6, 2012
  2. jcsd
  3. Jul 6, 2012 #2
    Hint: Can you factor the polynomial [itex]x^3 - 1[/itex]?
     
  4. Jul 6, 2012 #3
    I understand that 5^125-1 divided by 5^25-1 can be expanded as 1+5^25+5^50+5^75+5^100. How can it be proven that 1+5^25+5^50+5^75+5^100 is composite and not a prime?
     
  5. Jul 7, 2012 #4
    The bottom of the fraction is of the form [itex]x-1[/itex] and the top [itex]x^3-1[/itex]. Why don't you try polynomial long division?
     
  6. Jul 7, 2012 #5

    I like Serena

    User Avatar
    Homework Helper

    Hi StatOnTheSide! :smile:

    You want to break up (5^125-1) into smaller pieces.
    One way to do that is into (5^25-1) and (1+5^25+5^50+5^75+5^100).

    Suppose you find another way to break up (5^125-1) into smaller pieces?
    Can you think of another likely expression to divide by?
     
  7. Jul 7, 2012 #6
    Thanks Serena. There does not seem to be other ways to break 1+5^25+5^50+5^75+5^100. 5^125-1 has other ways of breaking up but all of them have 1+5^25+5^50+5^75+5^100 in common.

    Basically, 5^125-1 divided by 5^25-1 leaves us with 1+5^25+5^50+5^75+5^100 and that needs to be proven as being composite. I cannot think of a straightforward way of factorizing 1+5^25+5^50+5^75+5^100. Is there some other trick in order to prove that it is composite? Maybe some theorem which needs to hold for a prime number does not hold for this number. Please suggest any hint in case you think it can lead me to the answer.
     
  8. Jul 7, 2012 #7

    mathman

    User Avatar
    Science Advisor
    Gold Member

    There is a factor 5^50 - 2cos(2π/5)5^25 + 1. I don't know if it is an integer.

    Petek should have started with x^5 - 1.
     
  9. Jul 7, 2012 #8
    True. You can factor 1+x+x^2+x^3+x^4 as
    x^2+1-x*[(sqrt5)-1]/2 and x^2+1+x*[(sqrt5)+1]/2

    But these are not integers when you substitute x=5^25.

    I also tried to use cyclotomic factorizations but did not get very far with it. Numbers like (6^106+1)/(6^2+1) can be shown to be composite using that technique.

    I tend to get struck in a particular line of thought and the answer lies in another line of thought. A great challenge for me is to change the line of thought and I almost invariably can't think of an alternative line of thought if I can't get the solution to a problem in the first shot.
     
  10. Jul 7, 2012 #9
    A question I would ask is what integer of form (x^(x^3) - 1)/(x^(x^2) - 1) is not composite?
     
  11. Jul 7, 2012 #10
    Hi Anti Crackpot. I did notice that it has that form; however, it just leads to the idea that 1+x^(x^2)+x^(2x^2)+....+x^((x-1)*x^2) is prime. What can this lead me to? It does not say anything conclusive about whether or not that number is prime or composite. It is a nice expression but what is the key to proving that it is not a prime for x=5?
     
  12. Jul 7, 2012 #11
    What I'm thinking is that if you can show that this form is always composite, then 5 just becomes a special case of a broader one. I just checked for x = 2, 3, 4, 6 & 7 and, unless Wolfram Alpha is mistaken, all are composites. [EDIT: Please see posts by Dick and myself below, as this is an incorrect statement for n = 2 /EDIT]

    I have to think about it and/or remember it, but the form you are working with reminds me of some little number theory tidbit I have come across in the past. But, just as a thought in the meantime...

    Set 1 + 5^25 + 5^50 + 5^75 + 5^100 = y and perform the following routine:
    A ) Subtract 1 from both sides
    B ) Factor out 5^25
    C ) Divide both sides by 5^25
    D) Repeat until 0 is reached.

    - AC
     
    Last edited: Jul 8, 2012
  13. Jul 7, 2012 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    (2^(2^3) - 1)/(2^(2^2) - 1)=17. That's not composite. For the rest of the examples, an awfully lot of large numbers are composite. So that evidence is not very convincing.
     
  14. Jul 8, 2012 #13
    You are absolutely correct, Dick, and I agree with you with respect to "convincingness." And as was noted by StatontheSide, the point is to prove that (5^125-1)/(5^25-1) is composite, not (5^125-1). My bad. Thanks for the catch on n= 2. Indeed, 17 * 15 = 255 and 17 is prime.

    All the same, I'm not sure if it discounts the entire premise as an idea to work with since for the case of n = 2 there is only 1 1/3 iteration of the factorization routine I mentioned to get to 0. I'll have to go back and re-check the first few values for compositeness to determine if it's a "full stop no-go."

    @ StatontheSide
    Here is the prime factorization for the number you posted (courtesy of Wolfram Alpha). Note that, coincidentally or no, all factors are congruent to 1 mod (250)

    3597751×28707251×4032808198751×767186663625251×24687045214139234043375683501 (5 distinct prime factors)

    - AC
     
    Last edited: Jul 8, 2012
  15. Jul 8, 2012 #14

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No it isn't. 5125 = 5(53), not (55)3
     
  16. Jul 8, 2012 #15
    @AC, you are right. It does factor that way according to that website. I treid with 3^3^3-1 divided by 3^3^2-1 and that also turned out to be composite. Also, you rightly pointed out that when divided by 250, all the primes leave a reminder of 1. Proof of that is possible to be constructed and I have attempted that below.

    Let p, a prime, divide (5^125-1)/(5^25-1). Then 5^125=p*(5^25-1)*q+1 where q is some integer, and hence, 5^125=1mod(p).

    Also, 5^(p-1)=1mod(p) as p is prime according to Fermat's theorem. There is an argument to show that 125 is the least number i for which 5^i=1mod(p). I will first need to show that i divides 125 is i is the least number for which 5^i=1mod(p).

    If i is the least number, then let 125=ix+y,y<i. Since 5^125 and 5^i are both =1mod(p), 5^y=1mod(p). I have made use of the fact that (p,5)=1. Hence y<i is such that 5^y=1mod(p) against our assumption that i is the least number. Hence y=0 and i divides 125.

    Since i is a number such that 5^i=1mod(p), p divides 5^i-1. This implies that 5^i>p=1+5^25+....+5^100 which implies that i>100. Also, i divides 125 and hence, has to be 1,5,25,125. Since i>100, i=125.

    Hence we can conclude that p=1mod(125) and as p-1 is even, and as 125 and 2 are relatively prime, p leaves a reminder of 1 when divided by 250. QED.

    I still have not gotten the clue to prove that the number is composite. I know that it can be factored the way AC has suggested but I am thinking that there is a general proof possible for numbers of the form n^n^n-1 divided by n^n^(n-1)-1 where n>2. I checked for n=3 and it is true.

    Please do let me know if you guys can think of ways to prove that such a number is always composite.
     
  17. Jul 8, 2012 #16
    All I know offhand is that Fermat's Little Theorem and Geometric Series (which indirectly brings in Wilson's Theorem) are almost certain to be involved. Also, maybe (mod p) and mod (p- 1) since I think the number of terms might matter.

    I realize I am being very vague, but I'm just trying to help you "hopscotch" your thinking (as requested in not so many words).

    - AC
     
  18. Jul 9, 2012 #17

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    p=1+525+....+5100? No, p | 1+525+....+5100, surely.
    I think all that can be concluded along these lines is that:
    if p > 5 then p [itex]\equiv[/itex] 1 (5)
    if p > 55 then p [itex]\equiv[/itex] 1 (25)
    if p > 525 then p [itex]\equiv[/itex] 1 (125)
     
  19. Jul 9, 2012 #18
    I am not sure if I understand it correctly. 13 is a prime and it is not[itex]\equiv[/itex]1(5).

    Are you saying that geometric progressions in 5 having prime values must be [itex]\equiv[/itex]1(5)? If that is your claim, then I can uderstand why it is true; however, that property does not seem to help me a lot in trying to prove that this geometric progression is composite and not prime.
     
  20. Jul 9, 2012 #19

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    My post was in the context of p being presumed to be a factor of 5125-1, which 13 is not. The following are some of the lowest prime factors: 2, 11, 71.
    I was commenting on the post which claimed to show a prime factor of (5125-1)/(525-1) must be 1 mod 125. Not only does that not seem to help very much, it maybe isn't even true. I was pointing out an error in the proof offered. I can prove it for primes > 525.
     
  21. Jul 9, 2012 #20
    It is true that all the prime factors of (5125-1)/(525-1) must be 1 mod 125. It has been confirmed by actually calculating the prime factors. I have also provided the proof. Please do let me know as to where the proof goes wrong as I could not understand it from your post.

    Similar to the above, it can even be shown that (3^3^3-1)/(3^3^2-1) has prime factors which when divided by 3^3 ALWAYS leaves a reminder of 1.

    In general, (n^n^n-1)/(n^n^(n-1)-1) has prime factors which when divided by n^n always leaves a reminder of 1 for n>1.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove that this number is not a prime number
  1. Prime Numbers (Replies: 24)

  2. Prime Numbers (Replies: 28)

  3. Prime number. (Replies: 7)

  4. Proving prime numbers (Replies: 9)

  5. Prime Numbers (Replies: 1)

Loading...