Note that 159=3*53. The answer to this question is yes. I managed to find two of the solutions. They are $x=23,136$ but there are two more. The main question that I have is whether there is an easier way to find all solutions of a quadratic congruence when the modulus is not prime. Is it always the case that there will be four solutions when the modulus is composite? By solutions I mean the least residues. Thank you!
Does $x^2 \equiv 211\pmod{ 159}$ have a solution?
-
0We are only interested in the least residues. :) And I noticed that 314 doesn't satisfy. I didn't check the ones after that. – 2012-08-13
-
0Alright. Yes, there is infinitely many solutions. We are only interested in the $x$'s such that $0 \leq x < 159$. I know all the solutions, but I was asking if there is a nice way to find them when the mod is not prime. – 2012-08-13
-
0Deleted my comments as matlab revealed to me that: 23 76 83 136 are the solutions. Sorry about my previous posts. Only thing I can do is to find them. – 2012-08-13
-
1Given that $211>159$, my first reaction would be to subtract $159$ to arrive at $x^2\equiv 52\ (\mathrm{mod}\, 159)$. Which obviously makes determining the equivalence $\mod 53$ from the answers much easier. – 2012-08-13
3 Answers
If you know how to find the solutions when the modulus is prime, then, when the modulus is composite, solve the congruence modulo the primes, and use the Chinese Remainder Theorem to put them together to get solutions modulo the composites.
The number of solutions is (give or take a few exceptional circumstances) $2^r$, where $r$ is the number of distinct primes dividing the modulus. In your case, there are 2 solutions modulo 3, and 2 solutions modulo 53, yielding 4 solutions modulo 159.
-
5If the modulus isn't squarefree we also need Hensel's. – 2012-08-13
-
0@GerryMyerson I can't see how that would work. Would you mind demostrating. If it is not too much bother. Thank you! – 2012-08-13
-
2The solutions mod 3 are 1 and 2. The solutions mod 53 are 23 and 30. Are you familiar with the Chinese Remainder Theorem? It will find you a number congruent to 2 mod 3 and to 23 mod 53 (namely, 23), and a number congruent to 1 mod 3 and to 30 mod 53 (namely, 136), and it will also find you a number congruent to 1 mod 3 and to 23 mod 53 (namely, 76), and a number congruent to 2 mod 3 and to 30 mod 53 (namely, 83), and there are your 4 solutions. Is that the part you need to see? – 2012-08-13
-
0@GerryMyerson I am familiar with the Chinese remainder theorem, mainly the concept behind it. I have not put it to practice too much though. I managed to get the 2 solutions modulo 3 and 2 solutions modulo 53. I Just did not know how to use them to get my solutions for modulo 159. But now I see what I must do. Thank you so much. – 2012-08-14
Note that $159=3\cdot 53$. If the congruences $x^2\equiv 211\pmod{3}$ and $x^2\equiv 211\pmod{53}$ have solutions $x\equiv a \pmod{3}$ and $x\equiv b\pmod{53}$, then by the Chinese Remainder Theorem we can find an $x$ such that $x\equiv a \pmod{3}$ and $x\equiv b \pmod{53}$. Such an $x$ will have the property that $x^2\equiv 211\pmod{159}$.
To show that $x^2\equiv 1 \pmod{3}$ has a solution is trivial.
So we look at $x^2\equiv 211\pmod{53}$. We can find an explicit solution. But it is easier to note that $211\equiv -1\pmod{53}$. And $x^2\equiv -1 \pmod{53}$ has a solution, since $53$ is a prime of the form $4k+1$.
Till now we have found,
(i) we need to find x such that $x^2≡211(mod\ 3)$ and $x^2≡211(mod\ 53)$
(ii)$x^2≡211(mod\ 3)≡1(mod\ 3)=>x≡±1(mod\ 3)$=3y±1 , for some integer y.
(iii)$x^2≡211(mod\ 53)≡-1(mod\ 53)$ which is clearly solvable(applying Euler's criterion)
Now I am going to find the solution of (iii).
As $53=7^2+2^2$, so $53(c^2+d^2)=(7^2+2^2)(c^2+d^2)=(7c±2d)^2+(7d∓2c)^2$ for some integers c,d.
Comparing with $x^2+1$, the possible values of (x,1) are (±(7c-2d), ±(7d+2c)) or (±(7d+2c), ±(7c-2d))
If we take $7c-2d=1$ and $7d+2c=x$, then $7c-2d=1=7-3.2=>7(c-1)=2(d-3)=>7|(d-3)$ and $2|(c-1)$
i.e., $\frac{d-3}{7}=\frac{c-1}{2}=b$, where b is an integer.
$=>d=7b+3$ and $c=2b+1=>x=7d+2c=7(7b+3)+2(2b+1)=53b+23$
=>23 is a solution of $x^2≡-1(mod\ 53)$
Now, if A is a solution of $x^2≡t(mod\ m)=>A^2≡t(mod\ m)=>(-A)^2≡t(mod\ m)$ so, -A will be another solution --->(1).
So, -23 is a solution of $x^2≡-1(mod\ 53)$
=>x=53z±23, for some integer z.
Other combinations of values of (x,1) will reach at the same point.
Now we need to solve $53z±23=3y±1$
Taking both signs as positive, $53z+23=3y+1$
$=>3y-53z=22=22(53.2-3.35)$ as 53.2-3.35=1
$=>3(y+22.35)=53(z+2.22)$
$=>3|(z+44)=>3|(z-1)=>z=3w+1$ for some integer w.
$=>x=53z+23=53(3w+1)+23=159w+76≡76(mod\ 159)$
So, -76 will also be another solution (using (1)).
Now taking, $53z-23=3y+1$
$=>53z=3(y+8)=>3|z=>z=3u$ for some integer u.
$=>x=53z-23=53(3u)-23≡-23(mod\ 159)$
So, 23 will also be another solution (using (1)).
So, the 4 solutions are ±23, ±76.
Some generalization : As we know, any prime(p) of the form 4m+1 can always be expressed as $a^2+b^2$.
We observe, $(a,b) > a^2+b^2$ and $ (a,b) |(a^2+b^2) $
If $(a,b)>1,\ a^2+b^2$ can not be prime, but as $p(=a^2+b^2)$ is prime, (a,b) must be 1.
So, we can always find p,q in integers, such that $p\cdot a+q\cdot b=1$.
x can be calculated as $p\cdot b-q\cdot a$ as a,b are given.