2
$\begingroup$

$2.\,\,$Do the following computations.

$\text{(a)}$ Solve the equation $x^2\equiv 1\mod15$

Solution:
We only need to choose a complete representative set modulo $15$ and verify the equation over such a set. In the following table, we choose the representative set $$\{0,\pm1,\pm2,\pm3,\pm4,\pm5,\pm6,\pm7\}$$ and verify the equation as follows: $$ \begin{array}{c|c} x & 0 & \pm 1 & \pm 2 & \pm 3 & \pm 4 & \pm 5 & \pm 6 & \pm 7 \\ \hline x^2 & 0 & 1 & 4 & -6 & 1 & -5 & 6 & 4 \\ \end{array} $$

We see that the equation has four solutions: $\pm1$ and $\pm 4$.

(Note that $15$ is not a prime, so we do not just have two square roots!)

I understand that if you do $8^2 \mod 15 $, $9^2 \mod 15$, $10^2 \mod 15$, and so forth, you get repetitions of the above representative set. What I don't understand is how you could know this before doing those calculations manually.

$\endgroup$
3
$\begingroup$

If you really wanted to, you could choose the set $\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$, but notice that $8 \equiv -7 \mod 15$, $9 \equiv -6 \mod 15$, etc. So then it is more convenient to choose the representative set $\{0, \pm 1, \pm 2, \pm 3, \pm 4, \pm 5, \pm 6, \pm 7\}$. This cuts down the amount of work from $15$ computations to $8$, as clearly $a^2 \equiv (-a)^2$.

$\endgroup$
  • $\begingroup$ well said I would say:) $\endgroup$ – user87543 Dec 10 '13 at 2:33
0
$\begingroup$

The set $\{1,2,3,...n-1\}$ is called complete residue set for number $n$. And all conguence relation modulo $n$ can be reduced to elements of this set.

Now for your question you can write $24$ as $(15 + 9)$ so $24^2 \equiv (15 + 9)^2 \equiv 15^2 + 270 + 9^2 \equiv 9^2 \pmod {15}$

And you need to check only the first $\frac{n}{2}$ numbers because we have: $9\equiv-6 \pmod{15}$ Now square and you'll get $(-6)^2 \equiv 6^2 \equiv 36 \pmod {15}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.