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

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

-
What are random integers? There is no uniform distribution on $\mathbb N$. –  Rasmus Jul 23 '11 at 13:57
By randomness, I mean $A, B, C$ are any three integers. –  user12290 Jul 23 '11 at 14:08
Please try to understand what Rasmus has said. There is no uniform distribution on the integers. That means the phrase "random integers" is a nonsense, unless you give it a precise meaning. You haven't done that. Think about it. Please. –  Gerry Myerson Jul 23 '11 at 14:11
12 questions, not a single accepted answer. If none of the answers satisfy you, why do you keep asking questions here? –  Alex B. Jul 24 '11 at 5:15
@user12290: Yes, there's a checkbox next to an answer that essentially says 'this is the answer I accept'; you can check one answer per question. None of the answers on this question, for instance, have actually been marked as accepted; simply thanking the user in comments isn't enough. (As for why to accept an answer, there are any number of reasons, not least to aid new readers) –  Steven Stadnicki Jul 26 '11 at 22:41

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$.

-
+1 for the good write up and for finding a reasonable interpretation of the question. –  Willie Wong Jul 23 '11 at 14:25
Thank you very much for your help. I can understand the approach. Thank you again. –  user12290 Jul 23 '11 at 14:27

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$.

-
Thank you very much. –  user12290 Jul 23 '11 at 14:40

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.

-
Thank you very much. –  user12290 Jul 23 '11 at 14:40