# 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?

-

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 dea  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},\,$ i.e. the least nontrivial divisor of $\,n\,$ is its least prime factor (by uniqueness of prime factorizations).

-
Thanks bill – anonymous Feb 5 '11 at 3:51
I have attempted something. Please see if it's correct, and if there is a mistake i request you to help me out. – anonymous Feb 13 '11 at 16:00
Thanks for pointing out the mistake – anonymous Feb 13 '11 at 17:11
How did you find that mistake bill. Great, i couldn't find anything while i was trying to prove it. Feels bad, since my efforts have gone waste :x) – anonymous Feb 16 '11 at 16:24
@Saurabh Suppose, for contradiction, $\rm\:N\:|\:2^N\!-\!1,\:$ and prime $\rm\:P\:|\:N.\:$ Since $\rm\:2^N\!-\!1\:$ is odd, so is $\rm\:P.\:$ Now $\rm\:P\:|\:N\:|\:2^N\!-\!1\:\Rightarrow\:2^N\equiv 1\pmod P.\:$ Also $\rm\:2^{P-1}\equiv 1\pmod P\:$ by little Fermat. By Bezout, $\rm\:gcd(N,P\!-\!1)\, =\, J\:N+K\:(P\!-\!1)\:$ for $\rm\:J,K\in \mathbb Z.\:$ Hence $$\rm 2^{gcd(N,P-1)} \equiv 2^{\:J\:N+K\:(P-1)} \equiv (2^N)^{\!\:J} (2^{P-1})^K \equiv 1^J\, 1^K \equiv 1\pmod P$$ – Bill Dubuque Jun 11 '12 at 17:07

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=1$ (mod $p-1$) for some positive integer $a$. Now use Fermat's little theorem $$(2^n)^a=2^{p^rma}=2^{p^r}=2\not=1\qquad{\rm(mod\ }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.]

-