2021 JMC 10 Problems/Problem 25
Problem
How many ordered pairs of positive integers with
and
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?
Solution
The problem asks for when and
have the same number of powers of 5.
First, when is even, the numerator
is not divisible by
, so the denominator must also not be divisible by
. So
if and only if
. This gives
solutions.
When is odd,
has at least 3 powers of
due to the sum of
-th powers factorization for odd
. In order for
, we must have
. Note that
(taking
and/or
modulo 125 will work). Therefore,
. It is clear that
must be satisfied. To verify that all
with
work, we check with Lift-the-Exponent Lemma;
where
is the maximum possible
such that
divides
. So when
is odd, there are
solutions. Thus, we have in total,
solutions.