2021 JMC 10 Problems/Problem 25

Problem

How many ordered pairs of positive integers $(a,b)$ with $a \le 100$ and $b \le 10$ exist such that neither the numerator nor denominator of the below fraction, when completely simplified (i.e. numerator and denominator are relatively prime), are divisible by five? $\frac{4^b +121^b}{2^a -3^b}$

$\textbf{(A) } 10 \qquad \textbf{(B) } 12 \qquad \textbf{(C) } 375 \qquad \textbf{(D) } 380 \qquad \textbf{(E) } 382$

Solution

The problem asks for when $2^{2b} +11^{2b}$ and $2^a -3^b$ have the same number of powers of 5.

First, when $b$ is even, the numerator $4^b +121^b$ is not divisible by $5$ , so the denominator must also not be divisible by $5$ . So $2^a \not \equiv (2^3)^b \pmod 5$ if and only if $a \not \equiv 3b \pmod 4$ . This gives $75 \cdot 5 = 375$ solutions.

When $b$ is odd, $4^b +121^b$ has at least 3 powers of $5$ due to the sum of $b$ -th powers factorization for odd $b$ . In order for $2^a \equiv 3^b \pmod {125}$ , we must have $2^a \equiv (2^7)^b \pmod {125}$ . Note that $\text{ord}_2{(125)}=100$ (taking $2^{10}$ and/or $2^{20}$ modulo 125 will work). Therefore, $7b \equiv a \pmod {100}$ . It is clear that $7b=a$ must be satisfied. To verify that all $(a,b)$ with $a=7b$ work, we check with Lift-the-Exponent Lemma; $v_5 (121^b + 4^b) = v_5 (125) + v_5 (b) = v_5 (128^b - 3^b)$ where $v_5 (x)$ is the maximum possible $k$ such that $5^k$ divides $x$ . So when $b$ is odd, there are $5$ solutions. Thus, we have in total, $380$ solutions.

Page

Toolbox

Search

2021 JMC 10 Problems/Problem 25

Problem

Solution