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$\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.

 

[haruspex]

I am not sure if I understand it correctly. 13 is a prime and it is not$\equiv$1(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 $\equiv$1(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.

 

[StatOnTheSide]

Please do let me know if you find anything wrong with this proof.

Even though I have not written it down, I feel the the whole thing can be proved for
prime factors of a generic number n=(d^d^e-1)/(d^d^(e-1)-1), e>1. A prime factor of n
must be such that the least k for which d^k=1mod(p) is k=d^e. This is just my guess and I might be wrong.

 

[Anti-Crackpot]

Please do let me know if you find anything wrong with this proof.

Even though I have not written it down, I feel the the whole thing can be proved for
prime factors of a generic number n=(d^d^e-1)/(d^d^(e-1)-1), e>1. A prime factor of n
must be such that the least k for which d^k=1mod(p) is k=d^e. This is just my guess and I might be wrong.

If you can prove that I think it would be great. It would be even more general than what I intially suggested. Good luck with it.

- AC

 

[StatOnTheSide]

Thanks very much AC. I will definitely try.

 

[haruspex]

Let the number n=1+5^25+5^50+5^75+5^100. Let the p be one of its factors.
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.

Rather than check your proof of lemma 4, I've tried to generalise a bit in the hope of getting insight into the underlying structure.
Let $n = \sum^{r-1}_{i=0}p^{ir^{t}}$ and q be a prime factor of n.
With any r-dimensional integer vector (a_i) we can associate the sum $\sum^{r-1}_{i=0}a_ip^{ir^{t}}$. Let D be the set of such vectors for which the sum is divisible by q.
D includes the 0 vector and the all-ones vector. It is closed under addition and subtraction. Since q divides $p^{ir^{t+1}}-1$, it is also closed under cyclic permutations of the co-ordinates. So D is a subspace, containing at least the subspace (x, x, ... x). If we could show that inclusion of just one more vector implied inclusion of (1, 0, 0...0) then it would follow that D consists of only that minimal subspace, so no non-empty proper subsum of $\sum^{i=r-1}_{0}p^{ir^{t}}$ is divisible by q.
For the specific case of r = 5, we have the following chains of inclusion (adopting an abbreviated notation here):
01000 $\Rightarrow$ 10000 etc.
11000 $\Rightarrow$ 00110 $\Rightarrow$ 11110 $\Rightarrow$ 00001
11100 $\Rightarrow$ 00011
10100 $\Rightarrow$ 01010 $\Rightarrow$ 11110
and so on
Thus for r = 5 we have the desired result.
5 maybe unique in this regard. E.g. it can't work for r = 11: putting p = 2, t = 1, the sum 1+2+4+16 is a factor of 2¹¹-1.

 

[StatOnTheSide]

Nice proof haruspex. Honestly, I am still learning linear algebra and abstract algebra so I cannot claim that I completely understand your proof. I follow bits and pieces of such material simply because I lack the background. Thanks very much for ckecking my claim with your lense of formal theory.

Thus for r = 5 we have the desired result.
5 maybe unique in this regard. E.g. it can't work for r = 11: putting p = 2, t = 1, the sum 1+2+4+16 is a factor of 2¹¹-1.

That is true. I also checked for r=4 and p=4. The statement is not true; however, in all the cases where p= a prime number and r<=p and is a prime as well, it seems to be true. It is most certainly true for p=r=3. It is also true for p=5 and r=3.

If you look at the proof, Lemma4 is the most important one. For Lemma4 to be true, I think it is sufficient that p is a prime and r<=p. The critical thing is the (p^p^(r-1)-1,n) =1 and
(1+p^p^(r-1)+...+p^(k*p^(r-1)),n)=1 for k<p-1. If r is prime, then this seems to hold for all k.

Again, I am guessing a lot of things here and most importantly, none of this seems to point me towards the proof of the statement 'n is composite'. If you guys can think of any strong directions in proving that, I'd greatly appreciate it if you can please let me know.