# Prove the following number theoretic assertion.

Prove that there doesn't exist any positive integer $n$ such that $7 \mid (2^n+1)$.

My Approach:

For $n=1$, it is clear that $7 \not\mid 3$. We suppose that $7 \mid (2^n+1)$ for every positive integer $n>1$.

Note that $2^n \equiv -1 \equiv 6$ (mod $7$ ) ,i.e., $2^{n-1}\equiv 3$ (mod $7$) since $gcd(2,7)=1$. Now there are two possibilities. If $n-1=1$, then we get a contradiction since $2\equiv3$ (mod $7$) is not true. If $n-1>1$, then ,by our supposition , $2^{n-1}\equiv -1$ (mod $7$). By combining above, we get $-1\equiv 3$ (mod $7$) which is absurd & again we get a contradiction.

So there doesn't exist any positive integer $n$ such that $7 \mid (2^n+1)$.

The above proof doesn't seem right to me. Please anyone tell me about the correctness of my proof.

• I think you've been wanting to construct a proof by induction. What such a proof needs is: assume $7 \not\mid 2^i+1$ for $i<n$; then you need to prove $7 \not\mid 2^n+1$. However, I don't offhand see how to make it work. Your mistake, I think, is an incorrect induction assumption, namely that $7 \mid 2^i+1$ for $i<n$. – ForgotALot Apr 28 '17 at 4:13

$2^0 \equiv 1$ mod 7 ==> $2^0+1 \equiv 2$ mod 7
$2^1 \equiv 2$ mod 7 ==> $2^1+1 \equiv 3$ mod 7
$2^2 \equiv 4$ mod 7 ==> $2^2+1 \equiv 5$ mod 7
$2^3 \equiv 8 \equiv 1$ mod 7. ==> $2^3+1 \equiv 2$ mod 7
Because the powers of 2 modulo 7 are cyclic with period 3, and none of the numbers in the period divide 7, there cannot be an $n$ such that $7|2^n+1$.