# Math Help - 7|2^k+1

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.

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

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

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

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