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,

  • 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
    @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)$

  • 0
    @Mi$k$e: The symbol is the Lege$n$dre symbol. http://en.wikipedia.org/wiki/Legendre_symbol2011-03-01
3

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)\:.$

  • 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