Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm interested because I want to show that $x^2-34y^2\equiv -1\pmod{m}$ has solutions for all integers $m$. I started by using the following reasoning:

If $3\nmid m$, then $gcd(m,3)=1$. Then there exists a multiplicative inverse $\bar{3}$ modulo $m$. I note that $5^2-34=-(3^2)$, and thus $\bar{3}^2(5^2-34)\equiv (\bar{3}\cdot 5)^2-34(\bar{3}^2)\equiv -(\bar{3})^2(3^2) \equiv -1\pmod{4}$. And thus $(\bar{3}\cdot 5, \bar{3})$ is a solution modulo $m$.

Similarly, if $5\nmid m$, then $(m,5)=1$. Then since $3^2-34=-(5^2)$, then I also have $\bar{5}^2(3^2-34)\equiv (\bar{5}\cdot 3)^2-34(\bar{5}^2)\equiv -(\bar{5})^2(5^2)\equiv -1\pmod{m}$.

So for any $m$ not divisible by $3$ or $5$, there exists a solution. Then for $m$ such that $3|m$ and $5|m$, then $m$ has prime factorization $m=3^a5^b{p_1}^{q_1}\cdots {p_r}^{q_r}$. This would give the system of congruences

$x^2-34y^2 \equiv -1 \pmod{3^a}, x^2-34y^2 \equiv -1 \pmod{5^b}, x^2-34y^2 \equiv -1 \pmod{{p_i}^{q_i}}$

Then $5\nmid 3^a$, $3\nmid 5^b$, and $3\nmid {p_i}^{q_i}$ and $5\nmid {p_i}^{q_i}$, so each of the congruences has a solution. Does the Chinese Remainder Theorem then imply that there is a solution modulo $m$? I know that it holds for polynomials in one variable $x$, and that the number of solutions is the product of the number of solutions for each prime power modulus. Would the same result hold now that there are two variables in the polynomial? I haven't found any proofs to support or contradict the result. Thanks!

share|cite|improve this question
@xdfm: I don't think your first paragraph says what you mean to say; it is not true that the congruence holds for all $m$ (that would require the polynomial to be constant modulo $m$). I think you mean that the congruence has solutions for all integers $m$. Is that correct? – Arturo Magidin Nov 22 '10 at 5:48
@Arturo, yes, you are right. Thanks for pointing that out. I will edit it. – yunone Nov 22 '10 at 5:55
up vote 5 down vote accepted

The Chinese Remainder Theorem says that if the modulii $m_1,\ldots,m_k$ are pairwise relatively prime, and $a_1,\ldots,a_k$ are arbitrary, then there is a solution $x$ to the congruence system \begin{align*} x &\equiv a_1 &\pmod{m_1}\\ x &\equiv a_2 &\pmod{m_2}\\ &\vdots\\ x &\equiv a_k &\pmod{m_k} \end{align*} and the solution is unique modulo $m_1\cdots m_k$.

So, for each $i$ you find a value $r_i$ and a value $s_i$ such that $r_i^2 - 34s_i^2 \equiv -1 \pmod{p_i^{q_i}}$, and values $r$ and $s$ for the congruence modulo $3^a$, and values $r'$ and $s'$ for the congruence modulo $5^b$. Apply the Chinese Remainder Theorem to the $r_i$, $r$, and $r'$ (with appropriate modulii) to get a single value of $x$ that is congruent to what you want for each congruence. Do the same with the $s_i$, $s$, and $s'$ to get a value for $y$. The single value of $x$ and $y$ is the solution you want.

Notice that you are not applying the Chinese Remainder Theorem to a 2-variable polynomial (or to a one-variable polynomial other than $p(x)=x$, for that matter): rather, you are finding the values you want for each variable for each prime power, and then you are using the Chinese Remainder Theorem to find a single value that will have the appropriate remainders for each of the variables separately.

share|cite|improve this answer
Ah, ok. Perhaps I should reread the proof for the single variable polynomial case as well. Thanks, much appreciated! – yunone Nov 22 '10 at 6:04
@xdfm: I suspect that you will find that you are finding a value of $x$ modulo $m_i$ for a number of modulii, and then lifting it to a solution modulo $m_1\cdots m_k$ using the CRT, rather than applying the CRT to the polynomial itself. It's the same thing you do here. Basically, if you can find solutions to an equation/system of equations modulo pairwise coprime moduli, then you can find solutions modulo their product by using CRT for each unknown to find a single value modulo the product that has the value of the solution modulo each of the moduli. – Arturo Magidin Nov 22 '10 at 6:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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