2021 JMC 10 Problems/Problem 25

Revision as of 14:46, 1 April 2021 by Skyscraper (talk | contribs) (Created page with "==Problem== How many ordered pairs of positive integers <math>(a,b)</math> with <math>a \le 100</math> and <math>b \le 10</math> exist such that neither the numerator nor deno...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.