# Solving congruences in two variables

Is there a specific way to attack congruences with two variables? The reason I ask is because up until now, I had never encountered such a problem. While browsing tonight, I came across this challenge problem in one of my books:

Suppose that $(ab,p)=1$ and that $p>2$. Show that the number of solutions $(x,y)$ of the congruence $ax^2+by^2\equiv 1\pmod{p}$ is $p-\left(\frac{-ab}{p}\right)$.

After experimenting with it for a few hours, I've barely gotten anywhere. So far, I've only managed to break it into some cases. $(ab,p)=1$ implies $(a,p)=(b,p)=1$ and $\left(\frac{-ab}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$, so if $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)=1$ or $-1$, then $\left(\frac{ab}{p}\right)=1$, so I want to show there are $p-(-1)^{(p-1)/2}$ solutions.

Similarly, if $\left(\frac{a}{p}\right)=1$ and $\left(\frac{b}{p}\right)=-1$, I need to show there are $p+(-1)^{(p-1)/2}$ solutions.

In the first case, $a$ and $b$ would both be quadratic residues modulo $p$, and hence $c^2\equiv a\pmod{p}$ and $d^2\equiv b\pmod{p}$ for some $c,d$. Then the original problem would come to $(cx)^2+(dy)^2\equiv 1\pmod{p}$, but I'm not sure a sum of squares is any better. Is there a slick solution to a problem like this?, I'm very puzzled over it.

-

The answer to your first question is somewhat long. Counting solutions to congruences in two variables is equivalent to counting points on (affine) curves over finite fields, which happens to be quite hard in general and is an active field of study. Even studying cubic polynomials rapidly leads one to deep waters: elliptic curves, modular forms, ...

The quadratic case is much simpler. When working in projective coordinates the underlying curve has genus $0$, hence either has no points or is isomorphic to $\mathbb{P}^1$ (and has $p+1$ points). So to count points on an affine curve it suffices to determine if any solutions exist and, if so, to find an explicit map from $\mathbb{P}^1$ and see what points it misses.

Of course this might just be gibberish to you, so let me illustrate with the example case $a = b = 1$. It's clear that $x^2 + y^2 = 1$ has nontrivial solutions such as $(1, 0)$. The existence of these nontrivial solutions allows one to deduce the parameterization

$$x = \frac{1 - t^2}{1 + t^2}, y = \frac{2t}{1 + t^2}$$

which is valid for any $t$ such that $t^2 \not \equiv -1 \bmod p$. (The argument is roughly as follows: if $(x, y)$ is any other rational solution, then the line from $(x, y)$ to $(1, 0)$ has rational slope, and conversely given any such line it intersects the curve in at most one other point.) This parameterization misses the solution $(1, 0)$ which corresponds to sending $t$ to $\infty$, so in total there are $p+1$ solutions if $p \equiv 3 \bmod 4$ (so $t$ can be anything) and $p-1$ solutions if $p \equiv 1 \bmod 4$) (so $t$ cannot be the two nontrivial square roots of $-1$.)

For general $a, b$ you get cases depending on whether $a$ and $b$ are quadratic residues.

-
thanks for the answer, although I'm still a little confused after reading it a few times through. First, is there an elementary fact that would let me know that there are $p+1$ points/solutions from which to add or subtract from? I take it you added the solution $(1,0)$ to $p$ to get $p+1$ solutions when $p\equiv 3\pmod{4}$? I know from an earlier section I read that $x^2\equiv -1\pmod{p}$ only has solutions when $p\equiv 1\pmod{4}$, and so you subtracted 2 solutions from $p+1$, so that we wouldn't divide by zero? How do you know to begin with $p$ solutions as a starting point? – yunone Oct 24 '10 at 14:02
Also, I'm still unclear as to how to apply this to the cases where $a,b$ are quadratic residues or not. As I posted originally, if $a,b$ are residues, I get the equation $(cx)^2+(dy)^2\equiv 1\pmod{p}$. Would this lead to a parameterization $cx=(1-t^2)/(1+t^2),dy=2t/(1+t^2)$? If that is the case, then solutions don't change from the case where $a=b=1$, so the result holds? And in the case where $x$ or $y$ is not a quadratic residue, is it possible to have a nice parameterization if the LHS is no longer a sum of squares? I apologize for the flood of questions, I don't follow so quickly. – yunone Oct 24 '10 at 14:10
@xdfm: I apologize; the above explanation is a bit shoddy. The "elementary fact" follows from the fact the above parameterization is always possible for quadratics in two variables, and I explain this a little better here: artofproblemsolving.com/Forum/blog.php?u=14052&b=10559 . – Qiaochu Yuan Oct 24 '10 at 14:30
@xdfm: I should also mention that there always exists at least one solution. This is a nice exercise and you should think about it. – Qiaochu Yuan Oct 24 '10 at 14:30

What you have is a quadratic form, which makes the problem significantly easier than the general case, and can be split into the following steps.

1. Find at least one solution.
2. Given one solution, use this to parameterize all solutions.

This is roughly what Qiaochu did in his answer and this method is quite general, applying to quadratic forms in any number of variables and for finding solutions mod p, in the rationals or, in fact, in any field. I also used this method recently in answer to a question about Pythagorean triples.

Let me start with (2) first, so we suppose that you already have one solution (x0,y0). The idea is to find other solutions of the form (x,y) = (x0,y0) + (u,v)t. Where you choose nonzero (u,v) ∈ (ℤ/(p))2 and then solve for t. This will give a quadratic in t (as long as the t2 term doesn't cancel) with t = 0 as one solution. Extracting out a factor of t gives a linear form with a unique solution.

$$ax^2+by^2-1=(au^2+bv^2)t^2+2(ux_0+vy_0)t=0\ \Rightarrow\ t=-2\frac{ux_0+vy_0}{au^2+bv^2}\ (*)$$

This works as long as au2+bv2 ≠ 0, and gives us a parameterization of the solutions to the quadratic form in terms of nonzero (u,v) ∈ (ℤ/(p))2. The solution we get does not change if (u,v) are rescaled (the projective space ℙ1 mentioned by Qiaochu is precisely the set of nonzero (u,v) up to rescaling). Rescaling by 1/u, we only look at solutions corresponding to (u,v) = (1,v) and (in case u = 0), (u,v) = (0,1). That is p + 1 possibilities. The parameterization in terms of (1,v) only fails when a +bv2 = 0 so that (bv)2 = -ab. This can only happen if -ab is a quadratic residue, and occurs for bv one of the 2 square roots of -ab. This gives a total number of solutions to the quadratic form as p + 1 if -ab is not a quadratic residue and (p + 1) - 2 if it is.

Looking at step (1) now. You could try finding a solution by looking at cases depending on whether a,b, ab are quadratic residues, etc. However, there is a quick counting method. For any right hand side c, ax2 + by2 = c can have at most p + 1 solutions in x,y (mod p) -- using the above argument. As there are p2 possibilities for (x,y), this gives at least p2/(p + 1) values of c which occur. As p2/(p + 1) > p − 1, this shows that you can solve ax2 + by2 = c (mod p) for any value of c.

You should be able to see that this whole argument carries through almost word-for-word to any finite field of characteristic ≠ 2 (characteristic 2 is a bit different because (*) gives t = 0).

-