For $n \geq 2$, show that $n \nmid 2^{n}-1$

Here is a problem which i have not been able to do for quite sometime.

• For $n \geq 2$, show that $n \nmid 2^{n}-1$.

I have thought of proving this in two ways: One by using induction which didn't actually work. Next by Fermat's little theorem we have $2^{p-1} \equiv 1 \ (\text{mod} \ p)$, which actually says that for $p \mid 2^{p}-2$. But i couldn't proceed more than this. Any ideas by which i can actually solve the problem?

Solution 1:

Hint $\ \ $ Prime $\rm\ P\mid N\ \Rightarrow\ 2^{P-1}\equiv 1\equiv 2^N\ \Rightarrow\ 2^{(P-1,\,N)} \equiv 1\ \ (mod\ P)\ $

But if $\rm\:P\:$ is the least prime factor of $\rm\:N\:$ then $\rm\ (P\!-\!1,N) = 1.$

I.e. $\rm\ mod\ P\ $ the order of $\rm\:2\:$ is $\:1\:$ since it divides the coprime integers $\rm\:P\!-\!1\:$ and $\rm\:N.$

Note $\ $ This problem was posted to sci.math on 2009\11\03. $\ $ There I remarked that the proof shows that if $\rm\ A^N\! = 1,\ A\neq 1\,$ then the order of $\rm\:A\:$ is $\,\ge\,$ the least prime factor $\rm\:P\:$ of $\rm\:N.\,$ In particular this implies that $\rm\ A^{P-1}\!\ne 1,\, $ which settles the problem at hand.

--- For completeness here is a proof of a slightly more general result.

Theorem $\,\ \ \ m,n>1,\,\ m\mid 2^{\large n}-1\,\Rightarrow\, \ell(m) > \ell(n),\ \ $ $\ell(x) =\,$ least prime factor of $\,x $

Proof $\quad\ \, {\rm mod}\,\ q = \ell(m)\!:\,\ 2^{\large n}\equiv 1\equiv\, 2^{\large\color{}{q-1}}\,$ $\Rightarrow$ $\,\ \ell(m) = q > {\rm ord}\,2\color{#80f}{ \ge \ell(n)}$

Remark $\,\ $ The $ $ key idea $ $ is: $\ \ 2^n\equiv 1,\,\ \color{#0a0}{2\not\equiv 1}\,$ implies the order of $\,2\,$ is $\,\color{#80f}{\ge\ {\rm least\ prime}\,\ p\mid n},\ $ because the order must divide $\,n,\,$ and is $\color{}{\neq \color{#c00}1}$ (else $\,\color{#0a0}{2^{\color{#c00}{\large 1}}\equiv 1}),\,$ and the least divisor $>1$ of $\,n\,$ is its least prime factor (by existence and uniqueness of prime factorizations).

See here for a generalization $\,n\mid b^n - c^n.$

Solution 2:

You can look at this modulo the smallest prime factor $p$ of $n$.

Write $n=p^rm$ where $m$ is a product of primes greater than $p$. Then $m$ will be coprime to $p-1$, so $ma\equiv1\pmod{p-1}$ for some positive integer $a$. Now use Fermat's little theorem $$ (2^n)^a=2^{p^rma}\equiv2^{p^r}\equiv2\not\equiv 1\pmod p. $$

[Edit: Even better - $n$ will be coprime to $p-1$, as Bill notes in his answer, so there is no need to extract out the $p^r$ factor.]