Results 1 to 5 of 5

Thread: 7|2^k+1

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    1

    7|2^k+1

    I need help on proving $\displaystyle 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 $\displaystyle 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 $\displaystyle 2^k+1 \equiv 0 (\bmod 7) \Leftrightarrow 2^k \equiv 6 (\bmod 7)$
    Fermat's little theorem tells us that $\displaystyle 2^6 \equiv 1 (\bmod 7)$

    so consider the possible values of k modulo 6 :
    $\displaystyle k=6k' \Rightarrow 2^k=(2^6)^{k'} \equiv 1 (\bmod 7)$
    $\displaystyle k=1+6k' \Rightarrow 2^k=(2^6)^{k'} \cdot 2^1 \equiv 2 (\bmod 7)$
    $\displaystyle 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 $\displaystyle 7=2^3 -1$

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

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

    We then write $\displaystyle 7|(2^{3k'}+1)$ that is $\displaystyle 7|(8^{k'}+1)$ which is not possible since $\displaystyle 8=7+1$ and so $\displaystyle 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 $\displaystyle Z_7^\times=\{\pm1,\pm2,\pm3\}$ modulo 7.

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

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

    $\displaystyle \therefore\ 7\nmid2^k+1$ for any $\displaystyle 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 $\displaystyle 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:

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

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

Search Tags


/mathhelpforum @mathhelpforum