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.

  • $\begingroup$ 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$. $\endgroup$ – ForgotALot Apr 28 '17 at 4:13

Your proof is a bit hard to follow. Consider this proof.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.