## Prove that this number is not a prime number

 Quote by haruspex 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.

Recognitions:
Homework Help
 Quote by StatOnTheSide 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 5125-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 (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.

 Quote by 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.
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.

 Recognitions: Gold Member 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.
 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.
 Recognitions: Gold Member The result is a 5 digit repunit number base 5^25

 Quote by coolul007 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?

Recognitions:
Gold Member
 Quote by StatOnTheSide 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.

 Recognitions: Gold Member 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)

 Quote by 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)
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.

Recognitions:
Gold Member
 Quote by StatOnTheSide 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.

Recognitions:
Homework Help
 Quote by 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.
p=1+525+....+5100
and the proof seemed to rely on that. It's wrong, no? p is assumed to divide that, not be equal to it.

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

 Quote by 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.
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

 Thanks very much AC. I will definitely try.

Recognitions:
Homework Help
 Quote by StatOnTheSide 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 (ai) 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 211-1.