6
$\begingroup$

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,

  • 2
    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.2011-02-28
  • 0
    It's a *bad* idea to accept answers so quickly. Here you've accepted one that is far off the mark. Better to wait at least a day or two till many experts can see your query. Note: you can change your accepted answer. This will help to better guide other readers.2011-02-28
  • 0
    @Bill Dubuque: Thanks for your feedback, I will keep this in mind.2011-02-28

3 Answers 3

2

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.

  • 0
    @Moron: But the remainder of a number ranging from 0 -> quotient. How could it be -1? Could you explain this? Thanks.2011-02-28
  • 1
    @Chan: 22 = -1...2011-02-28
  • 0
    @Moron: Thanks, I understood that 23|(22 + 1). What I did not understand is how $-1$ is called remainder, since $-1 < 0.$2011-02-28
  • 0
    @Chan: Modular arithmetic allows for negative numbers. -1 becomes 22, if you want a number between 0 and 22.2011-02-28
  • 0
    @Chan: mod 23, you have -1 ≡ 22 ≡ 45 ≡ -24 ≡ -47, etc. Squaring any of them gives 1 modulo 23, so each of them is a square root of 1 (well, the *same* square root). The other square root is 1 ≡ 24 ≡ 47 ≡ -22 ≡ -45, etc. For convenience, we can write these two square roots as -1 and 1, which, if you want to have remainders in the range 0 to 22, is the same as 22 and 1.2011-02-28
  • 1
    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.2011-02-28
  • 0
    @Fixee: I interpreted the question as, if the the square of a number has a remainder which is itself a square, can we take square roots? That seemed to be a natural question one might have.2011-02-28
3

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

  • 1
    Sivaram, what is the first symbol mean (2/23)?2011-03-01
  • 0
    @Mike: The symbol is the Legendre symbol. http://en.wikipedia.org/wiki/Legendre_symbol2011-03-01
3

HINT $\rm\ \ mod\ 23\::\ \ 2\ \equiv\ 5^{\:2}\ \ \Rightarrow\ \ 2^{\:11}\ \equiv\ 5^{\: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)\:.$

  • 1
    @Siva: If the OP knew such advanced techniques he wouldn't be asking this question.2011-02-28
  • 0
    @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. :-)2011-02-28
  • 0
    @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.2011-02-28
  • 0
    @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.2011-02-28
  • 0
    @Moron: If you think about it more deeply you will see that it *does* answer his question generally.2011-02-28
  • 0
    @Siv: I noted $\rm\ 2\equiv 5^2\ $ which proves quite simply that $2\:$ is a square $\rm\ (mod\ 23)$. So I don't understand your comment.2011-02-28
  • 0
    @Moron: Well, it answers the question in the title. :-) This is always a problem with interpreting what the question asks…2011-02-28
  • 0
    @Shree: I agree, but I guess OP agrees with my interpretation...2011-02-28
  • 0
    @Moron: Your "answer" is far from answering the titled question.2011-02-28
  • 0
    @all: I really apologize for the confusing title. The true question that I wanted to ask was "if I can take the square root on both sides of congruence". However, I want name my question as a problem statement because it would be more convenient for searching. Most of the time, I want hints; sometimes I want the answer, not because it was my homework, I want to see how the problem being solved in a different way.2011-02-28