Probability of the event of product of three integers to be divisible by 4

Question

Let $A,B, C $ be three random integers. What is the probability $ABC \equiv 0 \bmod(4)$?

Answer 1

There is no probability distribution that gives "equal weight" to all integers. So the problem is technically wrong!

However, we are probably being invited to assume that the remainder when any of $A$, $B$, and $C$ is divided by $4$ is equally likely to be $0$, $1$, $2$, or $3$. This implies that any of these probabilities is equal to $1/4$.

Without explicitly saying so, the problem expects us to assume that the remainders of $A$, $B$, and $C$ are independent.

We imagine $A$, $B$, and $C$ to be picked one after the other.

It is a little easier to find the probability that the event we are interested in does not happen.

We have $ABC$ is not divisible by $4$ if (i) $A$, $B$, and $C$ are all odd or (ii) Two of $A$, $B$, $C$ are odd and the remaining one has remainder $2$ on division by $4$.

Case (i): The probability that any particular number is odd is $1/2$, so the probability they are all odd is $(1/2)^3$.

Case (ii): Let's find the probability that $A$ has remainder $2$, and $B$ and $C$ are odd. Easily, this is $(1/4)(1/2)^2$. We get the same probability for $B$ having remainder $2$ and the rest odd, and for $C$ having remainder $2$ with the rest odd. This gives a total of $3/16$.

Add up. The probability the product is not divisible by $4$ is $5/16$.

Thus the probability that the product is divisible by $4$ is $11/16$.

Answer 2

Random integers with what distribution? The natural default assumption would be "uniform", but there is no uniform distribution over the integers.

However, let's assume that the distribution is flat enough that the remainders of $A$, $B$ and $C \pmod 4$ are uniformly distributed over $\mathbb Z / 4 \mathbb Z$. Then $ABC \equiv 0 \pmod 4$ iff either

• any one of $A$, $B$ and $C$ equals $0 \pmod 4$, or
• at least two of $A$, $B$ and $C$ equal $2 \pmod 4$.

Conversely, $ABC \not\equiv 0 \pmod 4$ iff either

• all of $A$, $B$ and $C$ are odd, or
• two of $A$, $B$ and $C$ are odd and the third equals $2 \pmod 4$.

These possibilities are mutually exclusive; the first occurs with probability $(2/4)^3 = 1/8$, while the second occurs with probability $3 \cdot (1/4) \cdot (2/4)^2 = 3/16$. Thus, $P(ABC \not\equiv 0 \mod 4) = 1/8 + 3/16 = 5/16$, and so $P(ABC \equiv 0 \mod 4) = 1-P(ABC \not\equiv 0 \mod 4) = 11/16$.

Answer 3

This is the "brute force" approach, without trying any clever idea, just enumerating possibilities.

I think you will get these possibilities for the remainders modulo 4:

0BC ... 16=4·4 possibilities
A0C ... 12=3·4 possibilities (I do not want to double count anything, so I avoid things that have already been counted. That's why I can choose only A=1,2,3)
AB0 ... 9=3·3 possibilites
22C ... 3 possibilities
2B2 ... 2 possibilities (I have to omit B=0 and B=2, which have already been counted.)
A22 ... 2 possibilities

So I get $\frac{44}{4^3}=\frac{11}{16}$, if I did not miss something.