# Prove that $2^n \not \equiv 1 \pmod{n}$ for any $n > 1$.

I have proved this in following way.

Assume that $2^n \equiv 1 \pmod{n}$.

that means $n\mid(2^n -1)$.

but by proof by contradiction, for $n=3$ this does not hold and we can say $n \nmid (2^n-1)$.

Hence our earlier assumption is wrong.

So, by contradiction we can say that $2^n \not \equiv 1 \pmod{n}$ for any $n$.

My question is, Is this the correct formal proof ? Can I consider this as correct formal proof?

EDIT: If this is not correct, please provide one.

• No. The negation of the statement is that there exists some $n$ such that $2^n \equiv 1 \mod n$. Showing that this is false for the case $n = 3$ doesn't contradict this. Commented Nov 22, 2014 at 2:53
• using n=3 i just dis proved the fact that $n|2^n -1$. Not the whole proof. Commented Nov 22, 2014 at 2:55
• This is an insidious and subtle logical error. Again: what you want to show is that for all positive integer $n$, $2^n \not\equiv 1 \mod n$. The negation of that statement is: there exists some $n$ such that $2^n \equiv 1 \mod n$. Showing that this last statement is false for the case $n = 3$ does not show there is no such $n$ at all; only that it is not the case for $n = 3$. Commented Nov 22, 2014 at 2:57
• "So, by contradiction we can say that $2^n\not\equiv1\pmod n$ for some $n$." Commented Nov 22, 2014 at 3:04
• "For any" is an English term that is not well defined in mathematics in the presence of a negation. Your sentence can be read as "2^n \equiv 1 \mod{n} is false for all $n \gt 1$" or as "2^n \equiv 1 \mod{n} is false for some $n \gt 1$. If the statement were positive it would clearly be "for all $n \gt 1$ Commented Nov 22, 2014 at 3:56

We have $2^1\equiv 1\pmod{1}$. Not very interesting! We show there are no others.

For suppose the congruence $2^n\equiv 1\pmod{n}$ holds, and $n\gt 1$. Let $p$ be the smallest prime divisor of $n$.

Then by Fermat's theorem, $$2^{p-1}\equiv 1\pmod{p}.$$ Also, since $p$ divides $n$, we have $$2^n\equiv 1\pmod{p}.$$

Let $d=\gcd(n,p-1)$. If $d\gt 1$ then $n$ has a divisor greater than $1$ but less than $p$, contradicting the choice of $p$.

Thus $d=1$, and therefore there exist integers $x$ and $y$ such that $(p-1)x+ny=1$. Since $2^{p-1} \equiv 1\pmod{p}$ and $2^{n}\equiv 1\pmod p$, we conclude that $2^1=2^{(p-1)x+ny}\equiv 1 \pmod{p}$. But $2^1\equiv 1\pmod{p}$ is impossible.

• Nice! This approach uses the fact that"if $gcd(n,p-1) = 1$, there exist integers x and y such that $(p−1)x+ny=1$". Do we have another approach? Commented Nov 22, 2014 at 7:12
• Yes, the Bezout "identity." I do not know another one, though this one can be reworded to make use of properties of order mod $p$. Commented Nov 22, 2014 at 7:16

"For any" is an English term that is not well defined in mathematics in the presence of a negation. Your sentence can be read as "$2^n \equiv 1 \mod{n}$ is false for all $n \gt 1$" or as "$2^n \equiv 1 \mod{n}$ is false for some $n \gt 1$. If the statement were positive it would clearly be "for all $n \gt 1$" If you read it as "$2^n \equiv 1 \mod{n}$ is false for some $n \gt 1$ the example you have shown is sufficient. If you read it as "$2^n \equiv 1 \mod{n}$ is false for all $n \gt 1$" one example is not sufficient-you need to prove the failure for all $n \gt 1$

Here's another pass at this:

Suppose for some $k$, we have a positive integer $m$ such that $2^k-1 = mk$. Or, $2^k \equiv 1 (m)$

Therefore, in the vector space $\mathbb{F}_2^k$, there are $mk$ non-zero vectors. Partition these into $m$ disjoint sets of $k$ vectors: $S_i$ for $i=1,2, \ldots m$. Choose vectors $v_i \in S_i$ to form $\{v_1, v_2, \ldots v_k\}$. Now for any other vector, $w$, not in this set, the collection $\{v_1, v_2, \ldots v_k\}\cup\{w\}$ is linearly dependent. Therefore, the set spans $\mathbb{F}_2^k$ and thus it is a basis. Therefore, the number of possible bases is $m^k$. But then, $o(GL_k(\mathbb{F}_2)) = (2^k-1)(2^k-2)\ldots(2^k-2^{k-1})$

Older attempt

Hope this is right. Suppose there is a $k$ such that $2^k - 1 \equiv 0 (k)$.

That is, $1+2+2^2+ \ldots +2^{k-1} \equiv 0 (k)$, or, adding the two up:

$2+2^2+\ldots +2^k \equiv 0 (k)$

But this can't be since $(2,k)=1$ as, by hypothesis, $2$ is invertible in $\mathbb{Z}/k\mathbb{Z}$

• This isn't right either. $(1,k)=1$ but $1+1^2+1^3+\cdots+1^k\equiv 0\pmod{k}$. Commented Nov 22, 2014 at 3:34
• I am not able to understand what's wrong! Will you elaborate? Commented Nov 22, 2014 at 3:37
• One cannot derive a contradiction from $2+2^2+\cdots+2^k\equiv 0\pmod{k}$ using only the fact that $2$ is a unit. It's not sufficient, because the same equation holds for $1$ and $1$ is a unit. Commented Nov 22, 2014 at 3:39
• I think I get it, thanks! :) Commented Nov 22, 2014 at 3:40

A solution related to one of the above answers goes as follows:

Assume that $$2^n \equiv 1 (n)$$ for some natural number $$n>1$$. Let $$h$$ be the least natural number such that $$2^h \equiv 1 (n)$$. Since $$n>1$$ we have that $$h>1$$. At the same time we know that $$2^{\phi(n)} \equiv 1 (n)$$. Since $$\phi(n) < n$$ this gives that $$h.

We can write $$n = kh + r$$ for some $$0 \leq r < h$$. This gives $$2^n = (2^h)^k \cdot 2^r \equiv 2^r (n)$$. Thus $$2^r \equiv 1 (n)$$. The assumption on the minimality of $$h$$ implies that $$r=0$$ and $$h \mid n$$. Thus we get a new solution $$h to the equation $$2^x \equiv 1 (x)$$ ($$x>1$$).

But this implies that we have an infinite descending chain of natural numbers $$n \rightarrow h \rightarrow h' \rightarrow h'' \rightarrow \dots$$ which is impossible.