Prove that this number is not a prime number

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

 

[haruspex]

For now, just an addendum to my previous post. For r = 7, all attempts to include extra vectors quickly lead to 1000000 except this pattern: 1101000 (and cyclic rotations and reversals of same). For that case, 1101000 -> 0110100 and 0100011, whence 1311111 and thus 0200000. Now, I lied when I said D is a vector space - it isn't closed under division by scalars. But since r = 7 is odd, n is odd, so q > 2. Hence this line of reasoning also works for r = 7 (as well as 2, 3, and 5).
Not sure about r <= p being sufficient. I'll see if I can get anywhere with that.

And as you say, none of this seems to get us very far with the OP.

 

[StatOnTheSide]

Hence this line of reasoning also works for r = 7 (as well as 2, 3, and 5).
Not sure about r <= p being sufficient. I'll see if I can get anywhere with that.

That is pretty cool. No wonder Linear Algebra and Abstract Algebra are very important in pure math. It is amazing to see how these tools can be used to dig out facts. Thanks very much for your input haruspex.

I will update the post in case I can make any progress regarding the main problem.

 

[Anti-Crackpot]

Haruspex, I like the way you're applying abstract/linear algebra to number theory. Do you happen to have a specific book you could recommend?

- AC

 

[StatOnTheSide]

I found the solution. This problem happens to be an olympiad problem and I got the solution to it from a book. Sameful but was really the last resort given that I did not go anywhere with it by working it out by myself. Here it is

Observe that x^4 +x^3 +x^2 +x+1 = (x^2 +3x+1)^2 -5x(x+1)^2. Thus for

x = 5^25 we have

N = x^4 + x^3 + x^2 + x + 1
= (x^2 + 3x + 1 - 5^13*(x + 1))(x^2 + 3x + 1 + 5^13(x + 1))
= A · B.

Clearly, both A and B are positive integers greater than 1.

 

[StatOnTheSide]

It is really interesting to see the such olympiad problems have trivial solutions. Initially, it looks like the solution is really complicated. But when you look at the solution, it turns out to be really really simple.

How do people actually manage to solve such problems without assitance? Are they extraordinarily intelligent or does God speak to them in the ears giving the solution? Many of you are real experts. Please let me know as to how I can improve my problem solving ability. I am really very far from giving an olympiad exam. I am an engineer and am like 32 years old. All I want to do is gain confidence and solving the tough problems from the olympiads will really give me that confidence. If after having tried for so many days, I could not figure it out, does it mean that I won't be able to figure out solutions to olympiad problems if I try forever? What can I do to be able to eventually start being able to solve such problems? Please do let me know what you think as your suggestions matter to me a great deal.

 

[acabus]

Despite the fact I got next to nowhere with it, that was a really fun problem.

 

[Anti-Crackpot]

I found the solution. This problem happens to be an olympiad problem and I got the solution to it from a book. Sameful but was really the last resort given that I did not go anywhere with it by working it out by myself. Here it is

Observe that x^4 +x^3 +x^2 +x+1 = (x^2 +3x+1)^2 -5x(x+1)^2. Thus for

x = 5^25 we have

N = x^4 + x^3 + x^2 + x + 1
= (x^2 + 3x + 1 - 5^13*(x + 1))(x^2 + 3x + 1 + 5^13(x + 1))
= A · B.

Clearly, both A and B are positive integers greater than 1.

And...
((n^(n^2))^2 +3(n^(n^2))+1)^2 -5(n^(n^2))(n^(n^2)+1)^2
=
n^(0 n^2) + n^(1 n^2) + n^(2 n^2)+n^(3 n^2)+n^(4 n^2)

A form you and I both came across along the way.

Btw, in terms of confidence building, getting the solution is exactly what a good engineer is supposed to do. One way or another. And you got the solution, even if from a book (And even if you had the book all along). Also, fwiw, seems more than a few people were stumped, including those who are experts.

- AC

 

[StatOnTheSide]

It is so true isn't it AC? When I think back, I cannot figure out as to why I missed it. It is really discouraging to think of inability to solve math olympiad problems. It makes me wonder if I can become an accomplished mathematician when I can not solve these problems meant for high school kids, be it for the "brighter" ones.

There is a website where accomplished mathematicians have said you can ignore it if you cannot solve such problems.
http://lesswrong.com/lw/2v1/great_mathematicians_on_math_competitions_and/

I am not sure if they are being honest or if they are just being nice and encouraging for the less gifted kids like myself.

 

[Anti-Crackpot]

It is so true isn't it AC? When I think back, I cannot figure out as to why I missed it. It is really discouraging to think of inability to solve math olympiad problems. It makes me wonder if I can become an accomplished mathematician when I can not solve these problems meant for high school kids, be it for the "brighter" ones.

One's measure should not be a specific skill set IMHO and that's exactly what these Olympiad-type problems test. But -- albeit advice from a non-expert -- if you expose yourself to enough of these types of problems you'll start to see patterns emerge and, you'll have a broader range of "math experience" to draw upon in solving such problems. Think in terms of Malcolm Gladwell and the 10,000 hours. Hard work and practice is what what potentiates innate talent, not just the innate talent or lack thereof itself. Even a real dummy can seem pretty smart if he or she works hard enough is my guess.

And you're no dummy.

I'll be interested to see what advice others have to give.

Meantime, EPGY Math Olympiad Problem Solving: http://math.stanford.edu/~paquin/epgyMO.html

- AC

P.S. Pragmatically speaking, one thing that was interesting about this problem is that you had to "go the other way" with it once reducing that factorization you and I both came across. Make it bigger and then subtract out before substituting terms back in for x...

(1 x^4 + 6 x^3 + 11 x^2 + 6 x + 1) 1st term multiplied out
-
(0 x^4 + 5 x^3 + 10 x^2 + 5 x + 0) 2nd term multiplied out
=
(1 x^4 + 1 x^3 + 1 x^2 + 1 x + 0)

Nice little trick to store away for another time. Curious if there's a name for that specific technique.

 

[StatOnTheSide]

Thanks AC. It is a nice link. I will try to go through it at some point. People usually speak of "tricks" and I have known some tricks but those are really restricted to a handful of known ones. Once I get cought in one line of thought, that is the end of it. If I get the solution in that line of thought, then fine. Else I end up with giving up simply because it is hard to end that line of tought and open a new one which might lead me to the solution. This is another useful website
http://hcmop.wordpress.com/2012/03/23/how-to-approach-an-olympiad-problem-by-ho-jun-wei/

I think I will continue to do math simply because I love the subject. I am not become an average mathematician either but I will have the satisfaction that I tried. I wish I was as bright as those olympiad winners but I think I will nevertheless just try to learn and enjoy.

Thanks for your encouragement AC. I really appreciate it.

 

[haruspex]

Lovely solution. One way this might have been found is by actively looking for a form as the difference of two squares.

 

[StatOnTheSide]

Hi haruspex. Expressing a polynomial as a difference of squares is an old trick in the book. I am still amazed at the fact that I did not even attempt the solution in that line of thought. I had to look at a solution from another book to figure this out.

Thanks for all the help. You are really very knowledgeable.

 

[coolul007]

if x= 5^25, when you "double down" x^4 = 0x^4 + (5^25)x^3 this only works if you know what x is. The example with x=5 is incorrect as x is clearly not 5. It is a fine point.