A Primality Criterion

For which integers m do there exist integers a,b,c,d, all distinct
modulo m, such that ab-cd, ac-bd, and ad-bc are all divisible by m?
In other words, we require ab=cd, ac=bd, and ad=bc modulo m.  We 
can immediately rule out m less than 5, and also the number 9, by 
inspection.  Also, m cannot be a prime, because if m were prime we 
would have unique division modulo m, and hence we could compute 
a=cd/b and a=bd/c, which could be multiplied together to give 
a^2 = d^2 (mod m).  Making similar use of the other relation pairs,
we would have a^2 = b^2 = c^2 = d^2 (mod m), which is impossible in
distinct residues, because any given residue has only two square 
roots modulo a prime.

We can also rule out values of m of the form 2p for any odd prime p,
because if any of a,b,c,d is divisible by p then they all must be, 
but there are only two distinct residues (0 and p) mod 2p that are 
divisible by p, so this is impossible.  Likewise if any of a,b,c,d
is divisible by 2 then all must be, in which case all three of the
equations can be divided by 4, giving distinct values a'=a/2,b'=b/2,
c'=c/2,d'=d/2 that satisfy the three conditions modulo p, which we've
already seen is impossible.

On the other hand, if m is of the form p^2 for any prime greater than
3, then the values p,2p,3p,4p satisfy the stated conditions.  More
generally, rp,sp,up,vp satisfy the conditions for any set of four
distinct integers r,s,u,v less than p.

If m is of the form pq for two distinct odd primes p and q with p
greater than q, we always have a solution of the form a=u,b=v,c=-v,
d=-u, as shown by the fact that ab-cd and ac-bd are identically zero
and ad-bc is satisfied if u^2 = v^2.  Thus it is sufficient to find
distinct u,v such that u is not congruent to -v (mod pq).  One such
pair is given by u=p+q, v=p-q.  More generally, for any given u we
can solve u=px+qy for the minimal solution x,y where x is less than
q and y is less than p, and then take v=px-qy.  Clearly u^2 = v^2 
(mod pq) and also u+v=2px and u-v=2qy so neither of these is congruent
to zero (mod pq).

Lastly we note that if a,b,c,d is a solution for the integer m, then
for any integer k the number km has the solution ka,kb,kc,kd.  Hence
the only natural numbers (in addition to the numbers 1, 4, and 9) for
which there does NOT exist a solution are numbers of the form p and 
2p for any prime p.