Actually it doesn't get you nowhere.
From Fermat's little theorem (or Euler's theorem which is more general) we know without computing that . Thus we have two cases
Case 1: n is even, which like you said is easily ruled out
Case 2: n is odd, which implies that . From here there's hardly any work left to be done. Be sure to state why we need n > 1.
I'm not sure if you want me to clarify something I wrote, or complete the proof.
n divides a multiple of 3. Therefore n is either a unit (1 or -1) or is itself a multiple of 3. But n > 1 so n must be a multiple of 3.
Thanks for the effort. When you say
I don't see how you get the first implication.
It could easily be that my mind is a wreck right now so I hope you don't mind me noticing that I googled for Ferma's little theorem and it states that where p is prime number, not odd. Am I completely lost here, or what?
Still trying to see how to prove, but numerical data suggests that there may actually be stronger result: for any integer n > 0, n | n^2 + 1 iff n = 3^k for some non-negative integer k.
Edit: Nevermind, the sequence was misleading and I didn't go high enough, 1, 3, 9, 27, 81, 171, ... ha
Some interesting info here
Edit 2: All right, there is a proof here, see proposition 2, although to be honest I don't entirely follow it
Ok, its 9AM here in cloudy Croatia and I, being all fresh and daisy (not!), had to see what happened with this thread. I wrote a couple of lines on a piece of paper that I'd like to share with you and see if it gets us anywhere. So here goes.
We already established that has to be odd. Lets play fair and point out why:
Assume is even. It can be written down as . If divides then there exists a natural number such that equation . Using the assumption that is even we get This is not possible since on the left we definitely have an odd number and on the right we have an even number. Therefore the assumption that is even cannot be true. Hence must be an odd number.
Now can be written down as . Again because divides we form the equation . Now here's what I did:
and use binomial theorem.
now write last member of the sum outside the summation operator.
Since is odd .
. Now every term under summation operator has 3 as a factor, so using distributivity
There's a 3 right there. Shoot, I gotta go now. Someone please check if this sounds ok, and if it gets us anywhere closer to the solution?!
EDIT: well I'm back now but have some things sort out first. Anyway, if above is true it turns out that the product of numbers n and k is divisible by 3. Thus we have either k or n or both of them divisible by 3. Normally one should try to prove that k cannot be divisible by 3 and thus prove that n must be divisible by 3, but I wonder how to do that. Gotta go again.
The .pdf I referenced which had a proof seemed reputable enough, but it was written for an audience of experienced number theorists, which I am not. I'm not sure we really have to work towards a solution, since we already have a proof, but until someone understands it well enough to see if it's a valid proof, we have to take it on faith that the authors were correct. Perhaps a more elementary proof can be found without too much trouble and the authors were just showing off (or just wished to be brief). Or it could simply be that (somewhat) advanced techniques are required for this proof.
Or it could be that it's not that advanced and I simply don't know enough... from what I can tell, it's a 6 step proof, and I understand 2 of the steps.. heh
Edit: I think I've understood the first step now;
Only three steps left ..
Edit 2: Ah I now see how the fourth step obviously implies the fifth, so that's two steps remaining.
Edit 3: Okay, for the third step we can use and we know from Bezuot's identity that there exist k,m such that kb+mc=(b,c).
Edit 4: Okay, finally see that for the fourth step, (p-1)/2 can't possibly have any prime factors in common with n since we chose p the smallest, therefore (n,(p-1)/2)=1.
Proof looks good!
Thanks for your explanation. For your information, this question appeared in a final examination just a few months ago at one of the universities in Singapore. Apparently, almost no-one managed to solve this, except for one genius who has recently graduated as top student of the entire pure math cohort.