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

  • 0
    So how would I approach this proof? I guess a Direct Proof would work best?2012-07-14
  • 1
    There is no proof strategy for a false statement. How would you approach a proof that $1+1=3$?2012-07-14
  • 0
    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?2012-07-14
  • 0
    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.2012-07-14
  • 0
    I see, thank you. Sorry for giving you such a hard time as I'm still new to this whole proofing thing. Would it be possible to prove it using Contradiction or Contrapositive?2012-07-14
  • 0
    There's no need for contradiction or contraposition; the two examples I've presented in my answer (the two grey boxes) are complete proofs.2012-07-14
  • 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
    Is there another way to prove this besides using Euler's totient theorem?2012-07-14
  • 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$