Show that if $\displaystyle n>1$ is an integer such that $\displaystyle n$ divides $\displaystyle 2^n+1$ then $\displaystyle 3$ divides $\displaystyle n$.
EDIT: Sorry I made a mistake, further discussion below.
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 $\displaystyle 2^2 \equiv 1\pmod{3}$. 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 $\displaystyle 2^n\equiv2^1\equiv2\pmod{3}$. From here there's hardly any work left to be done. Be sure to state why we need n > 1.
EDIT: Sorry I made a mistake, further discussion below.
I'm not sure if you want me to clarify something I wrote, or complete the proof.
$\displaystyle n\equiv 1\pmod{2}\implies 2^n\equiv2\pmod{3}\implies 2^n+1\equiv0\pmod{3}$
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
$\displaystyle n\equiv 1\pmod{2}\implies 2^n\equiv2\pmod{3}\implies 2^n+1\equiv0\pmod{3}$
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 $\displaystyle a^p\equiv a \pmod{p}$ where p is prime number, not odd. Am I completely lost here, or what?
To undefined.
I understood that you've shown that if $\displaystyle n $ is odd, then $\displaystyle 2^n+1 $ is divisible by $\displaystyle 3 $. However, the OP asks to show that $\displaystyle n $ will be divisible by $\displaystyle 3 $ if $\displaystyle n>1 $ divides $\displaystyle 2^n+1 $. Am I missing something?
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
http://www.research.att.com/~njas/sequences/A006521
Edit 2: All right, there is a proof here, see proposition 2, although to be honest I don't entirely follow it
http://www.maths.ed.ac.uk/~chris/n_d...2to_nplus1.pdf (pdf)
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 $\displaystyle n$ has to be odd. Lets play fair and point out why:
Assume $\displaystyle n$ is even. It can be written down as $\displaystyle n=2l$. If $\displaystyle n$ divides $\displaystyle 2^n+1$ then there exists a natural number $\displaystyle k$ such that equation $\displaystyle 2^n+1=k\cdot n$. Using the assumption that $\displaystyle n$ is even we get $\displaystyle 2^{2l}+1=2lk.$ 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 $\displaystyle n$ is even cannot be true. Hence $\displaystyle n$ must be an odd number.
Now $\displaystyle n$ can be written down as $\displaystyle n=2l+1$. Again because $\displaystyle n$ divides $\displaystyle 2^n+1$ we form the equation$\displaystyle 2^n+1=k\cdot n.$. Now here's what I did:
$\displaystyle (3-1)^n+1=kn,$ and use binomial theorem.
$\displaystyle \sum\limits_{i=0}^{n}{n\choose i}3^{n-i}(-1)^i+1=kn,$ now write last member of the sum outside the summation operator.
$\displaystyle \sum\limits_{i=0}^{n-1}{n\choose i}3^{n-i}(-1)^i+3^0(-1)^n+1=kn.$ Since $\displaystyle n$ is odd $\displaystyle (-1)^n=-1$.
$\displaystyle \sum\limits_{i=0}^{n-1}{n\choose i}3^{n-i}(-1)^i-1+1=kn.$
$\displaystyle \sum\limits_{i=0}^{n-1}{n-1\choose i}3^{n-i}(-1)^i=kn.$. Now every term under summation operator has 3 as a factor, so using distributivity
$\displaystyle 3\cdot\sum\limits_{i=0}^{n-1}{n\choose i}3^{n-i-1}(-1)^i=kn.$.
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.
That seems to be a major issue with this approach -- how do we know the exponent of prime 3 in the prime factorization of k? I don't know how that could be overcome.
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;
$\displaystyle p|n\land n|2^n+1\implies p|2^n+1\implies 2^n\equiv-1\pmod{p}\implies 2^{2n}\equiv 1\pmod{p}$
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 $\displaystyle a^b\equiv a^c\equiv 1\implies a^{kb+mc}\equiv 1$ 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.