2020 AMC 10A Problems/Problem 22
Problem
For how many positive integers isnot 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 {, , } 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.