# Thread: Another congruence problem

1. ## Another congruence problem

I missed a lecture where they discussed finding solutions to $x^2 \equiv -1 mod 13$ , and was given this problem to try out. Problem is, I don't even know how to start off since I don't even know how to do the above one.

If $p > 2 is prime$ and a member of Z, show that $X^2 \equiv a mod p$ has either no solutions or exactly 2 solutions mod p.

If it has 2 solutions, show that only one solution, $x$ , satisfies $0 <= x <= (p-1)/2$.

2. Originally Posted by Th3sandm4n
I missed a lecture where they discussed finding solutions to $x^2 \equiv -1 mod 13$ , and was given this problem to try out. Problem is, I don't even know how to start off since I don't even know how to do the above one.
There is nothing brilliant here, just good through the numbers $x=1,2,...,12$ and see which ones work.

Now for the second part if $x^2 \equiv a(\bmod p)$ where $(a,p)=1$ has a solution $x_0$ then $a\equiv x_0^2(\bmod p)$ and so $(x-x_0)(x+x_0) = x^2 - x_0^2\equiv 0 (\bmod p) \implies x\equiv \pm x_0(\bmod p)$.

3. Originally Posted by ThePerfectHacker
There is nothing brilliant here, just good through the numbers $x=1,2,...,12$ and see which ones work.

Now for the second part if $x^2 \equiv a(\bmod p)$ where $(a,p)=1$ has a solution $x_0$ then $a\equiv x_0^2(\bmod p)$ and so $(x-x_0)(x+x_0) = x^2 - x_0^2\equiv 0 (\bmod p) \implies x\equiv \pm x_0(\bmod p)$.
Okay let me just make sure I'm getting this correctly
we KNOW it has a solution (but we show that if it has a solution, it must has two?) $x_0^2$.
so then $x_0^2 \equiv a mod p$

So then,
$x^2 \equiv amodp$
$x^2 \equiv x_0^2 mod p$ (substituting)
$x^2 - x_0^2 \equiv 0 mod p$ (subtracting $x_0^2$ from both sides)
$(x-x_0)(x+x_0) \equiv 0 modp$ (factoring)

So then,
$x = x_0$or $x = -x_0 \equiv 0modp$
$x \equiv x_0 modp$
$x \equiv -x_0 modp$?

And then im guessing that $0 <= x_0 <= (p-1)/2$ holds because if it was greater than half of p, squaring it would mess it up?
And also $0>= -x_0 >=-(p-1)/2$.

4. Originally Posted by Th3sandm4n
Okay let me just make sure I'm getting this correctly
we KNOW it has a solution (but we show that if it has a solution, it must has two?) $x_0^2$.
so then $x_0^2 \equiv a mod p$
I said if it has a solution then it has two. Thus, it either has no solutions or two.

5. Ah, yes. I forget how important wording is in proofs sometimes.

EDIT:
Just a follow up for anyone else looking for something similar

One of the solutions is between $0<= x <= (p-1)/2$ because the field of $p = {0,...,p-1}$ and since there are exactly 2 solutions or no solutions, then one solutions must cover half the field, and the other cover the other half.

If I am correct in my thinking, barely covered fields on Friday.

6. Originally Posted by ThePerfectHacker
There is nothing brilliant here, just good through the numbers $x=1,2,...,12$ and see which ones work.
here is a quicker way

$x^2\equiv-1\pmod{13}\ \iff\ x^2\equiv25\pmod{13}\ \iff\ 13\mid x^2-25=(x-5)(x+5)$

hence the two solutions are 5 and 8 (mod 13)

7. Originally Posted by Th3sandm4n
If $p > 2$ is prime and a member of Z, show that $X^2 \equiv a mod p$ has either no solutions or exactly 2 solutions mod p.
That is actually false, as it stands. If $p\mid a$, then $x^2\equiv a\pmod p$ has infinitely many solutions.

8. Originally Posted by JaneBennet
That is actually false, as it stands. If $p\mid a$, then $x^2\equiv a\pmod p$ has infinitely many solutions.
Any congruence with a solution has infinitely many solutions in $\mathbb{Z}$. When a congruence problem says "has two solutions" they mean two solutions that are distinct modulo the number you are working. If you want to be a little more formal then you can say $x^2 = a$ has zero,one, or two solutions in $\mathbb{F}_p$.

9. Originally Posted by ThePerfectHacker
Any congruence with a solution has infinitely many solutions in $\mathbb{Z}$. When a congruence problem says "has two solutions" they mean two solutions that are distinct modulo the number you are working. If you want to be a little more formal then you can say $x^2 = a$ has zero,one, or two solutions in $\mathbb{F}_p$.
yeah sorry, it's worded real weird.

"solutions mod p" is grouped together, not just solutions. It took me a while to understand it (if I even do fully, time will tell.) But like PerfectHacker points out it's not asking for over $\mathbb{Z}$

10. Okay, so you want solutions in $\{1,\ldots,p-1\}\pmod p.$ Now I know.

Let’s analyse the problem this way. Either $x^2\equiv a\pmod p$ has no solutions or there is at least one solution in $\{1,\ldots,p-1\}.$ In the first case, we are done; there is nothing to prove. So we’ll suppose there is at least one solution.

Note that if $x_0\in\{1,\ldots,p-1\}$ is one solution, then $p-x_0\in\{1,\ldots,p-1\}$ is another solution. Moreover, as $p>2$, $x_0\ne p-x_0$, otherwise we would have $p=2x_0,$ which is impossible as $p$ is odd. Hence there are at least two solutions in $\{1,\ldots,p-1\}.$ if any solutions exist at all. This would also answer your last query, namely one of them has to be less than or equal to $\frac{p-1}2,$ as it is not possible for both $x_0$ and $p-x_0$ to be greater than $\frac{p-1}2.$

We still need to show that there are no more than 2 solutions. For this, we use a bit of field theory. Consider the polynomial $x^2-a$ in $\mathbb Z/p\mathbb Z[x].$ As $\mathbb Z/p\mathbb Z$ is a field, $\mathbb Z/p\mathbb Z[x].$ is a unique-factorization domain. In a UFD, any polynomial of degree $n$ cannot have more than $n$ roots. Hence the quadratic polynomial $x^2-a$ can have at most 2 roots modulo $p.$ Hence there are at most 2 solutions to the equation $x^2\equiv a\pmod p.$

Combining the results, we see that $x^2\equiv a\pmod p$ has exactly 2 solutions whenever it is solvable.

11. Originally Posted by JaneBennet
We still need to show that there are no more than 2 solutions. For this, we use a bit of field theory. Consider the polynomial $x^2-a$ in $\mathbb Z/p\mathbb Z[x].$ As $\mathbb Z/p\mathbb Z$ is a field, $\mathbb Z/p\mathbb Z[x].$ is a unique-factorization domain. In a UFD, any polynomial of degree $n$ cannot have more than $n$ roots. Hence the quadratic polynomial $x^2-a$ can have at most 2 roots modulo $p.$ Hence there are at most 2 solutions to the equation $x^2\equiv a\pmod p.$

Combining the results, we see that $x^2\equiv a\pmod p$ has exactly 2 solutions whenever it is solvable.
Not too informed in field theory, as it was only touched on one day of class. We never proved the fact of the polynomial n having at most n roots modulo p, YET