Prove that this number is not a prime number

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

 

[Petek]

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

 

[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?

 

[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?

 

[I like Serena]

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.

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?

 

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

 

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

 

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

 

[Anti-Crackpot]

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

 

[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?

 

[Anti-Crackpot]

It is a nice expression but what is the key to proving that it is not a prime for x=5?

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

 

[Dick]

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.

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

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

 

[Anti-Crackpot]

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

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

 

[haruspex]

the top <is of the form> x^3-1.

No it isn't. 5¹²⁵ = 5⁽⁵³⁾, not (5⁵)³

 

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

 

[Anti-Crackpot]

Please do let me know if you guys can think of ways to prove that such a number is always composite.

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

 

[haruspex]

This implies that 5^i>p=1+5^25+...+5^100 which implies that i>100.

p=1+5²⁵+...+5¹⁰⁰? No, p | 1+5²⁵+...+5¹⁰⁰, surely.
I think all that can be concluded along these lines is that:
if p > 5 then p \equiv 1 (5)
if p > 5⁵ then p \equiv 1 (25)
if p > 5²⁵ then p \equiv 1 (125)

 

[StatOnTheSide]

I think all that can be concluded along these lines is that:
if p > 5 then p \equiv 1 (5)

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

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

 

[haruspex]

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

My post was in the context of p being presumed to be a factor of 5¹²⁵-1, which 13 is not. The following are some of the lowest prime factors: 2, 11, 71.

Are you saying that geometric progressions in 5 having prime values must be \equiv1(5)? If that is your claim, then I can understand 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.

I was commenting on the post which claimed to show a prime factor of (5¹²⁵-1)/(5²⁵-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 > 5²⁵.

 

[StatOnTheSide]

My post was in the context of p being presumed to be a factor of 5¹²⁵-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 (5¹²⁵-1)/(5²⁵-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 > 5²⁵.

It is true that all the prime factors of (5¹²⁵-1)/(5²⁵-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.

 

[coolul007]

an expression with composite exponents is divisible by the divisors of the exponent, so 5^125 - 1, is divisible by 5^1 - 1, 5^5 -1, 5^25 - 1.

 

[StatOnTheSide]

Thanks coolul007. The question is to prove that (5^125-1) divided by (5^25-1) is composite and not to prove that (5^125-1). The later, as you have pointed out, is trivial.
In other words, prove that 1+5^25+5^50+5^75+5^100 is composite.

 

[coolul007]

The result is a 5 digit repunit number base 5^25

 

[StatOnTheSide]

The result is a 5 digit repunit number base 5^25

I did not understand. What is a repunit? Did you just give me a hint to solve the problem or did you just make an observation?

 

[coolul007]

I did not understand. What is a repunit? Did you just give me a hint to solve the problem or did you just make an observation?

It's a observation/hint, I am researching factoring repunits, there are very few primes with large bases and a few number of digits.

 

[coolul007]

I may be stating the obvious here, just some thoughts:
a^{4} + a^{3} +a^{2} + a + 1 \equiv 0 mod(m) and 5^{25} \equiv a mod(m)

 

[StatOnTheSide]

I may be stating the obvious here, just some thoughts:
a^{4} + a^{3} +a^{2} + a + 1 \equiv 0 mod(m) and 5^{25} \equiv a mod(m)

If a is the reminder after dividing 5^25 by m, then the reminder of division of 1+a+...+a^4 by m is 0. Why is that? Also, does that have any use for proving that it is composite? I am sorry but I am confused and I do not see your point here. Please explain.

 

[coolul007]

If a is the reminder after dividing 5^25 by m, then the reminder of division of 1+a+...+a^4 by m is 0. Why is that? Also, does that have any use for proving that it is composite? I am sorry but I am confused and I do not see your point here. Please explain.

If we can find an "m" that satisfies both statements then the number is a composite with 'm" as a factor.

 

[haruspex]

It is true that all the prime factors of (5¹²⁵-1)/(5²⁵-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.

In the proof there was this statement:
p=1+5²⁵+...+5¹⁰⁰
and the proof seemed to rely on that. It's wrong, no? p is assumed to divide that, not be equal to it.

 

[StatOnTheSide]

haruspex: I must have been sleeping when I wrote that :). It is really embarassing :(.
Let me try to cover it up. You are right. The proof is obviously wrong; however, the claim is right. Let me re-write the proof.

Let the number n=1+5^25+5^50+5^75+5^100. Let the p be one of its factors. Then n=p*m where m is another number.

Lemma1: 5^125=1mod(p)

Proof: n=(5^125-1)/(5^25-1). Hence 5^125=1+n*(5^25-1)=1+p*m*(5^25-1).

Lemma2: 5^(p-1)=1mod(p)

Proof: Follows from Fermat's theorem.

Lemma3: If k is the least non-zero number such that 5^k=1mod(p), then either k=125 or k|125.

Proof: If there is no k<125, then according to lemma1, k=125 is the least number
for which 5^k=1mod(p). If there is a k less then 125 satisfying 5^k=1mod(p), then
let 125=kx+r where r is the reminder after Euclidean division of 125 by k. Hence
0<r<k. Lemma1 and 5^k=1mod(p) implies that 5^r=1mod(p) and hence, there is a number less than
k satisfying 5^r=1mod(p) against our assumption that k is the least of such non-zero
numbers. Hence r has to be =0 and k|125.

Lemma4: (n,5-1)=(n,5^5-1)
=(n,5^25-1)=(n,5^25+1)=(n,5^50+5^25+1)=(n,5^75+5^50+5^25+1)=1.

(1+5^25+5^50+5^75+5^100,5-1)=1 (4 is has no other prime factor than
2 and n is odd).

(1+5^25+5^50+5^75+5^100,5^25-1)=(1+5^25+5^50+2*5^75,5^25-1)
=(1+5^25+3*5^50,5^25-1)=(1+4*5^25,5^25-1)=(5,5^25-1)=(5,-1)
=(5,4)=1.

Since (5^5-1)|(5^25-1), and since (n,5^25-1)=1,
(n,5^5-1)=1.

(1+5^25+5^50+5^75+5^100,5^25+1)=(5^50,5^25+1)=(-5^25,5^25+1)
=(1,5^25+1)=1.

(1+5^25+5^50+5^75+5^100,5^50+5^25+1)=(5^75+5^100,5^50+5^25+1)
=(-1,5^50+5^25+1)=(5^50+5^25,5^50+5^25+1)=(5^50+5^25,1)=1.

(1+5^25+5^50+5^75+5^100,5^75+5^50+5^25+1)=(5^100,5^75+5^50+5^25+1)
=(-(5^75+5^50+5^25),5^75+5^50+5^25+1)=(1,5^75+5^50+5^25+1)=1.

Lemma5: If a number divides n, then it cannot divide 5^k-1
for k=1,5,25,50,70 or 100.

Proof: Follows immideately from Lemma4.

Theorem: k=125 is the least number for which 5^k=1mod(p).

Proof: k|125 from lemma3. Hence k has to be 1,5,25, or 125.
From lemma5, a prime p which divides n cannot divide
any number of the form 5^k-1 for k=1,5,25. We know
from lemma1 that it holds for k=125 that 5^k=1mod(p).

Hence the least number for which 5^k=1mod(p) is
k=125. Q.E.D.