Divisibility Problem

Printable View

September 16th 2010, 05:09 AM
Markeur

Divisibility Problem

Show that if $n>1$ is an integer such that $n$ divides $2^n+1$ then $3$ divides $n$ .
September 16th 2010, 05:53 AM
MathoMan

Quote:

Originally Posted by Markeur

Show that if $n>1$ is an integer such that $n$ divides $2^n+1$ then $3$ divides $n$ .

Obviously n has to be an odd number. I know it gets you nowhere but its a start, and maybe someone will get motivated to tackle this problem.
September 16th 2010, 06:10 AM
undefined

Quote:

Originally Posted by MathoMan

Obviously n has to be an odd number. I know it gets you nowhere but its a start, and maybe someone will get motivated to tackle this problem.

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 $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 $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.
September 16th 2010, 06:17 AM
MathoMan

Could you be more specific? I know it'll be a spoiler but I am really curious, and I'guess too tired (or stupid) to see where you're going with this one. :)
September 16th 2010, 06:24 AM
undefined

Quote:

Originally Posted by MathoMan

Could you be more specific? I know it'll be a spoiler but I am really curious, and I'guess too tired (or stupid) to see where you're going with this one. :)

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.

$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.
September 16th 2010, 06:36 AM
MathoMan

Thanks for the effort. When you say
$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 $a^p\equiv a \pmod{p}$ where p is prime number, not odd. Am I completely lost here, or what?
September 16th 2010, 06:40 AM
MathoMan

I get it now... Sorry for bothering you. I really should get some sleep now.
September 16th 2010, 06:44 AM
undefined

Quote:

Originally Posted by MathoMan

I get it now... Sorry for bothering you. I really should get some sleep now.

Don't sweat it! Glad to help.
September 16th 2010, 07:40 AM
melese

Quote:

Originally Posted by undefined

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

To undefined.
I understood that you've shown that if $n$ is odd, then $2^n+1$ is divisible by $3$ . However, the OP asks to show that $n$ will be divisible by $3$ if $n>1$ divides $2^n+1$ . Am I missing something?
September 16th 2010, 07:51 AM
undefined

Quote:

Originally Posted by melese

To undefined.
I understood that you've shown that if $n$ is odd, then $2^n+1$ is divisible by $3$ . However, the OP asks to show that $n$ will be divisible by $3$ if $n>1$ divides $2^n+1$ . Am I missing something?

Ah you're right, I got completely mixed up. n > 1 and n | 3k does not imply 3 | n. I will review.
September 16th 2010, 08:15 AM
undefined

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)
September 16th 2010, 11:36 PM
MathoMan

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 $n$ has to be odd. Lets play fair and point out why:

Assume $n$ is even. It can be written down as $n=2l$ . If $n$ divides $2^n+1$ then there exists a natural number $k$ such that equation $2^n+1=k\cdot n$ . Using the assumption that $n$ is even we get $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 $n$ is even cannot be true. Hence $n$ must be an odd number.

Now $n$ can be written down as $n=2l+1$ . Again because $n$ divides $2^n+1$ we form the equation $2^n+1=k\cdot n.$ . Now here's what I did:
$(3-1)^n+1=kn,$ and use binomial theorem.
$\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.
$\sum\limits_{i=0}^{n-1}{n\choose i}3^{n-i}(-1)^i+3^0(-1)^n+1=kn.$ Since $n$ is odd $(-1)^n=-1$ .
$\sum\limits_{i=0}^{n-1}{n\choose i}3^{n-i}(-1)^i-1+1=kn.$
$\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
$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.
September 17th 2010, 01:34 AM
undefined

Quote:

Originally Posted by MathoMan

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;

$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 .. (Rofl)

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 $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!
September 17th 2010, 05:40 AM
Markeur

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.