Find the remainder of $2^{11}$ by $23$

My attempt was:

By Fermat's little theorem:
$$2^{22} \equiv 1 \pmod{23}$$ $$(2^{11})^2 \equiv 1 \pmod{23}$$

I checked with my calculator the remainder is actually $1$. However, I wonder if I can take the square root on both sides of congruence. Any idea?

Thanks,

• Actually you can, because then you would be reasoning in the finite field of order 23, where the equation $x^2-1$ factors into $(x+1)(x-1)$. However, you would still need to exclude the other possibility that $2^{11} = -1$ somehow. – Myself Feb 28 '11 at 5:46
• @Bill Dubuque: Thanks for your feedback, I will keep this in mind. – Chan Feb 28 '11 at 20:03

Yes you can take the square root, the elements $\{0,1,2, \dots, 22\}$ form a finite field, when the operations are taken modulo $23$.

That only tells you that it is $\pm 1$, though.

• @Moron: But the remainder of a number ranging from 0 -> quotient. How could it be -1? Could you explain this? Thanks. – Chan Feb 28 '11 at 5:49
• @Chan: 22 = -1... – Aryabhata Feb 28 '11 at 5:51
• @Moron: Thanks, I understood that 23|(22 + 1). What I did not understand is how $-1$ is called remainder, since $-1 < 0.$ – Chan Feb 28 '11 at 6:10
• @Chan: Modular arithmetic allows for negative numbers. -1 becomes 22, if you want a number between 0 and 22. – Aryabhata Feb 28 '11 at 6:32
• Saying "you can take square roots" because you're in a finite field is a little dangerous to those who might take it at face value: only half the nonzero elements have square roots, and those that do have two of them. (And yes, this is analogous to $\mathbb{R}$, but there the negative sign is very helpful. – Fixee Feb 28 '11 at 7:47

$\left( \frac{2}{23}\right) = 1 \Rightarrow 2^{11} \equiv 1 \left( \bmod 23 \right)$

• Sivaram, what is the first symbol mean (2/23)? – Digital Gal Mar 1 '11 at 17:03
• @Mike: The symbol is the Legendre symbol. en.wikipedia.org/wiki/Legendre_symbol – user17762 Mar 1 '11 at 17:32

Hint $$\rm\ \bmod\ 23\!:\ \ 2 \equiv 5^{\large2}\, \Rightarrow\, 2^{\large11} \equiv 5^{\large 22} \equiv 1\$$ by Fermat's little Theorem.

See Euler's Criterion and quadratic reciprocity to understand what happens generally.

Regarding square-roots, $$\rm\ x^2 = a^2\ \iff\ (x-a)\ (x+a) = 0\ \iff\ x = \pm\: a\ \$$ holds true in any integral domain, i.e. it's true in any ring without zero-divisors. More concretely, in $$\rm\ \mathbb Z/p\:,\:$$ we have prime $$\rm\ p\ |\ (x-a)\ (x+a)\ \Rightarrow\ p\ |\ x-a\$$ or $$\rm\ p\ |\ x+a\:,\:$$ so $$\rm\ x \equiv \pm\: a\ \ (mod\ p)\:.$$

• @Siva: If the OP knew such advanced techniques he wouldn't be asking this question. – Bill Dubuque Feb 28 '11 at 6:30
• @Siv: I think Bill was trying to avoid using the Legendre symbol, and stick to stuff at the level of Fermat's Little Theorem which the OP knows. Presumably if the OP could already read and understand your notation, he may not have asked the question. :-) – ShreevatsaR Feb 28 '11 at 6:30
• @Shreevatsa: Neither this nor Siva's answers answer the question as asked. The question was "Can I take square roots?" Chan already knew that the remainder was 1. Of course, the title does not exactly match the body. – Aryabhata Feb 28 '11 at 6:36
• @Bill: I thought you wanted to prove that $2$ was a quadratic residue and hence I thought you wrote $2=5^2$ and hence my previous comment. – user17762 Feb 28 '11 at 6:36
• @Moron: If you think about it more deeply you will see that it does answer his question generally. – Bill Dubuque Feb 28 '11 at 6:38