Find $a,b,c,d$ such that $p \not\mid ad - bd$ and each element is in $\mathbb{Z}/p\mathbb{Z}$

Question

Find the number of quadruples $(a,b,c,d)$ such that $ad - bc \not\equiv 0 \pmod p$ where $a,b,c,d \in \{\mathbb{\overline{0},\overline{1},\cdots, \overline{p-1}} \}$.

From this, we have $\displaystyle\prod_{r=0}^{1}(p^2 - p^r)$ as the result. Can I get a more elementary (number-theoretic) approach rather that one that uses matrix properties?

This looks like an application of the inclusion exclusion principle.

Answer 1

I would, in this case, rather look for the number of solutions to $ad - bc = 0$, and then subtract that from $p^4$. It seems simpler. And we can indeed go by inclusion-exclusion, split into cases depending on how many of the variables are $0$. Let $A, B, C, D$ be the set of solutions where $a = 0$, $b = 0$, $c = 0$ and $d = 0$ respectively. We count:

• The complement of $A\cup B\cup C \cup D$ in the set of solutions: Then there are $(p-1)^3$ solutions, because no matter what non-zero values $a, b, c$ have, we can and must pick $d$ to be $\frac{bc}{a}$ (where the division is modular)
• Size of $A$: $d$ can be whatever it wants, and at least one of $b$ and $c$ must be $0$: $p(2p-1)$ solutions
• Sizes of $B$, $C$, $D$ are the same as above
• Size of $A\cap D$: At least one of $b$ and $c$ must be $0$, there are $2p-1$ solutions
• Size of $B\cap C$ is the same as above
• Size of $A\cap B$: $d$ and $c$ can be whatever they want: $p^2$ solutions
• Sizes of $A\cap C$, $D\cap B$ and $D\cap C$ are the same as above
• Size of $A\cap D\cap B$: $c$ can be whatever it wants, $p$ solutions
• Sizes of $A\cap D\cap C$, $A\cap B\cap C$, $D\cap B\cap C$ are the same as above
• Size of $A\cap B\cap C\cap D$: One solution

So, using the inclusion-exclusion principle to find the size of $A\cup B\cup C \cup D$, we get that the number of solutions is $$ (p-1)^3 + 4p(2p-1) - \big(2(2p-1) + 4p^2\big) + 4p - 1 = p^3 + p^2 - p $$ Subtracting this from $p^4$, we get the number of non-solutions to $ad-bc = 0$, which is indeed equal to $$ p^4 - p^3 - p^2 + p = (p^2-1)(p^2-p) $$