# Prove that there exists a natural number n for which $11\mid (2^{n} - 1)$

I'm thinking putting it into modulo form: there exists a natural number $n$ for which

$$2^{n}\equiv 1 \pmod {11}$$

but I don't know what to do next and I'm still confused how to figure out remainders when doing modulos, like $2^n\equiv \;?? \pmod{11}$. Is there some pattern to find $??$ or you would have to use specific numbers for $??$ which is divisible by $11$?

-
If you have done Fermat's Theorem, it is immediate that $2^{11-1}\equiv 1 \pmod{11}$. If you haven't, it is probably best to compute powers of $2$ modulo $11$ until you bump into an answer. Calculation is easy, $2^4\equiv 5$ so $2^{5}\equiv 10$ so $2^6\equiv 9$ so $2^7 \equiv 7$ so $2^8\equiv 3$ so $2^9\equiv 6$ so $2^{10}\equiv 1$. –  André Nicolas Jul 14 '12 at 18:18

A natural number $n$ will have the property that $11\mid 2^n-1$ precisely when $n$ is a multiple of $10$.

$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|} n & \!\!\!\!\!& 1 & 2& 3& 4& 5& 6& 7&8&9&\mathbf{\Large 10}&11&12&13&14\\\hline\\ 2^n\bmod 11 & \!\!\!\!\!& 2 & 4& 8 &5 &10 &9 & 7&3 &6&\mathbf{\Large 1 }&2&4&8&5 \end{array}\;\;\cdots\;\;\begin{array}{|c|c|}19 &\mathbf{\Large20}\\\hline\\ 6&\mathbf{\Large1}\end{array}\;\;\cdots$$

To be even more explicit,

Here is a proof that there exists a natural number $n$ such that $2^n\equiv 1\bmod 11$. Consider $n=10$: $$2^{10}-1=1024-1=1023=3\times \fbox{11}\times 31$$ so that $11\mid 2^{10}-1$. Thus by definition $2^{10}-1\equiv0\bmod 11$, and therefore $2^{10}\equiv 1\bmod 11$.

and

Here is a proof that there exists a natural number $n$ such that $2^n\equiv 1\bmod 11$. Consider $n=20$: $$2^{20}-1=1,048,576-1=1,048,575=3\times 5^2\times \fbox{11}\times 31\times 41$$ so that $11\mid 2^{20}-1$. Thus by definition $2^{20}-1\equiv0\bmod 11$, and therefore $2^{20}\equiv 1\bmod 11$.

-
So how would I approach this proof? I guess a Direct Proof would work best? –  laser295 Jul 14 '12 at 15:57
There is no proof strategy for a false statement. How would you approach a proof that $1+1=3$? –  Zev Chonoles Jul 14 '12 at 15:58
Yes, I understand that. Putting my false statement aside, how would I approach the proof of "there exists a natural number n for which 11|(2n−1)" then, or were you saying that statement was false? –  laser295 Jul 14 '12 at 16:01
To prove that there exists a natural number $n$ that has some property, usually the easiest proof is to present an example of such an $n$ and simply demonstrate that that specific $n$ has the desired property. I have given two examples in my answer. –  Zev Chonoles Jul 14 '12 at 16:03
Here we see exhibited the first stumbling block that one new to mathematics will face: how to recognize a proof. I think all of us must have passed through this stage. Tom Banchoff told me a story of a student coming to his office asking what more was needed to complete a proof, and showed Tom what he had. It was a perfect proof by induction, needed not a single word more. But the student didn’t realize that he had already done the job. –  Lubin Jul 14 '12 at 18:21

Hint: The number of different values $2^n \bmod 11$ can take is finite, while the number of values $n \in \mathbb{N}$ is infinite. So by the pigeonhole principle, there exist two different natural numbers $n,m$ such that $2^n \equiv 2^m \mod 11$. Can you then find a natural number $k > 0$ such that $2^k \equiv 1 \mod 11$?

-

According to Euler's totient theorem, $a^n\equiv 1\pmod{m}$ if $\phi(m)\mid n$, where $(a,m)=1$.

As $(11,2)=1$, you must get solutions which are multiple of $\phi(11)=10$.

-
Is there another way to prove this besides using Euler's totient theorem? –  laser295 Jul 14 '12 at 15:56
Can you please check my other answer? –  lab bhattacharjee Jul 15 '12 at 5:07

Let $2^n$ leaves different remainders when divided by 11.

Now there can be 11 different remainders. Now if we can set of {$2^n$} where cardinality>11.

The remainders of at least two members of the set must be same (using Pigeonhole principle).

Let $2^s=r+11a$ and $2^t=r+11b$ where s>t

Subtracting, $2^{s-t}(2^t-1)=11(a-b)$.

So, 11 divides $2^{s-t}(2^t-1)$

But 11 can not divide $2^n$ as (2,11)=1 (=> remainder can not be 0)

So, 11 must divide $2^t-1$

-