# Prove that this number is not a prime number

1. Jul 6, 2012

### StatOnTheSide

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. Jul 6, 2012

### Petek

Hint: Can you factor the polynomial $x^3 - 1$?

3. Jul 6, 2012

### StatOnTheSide

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?

4. Jul 7, 2012

### Millennial

The bottom of the fraction is of the form $x-1$ and the top $x^3-1$. Why don't you try polynomial long division?

5. Jul 7, 2012

### I like Serena

Hi StatOnTheSide!

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?

6. Jul 7, 2012

### StatOnTheSide

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.

7. Jul 7, 2012

### mathman

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.

8. Jul 7, 2012

### StatOnTheSide

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.

9. Jul 7, 2012

### Anti-Crackpot

A question I would ask is what integer of form (x^(x^3) - 1)/(x^(x^2) - 1) is not composite?

10. Jul 7, 2012

### StatOnTheSide

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?

11. Jul 7, 2012

### Anti-Crackpot

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
12. Jul 7, 2012

### Dick

(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.

13. Jul 8, 2012

### Anti-Crackpot

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
14. Jul 8, 2012

### haruspex

No it isn't. 5125 = 5(53), not (55)3

15. Jul 8, 2012

### StatOnTheSide

@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.

16. Jul 8, 2012

### Anti-Crackpot

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

17. Jul 9, 2012

### haruspex

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 $\equiv$ 1 (5)
if p > 55 then p $\equiv$ 1 (25)
if p > 525 then p $\equiv$ 1 (125)

18. Jul 9, 2012

### StatOnTheSide

I am not sure if I understand it correctly. 13 is a prime and it is not$\equiv$1(5).

Are you saying that geometric progressions in 5 having prime values must be $\equiv$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.

19. Jul 9, 2012

### haruspex

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.

20. Jul 9, 2012

### StatOnTheSide

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