2
$\begingroup$

Suppose that $0\leq a,b,c,d\leq p-1$, where $p$ is a prime. Then how many solution are there to $ad\equiv bc \bmod p$?

We can work out the case $p=2$. Suppose that $p>2$.

My approach is this:

  1. Case I: One of $a$ or $b$ is $0$. WLOG assume $a=0$. Then $bc \equiv 0 \bmod p$ and hence $b$ or $c=0$. There are $2\times p \times 2 \times p=4p^2 $ ways to form $(a,b,c,d)$.
  2. Case II: None of $a \text{ or } b$ is $0$. Then $b,c\not = 0$(otherwise, $ad\equiv 0 \bmod p$ which would mean $a$ or $d$ is $0$.

I did not really get any further and just noticed that $ad \equiv ad \equiv da \equiv (p-d)(p-a) \bmod p$ which is fine but I can't say these are the only solutions.

I would appreciate a hint. Thanks.

$\endgroup$
  • 2
    $\begingroup$ My hint would be to count $2 \times 2$ matrices $\left( \begin{array}{clcr} a & b \\c & d \end{array} \right)$ with entries in the field of $p$ elements, and then count those of non-zero determinant, the last quantity being quite well-known. $\endgroup$ – Geoff Robinson Mar 1 '15 at 15:19
0
$\begingroup$

When at least one of them is zero:

There are $p^2-(p^2-2p+1)=2p-1$ ways to select $a$ and $d$ and $2p-1$ ways to select $b,c$. So there are $(2p-1)^2$ ways, as André points out.

When none are zero there are $(p-1)^3$ ways to select $a,b,c$ and after that we must solve a congrunce $ad\equiv bc$ which amounts to $d\equiv bca^{-1}$. So there is one solution once $a,b,c$ have been chosen.

Hence there are $(2p-1)^2+(p-1)^3$ solutions.

$\endgroup$
0
$\begingroup$

For the nobody equal to $0$ case, $a$, $b$, and $c$ can be chosen arbitrarily from the non-zero elements. For each choice, there is a unique $d$ that works, giving $(p-1)^3$ ways.

Remark: Note that there are $(2p-1)^2$ cases where the two products are congruent to $0$. The $2p$ that you used instead of $2p-1$ double-counts the pair $(a,d)=(0,0)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy