2020 AMC 10A Problems/Problem 22
Problem
For how many positive integers is
not divisible by
? (Recall that
is the greatest integer less than or equal to
.)
Solution (Casework)
Expression:
Solution:
Let
Notice that for every integer ,
if
is an integer, then the three terms in the expression above must be
,
if
is an integer, then the three terms in the expression above must be
, and
if
is an integer, then the three terms in the expression above must be
.
if none of
,
, nor
are integral, then the three terms in the expression above must be
.
This is due to the fact that ,
, and
do not collectively share any common factors (other than 1).
Note that doesn't work; to prove this, we just have to substitute
for
in the expression.
This gives us
which is divisible by 3.
Therefore, the case
does not work.
Now, we test the three cases listed above.
Case 1: divides
The first case does not work, as the three terms in the expression must be , as mentioned above, so the sum becomes
, which is divisible by
.
Case 2: divides
Because divides
, the number of possibilities for
is the same as the number of factors of
.
=
So, the total number of factors of
is
.
However, we have to subtract , because the case
doesn't work, as mentioned previously.
We now do the same for the third and last case.
Case 3: divides
Because divides
, the number of possibilities for
is the same as the number of factors of
.
=
So, the total number of factors of
is
.
Again, we have to subtract , for the reason stated in Case 2.
Case 4: divides none of {
}
Now that we have counted all of the cases, we add them.
, so the answer is
.
~dragonchomper
Video Solution
~IceMatrix
See Also
2020 AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 21 |
Followed by Problem 23 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
All AMC 10 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.