4
$\begingroup$

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

  • 0
    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$.2012-07-14

4 Answers 4

5

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

  • 1
    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.2012-07-14
4

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

1

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

  • 0
    Can you please check my other answer?2012-07-15
0

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$