2017 AIME II Problems/Problem 8
Problem
Find the number of positive integers less than
such that
is an integer.
Solution 1 (Not Rigorous)
Writing the last two terms with a common denominator, we have By inspection. this yields that
. Therefore, we get the final answer of
.
Solution 2
Taking out the part of the expression and writing the remaining terms under a common denominator, we get
. Therefore the expression
must equal
for some positive integer
.
Taking both sides mod
, the result is
. Therefore
must be even. If
is even, that means
can be written in the form
where
is a positive integer. Replacing
with
in the expression,
is divisible by
because each coefficient is divisible by
. Therefore, if
is even,
is divisible by
.
Taking the equation mod
, the result is
. Therefore
must be a multiple of
. If
is a multiple of three, that means
can be written in the form
where
is a positive integer. Replacing
with
in the expression,
is divisible by
because each coefficient is divisible by
. Therefore, if
is a multiple of
,
is divisibly by
.
Taking the equation mod
, the result is
. The only values of
that satisfy the equation are
and
. Therefore if
is
or
mod
,
will be a multiple of
.
The only way to get the expression to be divisible by
is to have
,
, and
. By the Chinese Remainder Theorem or simple guessing and checking, we see
. Because no numbers between
and
are equivalent to
or
mod
, the answer is
.
Solution 3
Note that will have a denominator that divides
. Therefore, for the expression to be an integer,
must have a denominator that divides
. Thus,
, and
. Let
. Substituting gives
. Note that the first
terms are integers, so it suffices for
to be an integer. This simplifies to
. It follows that
. Therefore,
is either
or
modulo
. However, we seek the number of
, and
. By CRT,
is either
or
modulo
, and the answer is
.
-TheUltimate123
Step Solution
Clearly is an integer. The part we need to verify as an integer is, upon common denominator,
. Clearly, the numerator must be even for the fraction to be an integer. Therefore,
is even and n is even, aka
for some integer
. Then, we can substitute
and see that
is trivially integral. Then, substitute for the rest of the non-confirmed-integral terms and get
. It is also clear that for this to be an integer, which it needs to be, the numerator has to be divisible by 3. The only term we worry about is the
, and we see that
for some integer
. From there we now know that
. If we substitute again, we see that all parts except the last two fractions are trivially integral. In order for the last two fractions to sum to an integer we see that
, so combining with divisibility by 6,
is
or
(mod
). There are
cases for each, hence the answer
.
See Also
2017 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 7 |
Followed by Problem 9 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.