Results 1 to 14 of 14

Math Help - Divisibility Problem

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    63

    Divisibility Problem

    Show that if n>1 is an integer such that n divides 2^n+1 then 3 divides n.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Sep 2010
    Posts
    185
    Thanks
    13
    Quote Originally Posted by Markeur View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by MathoMan View Post
    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.
    Last edited by undefined; September 16th 2010 at 08:06 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2010
    Posts
    185
    Thanks
    13
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by MathoMan View Post
    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.
    Last edited by undefined; September 16th 2010 at 08:06 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Sep 2010
    Posts
    185
    Thanks
    13
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2010
    Posts
    185
    Thanks
    13
    I get it now... Sorry for bothering you. I really should get some sleep now.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by MathoMan View Post
    I get it now... Sorry for bothering you. I really should get some sleep now.
    Don't sweat it! Glad to help.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by undefined View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by melese View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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)
    Last edited by undefined; September 16th 2010 at 08:40 AM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Sep 2010
    Posts
    185
    Thanks
    13
    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.
    Last edited by MathoMan; September 17th 2010 at 01:25 AM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by MathoMan View Post
    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 ..

    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!
    Last edited by undefined; September 17th 2010 at 02:26 AM.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Mar 2010
    Posts
    63
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. problem with divisibility
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 8th 2010, 08:06 AM
  2. A divisibility problem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: August 19th 2010, 08:21 PM
  3. A problem about divisibility
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 29th 2010, 09:18 PM
  4. divisibility problem?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 24th 2010, 04:18 AM
  5. help this divisibility problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 29th 2008, 05:13 AM

Search Tags


/mathhelpforum @mathhelpforum