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,

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Myself
    Commented Feb 28, 2011 at 5:46
  • $\begingroup$ @Bill Dubuque: Thanks for your feedback, I will keep this in mind. $\endgroup$
    – roxrook
    Commented Feb 28, 2011 at 20:03
  • $\begingroup$ cf. this question $\endgroup$
    – J. W. Tanner
    Commented Nov 7, 2019 at 2:47

3 Answers 3

Reset to default
4
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Sivaram, what is the first symbol mean (2/23)? $\endgroup$
    – Mykie
    Commented Mar 1, 2011 at 17:03
  • $\begingroup$ @Mike: The symbol is the Legendre symbol. en.wikipedia.org/wiki/Legendre_symbol $\endgroup$
    – user17762
    Commented Mar 1, 2011 at 17:32
4
$\begingroup$

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, and see the Remark here for the analog with higher power residues.

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

$\endgroup$
10
  • 1
    $\begingroup$ @Siva: If the OP knew such advanced techniques he wouldn't be asking this question. $\endgroup$
    – Bill Dubuque
    Commented Feb 28, 2011 at 6:30
  • $\begingroup$ @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. :-) $\endgroup$
    – ShreevatsaR
    Commented Feb 28, 2011 at 6:30
  • $\begingroup$ @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. $\endgroup$
    – Aryabhata
    Commented Feb 28, 2011 at 6:36
  • $\begingroup$ @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. $\endgroup$
    – user17762
    Commented Feb 28, 2011 at 6:36
  • $\begingroup$ @Moron: If you think about it more deeply you will see that it does answer his question generally. $\endgroup$
    – Bill Dubuque
    Commented Feb 28, 2011 at 6:38
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ @Moron: But the remainder of a number ranging from 0 -> quotient. How could it be -1? Could you explain this? Thanks. $\endgroup$
    – roxrook
    Commented Feb 28, 2011 at 5:49
  • 1
    $\begingroup$ @Chan: 22 = -1... $\endgroup$
    – Aryabhata
    Commented Feb 28, 2011 at 5:51
  • $\begingroup$ @Moron: Thanks, I understood that 23|(22 + 1). What I did not understand is how $-1$ is called remainder, since $-1 < 0.$ $\endgroup$
    – roxrook
    Commented Feb 28, 2011 at 6:10
  • $\begingroup$ @Chan: Modular arithmetic allows for negative numbers. -1 becomes 22, if you want a number between 0 and 22. $\endgroup$
    – Aryabhata
    Commented Feb 28, 2011 at 6:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – Fixee
    Commented Feb 28, 2011 at 7:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .