# Probability/Number Theory Problem

Positive integers a, b, and c are randomly and independently selected with replacement from the set $\{1, 2, 3, \dots, 2010\}$. What is the probability that $abc + ab + a$ is divisible by 3?

This is how I tried to approach it:

$abc + ab + a$ can be factored as $a(bc + b + 1)$

Thus, for $abc + ab + a$ to be divisible by $3$, all that needs to be true is $a$ is divisible by 3.

There are $2010/3 = 670$ numbers from $1 ... 2010$ thare are divisible by $3$. These are the possible choices for $a$

$b$ and $c$ can be anything and there are $2010$ choices for each.

Thus the probability is $\frac{670\cdot 2010\cdot 2010}{2010\cdot 2010\cdot 2010}$ which simplifies to $\frac{1}{3}$.

However, apparently my solution is incorrect. Where did I go wrong?

EDIT: I forgot about the case where $bc + b + 1$ could be divisible by 3. How do you solve it then?

• What if $a$ isn't divisible by $3$, but $bc+b+1$ is? – Daniel Fischer Dec 11 '13 at 3:15
• Oh - how do you solve it then? – 1110101001 Dec 11 '13 at 3:47
• Count how many ways $bc+b+1$ can be a multiple of $3$. $b$ cannot be a multiple of $3$ then. If $b \equiv 1 \pmod{3}$, then $c$ must be ... . If $b \equiv 2 \pmod{3}$, then $c$ must be ... . – Daniel Fischer Dec 11 '13 at 3:51
• ... And don't double count. – Dale M Dec 11 '13 at 7:07

## 1 Answer

First of all, whether any polynomial expression in $a,b,c$ is divisible by $3$ or not depends only upon the residue classes of $a,b,c$ modulo $3$. Because $2010$ is a multiple of $3$, each of $a,b,c$ has exactly a $\frac13$ probability of being congruent to $0,1,2\pmod 3$. So you'll get the same answer by just restricting each of $a,b,c$ to the values $0,1,2$, independently and each with probability $\frac13$.

At this point you could just do it by brute force. But: $abc+ab+a$ is not divisible by $3$ if and only if both $a$ is not divisible by $3$ and $bc+b+1$ is not divisible by $3$. The events are independent, and the first event has probability $\frac23$. For the second event, either brute force or: $b=0$ works no matter what $c$ is, while each of $b=1$ amd $b=2$ works for two values of $c$. So the second event has probability $\frac79$, yielding the final probability of $\frac23 \frac79$. In other words, $abc+ab+a$ is divisible by $3$ with probability $1-\frac23\frac79 = \frac{13}{27}$.

• Nice way of doing it without brute force! – 1110101001 Dec 11 '13 at 5:11