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.

Thanks

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

3. 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)

4. 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^+.$

5. Originally Posted by mathn00bsta
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.$