Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

4 Answers 4

up vote 4 down vote accepted

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

share|improve this answer
    
So how would I approach this proof? I guess a Direct Proof would work best? –  laser295 Jul 14 '12 at 15:57
1  
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
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. –  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$?

share|improve this answer

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

share|improve this answer
    
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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.