A number theory problem by Kushal Bose

Since $3^1 \equiv 3$ , $3^2 \equiv 4$ , $3^3 \equiv 2$ , $3^4 \equiv 1$ modulo $5$ , we see that $5$ divides $3^x + 3^y$ provided that one of $x \equiv0\,,\,y \equiv 2$ or $x \equiv1\,,\,y \equiv 3$ or $x \equiv 2\,,\,y \equiv 0$ or $x \equiv 3\,,\,y \equiv 1$ modulo $5$ occurs. Thus there are $25$ possible choices of $y$ for each choice of $x$ , and hence there are $100\times25 = \boxed{2500}$ ordered pairs.

Note that

$3^n \equiv \begin{cases} 1, & n=4k \\ 3, & n=4k+1 \\ 9, & n=4k+2 \\ 7, & n=4k+3 \end{cases} \pmod{10}$

We observe that

$3^{4k+1} + 3^{4k+3} \equiv 0 \pmod{10} \implies 3^{4k+1} + 3^{4k+3} \equiv 0 \pmod{5}$

$3^{4k} + 3^{4k+2} \equiv 0 \pmod{10} \implies 3^{4k} + 3^{4k+2} \equiv 0 \pmod{5}$

Note: Another condition for $x \equiv 0 \pmod{5}$ would be $x \equiv 5 \pmod{10}$ . However, such a case wasn't observed above and so it was ruled out.

• For $x = 4k+1$ and $y = 4k+3$ we have $25$ choices for each selection in the given interval. Thus we have $\dbinom{25}{1} \cdot \dbinom{25}{1} = 625$ solutions.

• Similarly, for $x = 4k$ and $y = 4k+2$ we have $25$ choices for each selection in the given interval. Thus we have $\dbinom{25}{1} \cdot \dbinom{25}{1} = 625$ solutions.

Also note that if $(a,b)$ were to be one solution for $(x,y)$ , then $(b,a)$ is also a solution. Thus the total number of ordered pairs $(x,y)$ comes out to be $2 \times (625+625) = \boxed{2500}$ .