Another congruence problem

**Th3sandm4n** · March 29th 2009, 06:20 PM

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$ .

**ThePerfectHacker** · March 29th 2009, 07:45 PM

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

**Th3sandm4n** · March 29th 2009, 08:29 PM

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$
which leads to:
$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$ .

**ThePerfectHacker** · March 29th 2009, 08:56 PM

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.

**Th3sandm4n** · March 29th 2009, 09:11 PM

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.

**siegfried** · April 3rd 2009, 01:16 AM

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)

**JaneBennet** · April 3rd 2009, 06:05 AM

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.

**ThePerfectHacker** · April 3rd 2009, 10:43 AM

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$ .

**Th3sandm4n** · April 3rd 2009, 10:58 AM

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}$

**JaneBennet** · April 3rd 2009, 03:04 PM

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.

**Th3sandm4n** · April 3rd 2009, 05:14 PM

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

Thread: Another congruence problem

LinkBack

Thread Tools

Display

Another congruence problem

Similar Math Help Forum Discussions

[SOLVED] Congruence Problem

[SOLVED] Congruence Problem

Congruence problem with gcd

Congruence problem

Congruence problem with LCM

Search Tags