1. ## Another congruence problem

I missed a lecture where they discussed finding solutions to $\displaystyle 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 $\displaystyle p > 2 is prime$ and a member of Z, show that $\displaystyle 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, $\displaystyle x$ , satisfies $\displaystyle 0 <= x <= (p-1)/2$.

2. Originally Posted by Th3sandm4n
I missed a lecture where they discussed finding solutions to $\displaystyle 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 $\displaystyle x=1,2,...,12$ and see which ones work.

Now for the second part if $\displaystyle x^2 \equiv a(\bmod p)$ where $\displaystyle (a,p)=1$ has a solution $\displaystyle x_0$ then $\displaystyle a\equiv x_0^2(\bmod p)$ and so $\displaystyle (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 $\displaystyle x=1,2,...,12$ and see which ones work.

Now for the second part if $\displaystyle x^2 \equiv a(\bmod p)$ where $\displaystyle (a,p)=1$ has a solution $\displaystyle x_0$ then $\displaystyle a\equiv x_0^2(\bmod p)$ and so $\displaystyle (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?)$\displaystyle x_0^2$.
so then $\displaystyle x_0^2 \equiv a mod p$

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

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

And then im guessing that $\displaystyle 0 <= x_0 <= (p-1)/2$ holds because if it was greater than half of p, squaring it would mess it up?
And also $\displaystyle 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?)$\displaystyle x_0^2$.
so then $\displaystyle 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 $\displaystyle 0<= x <= (p-1)/2$ because the field of $\displaystyle 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 $\displaystyle x=1,2,...,12$ and see which ones work.
here is a quicker way

$\displaystyle 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 $\displaystyle p > 2$ is prime and a member of Z, show that $\displaystyle X^2 \equiv a mod p$ has either no solutions or exactly 2 solutions mod p.
That is actually false, as it stands. If $\displaystyle p\mid a$, then $\displaystyle x^2\equiv a\pmod p$ has infinitely many solutions.

8. Originally Posted by JaneBennet
That is actually false, as it stands. If $\displaystyle p\mid a$, then $\displaystyle x^2\equiv a\pmod p$ has infinitely many solutions.
Any congruence with a solution has infinitely many solutions in $\displaystyle \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 $\displaystyle x^2 = a$ has zero,one, or two solutions in $\displaystyle \mathbb{F}_p$.

9. Originally Posted by ThePerfectHacker
Any congruence with a solution has infinitely many solutions in $\displaystyle \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 $\displaystyle x^2 = a$ has zero,one, or two solutions in $\displaystyle \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 $\displaystyle \mathbb{Z}$

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

Let’s analyse the problem this way. Either $\displaystyle x^2\equiv a\pmod p$ has no solutions or there is at least one solution in $\displaystyle \{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 $\displaystyle x_0\in\{1,\ldots,p-1\}$ is one solution, then $\displaystyle p-x_0\in\{1,\ldots,p-1\}$ is another solution. Moreover, as $\displaystyle p>2$, $\displaystyle x_0\ne p-x_0$, otherwise we would have $\displaystyle p=2x_0,$ which is impossible as $\displaystyle p$ is odd. Hence there are at least two solutions in $\displaystyle \{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 $\displaystyle \frac{p-1}2,$ as it is not possible for both $\displaystyle x_0$ and $\displaystyle p-x_0$ to be greater than $\displaystyle \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 $\displaystyle x^2-a$ in $\displaystyle \mathbb Z/p\mathbb Z[x].$ As $\displaystyle \mathbb Z/p\mathbb Z$ is a field, $\displaystyle \mathbb Z/p\mathbb Z[x].$ is a unique-factorization domain. In a UFD, any polynomial of degree $\displaystyle n$ cannot have more than $\displaystyle n$ roots. Hence the quadratic polynomial $\displaystyle x^2-a$ can have at most 2 roots modulo $\displaystyle p.$ Hence there are at most 2 solutions to the equation $\displaystyle x^2\equiv a\pmod p.$

Combining the results, we see that $\displaystyle 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 $\displaystyle x^2-a$ in $\displaystyle \mathbb Z/p\mathbb Z[x].$ As $\displaystyle \mathbb Z/p\mathbb Z$ is a field, $\displaystyle \mathbb Z/p\mathbb Z[x].$ is a unique-factorization domain. In a UFD, any polynomial of degree $\displaystyle n$ cannot have more than $\displaystyle n$ roots. Hence the quadratic polynomial $\displaystyle x^2-a$ can have at most 2 roots modulo $\displaystyle p.$ Hence there are at most 2 solutions to the equation $\displaystyle x^2\equiv a\pmod p.$

Combining the results, we see that $\displaystyle 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