1
$\begingroup$

It is quite clear that if a≡c and b≡d (mod p), then ab≡cd (mod p), or if a≡d and b≡c (mod p). There are p cases of a≡c (mod p) as well as for b≡d (mod p), and so there are a total of p^2 cases of a≡c and b≡d (mod p). This is also the case for a≡d and b≡c (mod p), which gives together 2p^2-1 solutions, removing the case where a≡b≡c≡d (mod p), as it is repeated. There is also the case where (a or b) ≡ p (mod p) together with (c or d) ≡ p (mod p). However there do exist cases of ab≡cd (mod p) where neither a nor b is congruent to c nor d (mod p). An example of this is 23*56≡3*37≡4 (mod 107).

I do not know of any method to account for all of these cases. And so, how can I approach finding the number of solutions to ab≡cd (mod p) where p is a prime and 1≤a,b,c,d≤p?

Thank you very much.

$\endgroup$
9
  • 2
    $\begingroup$ Write your equation as a determinant, and argue from there. $\endgroup$
    – damiano
    Oct 20, 2010 at 14:00
  • 4
    $\begingroup$ Note that we can fix any a,b and non-zero c and get a unique d to make it work, which gives $p^2(p-1)$ solutions. For zero c, there are $2p^2$ (unique) solutions, assuming you're looking at ordered quadruples (a,b,c,d). These give all of them, so there are $p^2(p+1)$ solutions. $\endgroup$ Oct 20, 2010 at 14:02
  • 5
    $\begingroup$ This is very elementary and therefore not really suitable for this site. But here is an expansion on damiano's comment: consider the matrix with rows (a,b) and (c,d) with entries in $\mathbb{F}_p$. Then $ad = bc$ in $\mathbb{F}_p$ if and only if the determinant of the matrix is 0, which happens if and only if the second column is linearly dependent on the first. So you have to count the number of invertible 2 by 2 matrices / $\mathbb{F}_p$. There are $p^2-1$ ways of selecting the 1st column and after that you have to avoid the linear subspace it spans, so $p^2-p$ possibilities for the 2nd. $\endgroup$
    – Alex B.
    Oct 20, 2010 at 14:14
  • 3
    $\begingroup$ Actually, I don't know, why I decided to count the invertible matrices, rather than the singular ones: Your first column is either zero and then the second one can be anything ($p^2$ possibilities) or the first is non-zero ($p^2-1$ possibilities) and then the second must be in the linear span of the first ($p$ such second columns). So altogether you get $p^2 + p(p^2-1) = p^3+p^2-p$, which is the same as by counting invertible matrices. $\endgroup$
    – Alex B.
    Oct 20, 2010 at 14:26
  • 1
    $\begingroup$ Thomas, You have double counted several cases when $c=0$ (namely you have counted $a=b=0$ several times).. $\endgroup$
    – Alex B.
    Oct 20, 2010 at 14:27

0