2010 AMC 12A Problems/Problem 23
- The following problem is from both the 2010 AMC 12A #23 and 2010 AMC 10A #24, so both problems redirect to this page.
Contents
Problem
The number obtained from the last two nonzero digits of is equal to
. What is
?
Hints and Method of Attack
Let be the result of dividing
by tens such that
is not divisible by
. We want to consider
. But because
is not prime, and because
is obviously divisible by
(if in doubt, look at the answer choices), we only need to consider
.
However, is a very particular number.
, and so is
. How can we group terms to take advantage of this fact?
There might be a problem when you cancel out the s from
. One method is to cancel out a factor of
from an existing number along with a factor of
. But this might prove cumbersome, as the grouping method will not be as effective. Instead, take advantage of inverses in modular arithmetic. Just leave the negative powers of
in a "storage base," and take care of the other terms first. Then, use Fermat's Little Theorem to solve for the power of
.
Video Solution: https://youtu.be/30CamkkifHM?t=766
Solution 1
We will use the fact that for any integer ,
First, we find that the number of factors of in
is equal to
. Let
. The
we want is therefore the last two digits of
, or
. If instead we find
, we know that
, what we are looking for, could be
,
,
, or
. Only one of these numbers will be a multiple of four, and whichever one that is will be the answer, because
has to be a multiple of 4.
If we divide by
by taking out all the factors of
in
, we can write
as
where
where every multiple of 5 is replaced by the number with all its factors of 5 removed. Specifically, every number in the form
is replaced by
, and every number in the form
is replaced by
.
The number can be grouped as follows:
Where the first line is composed of the numbers in that aren't multiples of five, the second line is the multiples of five and not 25 after they have been divided by five, and the third line is multiples of 25 after they have been divided by 25.
Using the identity at the beginning of the solution, we can reduce to
Using the fact that (or simply the fact that
if you have your powers of 2 memorized), we can deduce that
. Therefore
.
Finally, combining with the fact that yields
.
Solution 2
Let be
after we truncate its zeros. Notice that
has exactly (floored)
factors of 5; thus,
We shall consider
modulo 4 and 25, to determine its residue modulo 100. It is easy to prove that
is divisible by 4 (consider the number of 2s dividing
minus the number of 5s dividing
), and so we only need to consider
modulo 25.
Now, notice that for integers we have
Thus, for integral a: Using this process, we can essentially remove all the numbers which had not formerly been a multiple of 5 in
from consideration.
Now, we consider the remnants of the 5, 10, 15, 20, ..., 90 not yet eliminated. The 10, 20, 30, ..., 90 becomes 1, 2, 3, 4, 1, 6, 7, 8, 9, whose product is 1 mod 25. Also, the 5, 5, 15, 25, ..., 85 becomes 1, 1, 3, 1, 7, 9, 11, 13, 3, 17 and . We deduce that from multiplying out the 1, 1, 3, 1, 7, ..., 17 is equivalent to 2 modulo 25, and so we need to compute
. Also note that
. And by combining Euler's Theorem with Fermat's Little Theorem, we get that
. Because 12 is also a multiple of 4, we can utilize the Chinese Remainder Theorem to show that
and so the answer is
.
Solution 3
We start of by truncating the s off
, just like Solution 2. Since there are
terminating zeroes, we have the number we obtain from truncating the terminating zeroes at the end of
will be
.
By Chinese Remainder Theorem, we can divide the mod into mod
and mod
. We know that there are way more than
s in
, so we have
Now, notice that is basically
without any factors that are multiples of
.
We can rewrite the expression as
We also have
Squaring the expression gets us
Notice that there are of this string of numbers multiplied together occurs four times in
, the fourth being only a partial
Multiplying these together gives us
By Euler's Theorem, we have
Thus, we want to solve and
. An obvious solution is
and by Chinese Remainder Theorem, we have
is the only solution. So thus,
~sml1809
~minor edits by KevinChen_Yay excuse me but isn't the inverse of 2 mod 25 13?
Remark (Chinese Remainder Theorem)
Both solution 1 and solution 2 rely on ,
to get
By Chinese Remainder Theorem, the general solution of the system of linear congruences is:
,
,
Find
and
such that
,
Then
![]()
In this problem, ,
:
,
,
![]()
,
Then
![]()
See also
2010 AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 22 |
Followed by Problem 24 |
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 12 Problems and Solutions |
2010 AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 23 |
Followed by Problem 25 | |
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.