# Probability that $2^a+3^b+5^c$ is divisible by 4

If $a,b,c\in{1,2,3,4,5}$, find the probability that $2^a+3^b+5^c$ is divisible by 4.

For a number to be divisible by $4$, the last two digits have to be divisible by $4$

$5^c= \_~\_25$ if $c>1$

$3^1=3,~3^2=9,~3^3=27,~3^4=81,~ 3^5=243$

$2^1=2,~2^2=4,~2^3=8,~2^4=16,~2^5=32$

Should I add all possibilities? Is there a simpler method?

• nice problem.........+1. do you have such more problems? – Bhaskara-III Jan 13 '16 at 13:00
• That depends on the distribution of $a$, $b$ and $c$. There's distributions that make the probability anything (between $0$ and $1$ inclusively). – skyking Jan 13 '16 at 13:17

Let's consider the remainders when dividing by $4$. If $a=1$ then $2^a=2$ has the remainder $2$. Otherwise, $2^a$ has the remainder zero. If $b$ is odd then $3^b$ has remainder $3$, but if $b$ is even $3^b$ has remainder $1$. Whatever $c$ is, $5^c$ will have remainder $1$. (All of these statements are provable by induction, but the patterns are obvious.)

Then there are just two basic ways for the sum to have remainder zero when divided by $4$:

Case 1: $a=1$, $b$ is even, $c$ is anything. This gives remainders $2+1+1$ or zero.

Case2: $a>1$, $b$ is odd, $c$ is anything. This gives remainders $0+3+1$ or zero.

Now count each case and add the counts.

• for case 1, I got $\frac{2^a+3^b+5^c}{4}=k+\frac{1}{2}+\frac{1}{4}+\frac{1}{5}$ which is not an integer. – Aditya Dev Jan 13 '16 at 13:46
• @AdityaDev: I do not understand. Since you say case 1, $a=1$, but which values of $b$ and $c$ are you using here? And since you are dividing by $4$, it is not possible to get a value of $\frac 15$. If you mean $a=1,b=2,c=1$, then you get $2^1+3^2+5^1=16$ which is divisible by $4$. In the example in your comment, I think the last value should be $\frac 14$, and adding up those fractions you get $k+1$, which is a integer. – Rory Daulton Jan 13 '16 at 20:50
• yes. The last value should have been 1/4. – Aditya Dev Jan 13 '16 at 23:51

Observe that $$2^a+3^b+5^c \equiv 2^a+(-1)^b+1 \pmod{4}$$

So for this to be $0 \pmod 4$, we have the following scenarios

1. $a \geq 2$, $b$ is odd and $c$ is any number.
2. $a=1$, $b$ is even and $c$ is any number.

The number of three tuples $(a,b,c)$ that satisfy the first case =$(4)(3)(5)=60$ and the number of three tuples $(a,b,c)$ that satisfy the second case =$(1)(2)(5)=10.$

Probability is $\frac{70}{125}$.

• I don't understand the first step. (I know about congruence modulo theorem) – Aditya Dev Jan 13 '16 at 13:48
• @AdityaDev using basic properties of congruences we can say since $3 \equiv -1 \pmod{4}$, therefore $3^b \equiv (-1)^b \pmod{4}$. Likewise $5 \equiv 1 \pmod{4}$, therefore $5^c \equiv (1)^c \equiv 1 \pmod{4}$. Then add up all the congruences. – Anurag A Jan 13 '16 at 19:41

$2^{\color\red{a}}+3^\color\green{b}+5^\color\magenta{c}\equiv0\pmod4\iff$

• $\Big(\big(\color\red{a}=1\big)\wedge\big((\color\green{b}=2)\vee(\color\green{b}=4)\big)\Big)\vee$
• $\Big(\big(\color\red{a}\neq1\big)\wedge\big((\color\green{b}\neq2)\wedge(\color\green{b}\neq4)\big)\Big)$

Therefore, the probability is $\dfrac{\color\red1\cdot\color\green2\cdot\color\magenta5+(5-\color\red1)\cdot(5-\color\green2)\cdot\color\magenta5}{5\cdot5\cdot5}=\dfrac{14}{25}$