Results 1 to 5 of 5

Math Help - 7|2^k+1

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    1

    7|2^k+1

    I need help on proving 7|2^k+1 such that no integer k exists.

    I assume the to proof this I need to use contradiction, assume there is some k such that 7|2^k+1 . But Im having trouble finding a contradiction.

    Please help,
    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    If you can work with modular arithmetic, then you're done.


    You have to prove that there is no k such that 2^k+1 \equiv 0 (\bmod 7) \Leftrightarrow 2^k \equiv 6 (\bmod 7)
    Fermat's little theorem tells us that 2^6 \equiv 1 (\bmod 7)

    so consider the possible values of k modulo 6 :
    k=6k' \Rightarrow 2^k=(2^6)^{k'} \equiv 1 (\bmod 7)
    k=1+6k' \Rightarrow 2^k=(2^6)^{k'} \cdot 2^1 \equiv 2 (\bmod 7)
    k=2+6k' \Rightarrow 2^k=(2^6)^{k'} \cdot 2^2 \equiv 4 (\bmod 7)

    etc....
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    As you say, we will try to find a contradiction. First note that 7=2^3 -1

    The fact that 7|(2^k+1) implies 7|(2^{2k}-1) since 2^{2k}-1 = (2^k+1)\cdot (2^k -1)

    Now (2^3-1)|(2^{2k}-1) implies 3|(2k) thus 3|k and then k=3k' ( In general we have that (a^d-1)|(a^n-1) if and only if d|n )

    We then write 7|(2^{3k'}+1) that is 7|(8^{k'}+1) which is not possible since 8=7+1 and so 8^{k'}=7k''+1 (expand using the binomial theorem)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Consider the element 2 in the multiplicative group Z_7^\times=\{\pm1,\pm2,\pm3\} modulo 7.

    2 has order 3 in this group since 2^3\equiv1\pmod 7.

    And clearly -1\notin\left<2\right>=\{1,2,-3\} in Z_7^\times.

    \therefore\ 7\nmid2^k+1 for any k\in\mathbb Z^+.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by mathn00bsta View Post
    I need help on proving 7|2^k+1 such that no integer k exists.
    Hi mathn00bsta.

    JaneBennet has given a neat if slightly abstract proof. What it means is this:

    2^0\equiv1\pmod7
    2^1\equiv2\pmod7
    2^2\equiv-3\pmod7
    2^3\equiv1\pmod7

    Hence, writing k=3q+r where r=0,1,2, we have 2^k\equiv2^r\pmod7 and so 2^k is never congruent to -1 modulo 7 for any positive integer k.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum