Difference between revisions of "2014 AIME I Problems/Problem 8"
Line 139: | Line 139: | ||
== See also == | == See also == | ||
{{AIME box|year=2014|n=I|num-b=7|num-a=9}} | {{AIME box|year=2014|n=I|num-b=7|num-a=9}} | ||
+ | [[Category:Intermediate Number Theory Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} | ||
− |
Revision as of 15:12, 9 April 2020
Contents
Problem 8
The positive integers and
both end in the same sequence of four digits
when written in base 10, where digit a is not zero. Find the three-digit number
.
Solution 1 (similar to Solution 3)
We have that
Thus, must be divisible by both
and
. Note, however, that if either
or
has both a 5 and a 2 in its factorization, the other must end in either 1 or 9, which is impossible for a number that is divisible by either 2 or 5. Thus, one of them is divisible by
, and the other is divisible by
. Noting that
, we see that 625 would work for
, except the thousands digit is 0. The other possibility is that
is a multiple of 16 and
is a multiple of 625. In order for this to happen,
must be congruent to -1 (mod 16). Since
, we know that
. Thus,
, so
, and our answer is
.
Solution 2 (bashing)
let for positive integer values t,a,b,c,d
when we square N we get that
However we dont have to deal with this whole expression but only with its last 4 digits so it is suffices to consider only:
now we need to compare each decimal digit with
and see whether the digits are congruent in base 10.
we first consider the ones digits:
this can happen for only 3 values : 1, 5 and 6
we can try to solve each case
- Case 1
considering the tenths place we have that:
so
considering the hundreds place we have that
so again
now considering the thousands place we have that
so we get
but
cannot be equal to 0 so we consider
- Case 2
considering the tenths place we have that:
( the extra 20 is carried from
which is equal to 25)
so
considering the hundreds place we have that
( the extra 100c is carried from the tenths place)
so
now considering the thousands place we have that
( the extra 1000b is carried from the hundreds place)
so a is equal 0 again
- Case 3
considering the tenths place we have that:
( the extra 20 is carried from
which is equal to 25)
if
then we have
so
considering the hundreds place we have that
( the extra 100c+100 is carried from the tenths place)
if then we have
so
now considering the thousands place we have that
( the extra 1000b+6000 is carried from the hundreds place)
if then we have
so
so we have that the last 4 digits of N are
and
is equal to
Solution 3 (general)
By the Chinese Remainder Theorem, the equation is equivalent to the two equations:
Since
and
are coprime, the only solutions are when
.
Let ,
. The statement of the Chinese Remainder theorem is that
is an isomorphism between the two rings. In this language, the solutions are
,
,
, and
. Now we easily see that
and
. Noting that
, it follows that
. To compute
, note that
in
, so since
is linear in its arguments (by virtue of being an isomorphism),
.
The four candidate digit strings are then
. Of those, only
has nonzero first digit, and therefore the answer is
.
Solution 4 (semi-bashing)
- Note -
means the number formed when the digits represented by
,
,
, and
are substituted in.
.
WLOG, we can assume that is a 4-digit integer
. Note that the only
that will satisfy
will also satisfy
, as the units digit of
is affected only by
, regardless of
,
, or
.
By checking the numbers 0-9, we see that the only possible values of are
.
Now, we seek to find . Note that the only
that will satisfy
will also satisfy
, by the same reasoning as above - the last two digits of
are only affected by
and
. As we already have narrowed choices for
, we start reasoning out.
First, we note that if , then
, as a number ending in 0, and therefore divisible by 10, is squared, the result is divisible by 100, meaning it ends in two 0's. However, if
ends in
, then recursively,
and
must be
, as a number divisible by 100 squared ends in four zeros. As
cannot be 0, we throw out this possibility, as the only solution in this case is
.
Now, let's assume that .
is equal to
. Squaring this gives
, and when modulo 100 is taken, it must equal
. As
is an integer,
must be divisible by 100, so
, which must be equivalent to
. Note that this is really
and
, and comparing the 10's digits. So really, we're just looking for when the units digit of
and
are equal, and a quick check reveals that this is only true when
.However, if we extend this process to find
and
, we'd find that they are also 0. The only solution in this case is
, and since
here, this is not our solution. Therefore, there are no valid solutions in this case.
Let's assume that . Note that
, and when modulo 100 is taken, 25 is the remainder. So all cases here have squares that end in 25, so
is our only case here. A quick check reveals that
, which works for now.
Now, let . Note that
. Taking modulo 100, this reduces to
, which must be equivalent to
. Again, this is similar to
and
, so we see when the units digits of
and
are equal. To make checking faster, note that
is necessarily even, so
is necessarily odd, so
must be odd. Checking all the odds reveals that only
works, so this case gives
. Checking quickly
, which works for now.
Now, we find , given two possibilities for
.
Start with .
Note that if we square this, we get
, which should be equivalent to
modulo 1000. Note that, since
is an integer,
simplifies modulo 1000 to
. Therefore, the only
that works here is
.
.
Now, assume that . We have
, and when squared, becomes
, which, modulo 1000, should be equivalent to
. Reducing
modulo 1000 gives
. Using the same technique as before, we must equate the hundreds digit of
to
, or equate the units digit of
and
. Since
is necessarily odd, any possible
's must be odd. A quick check reveals that
is the only solution, so we get a solution of
.
.
Finally, we solve for . Start with
. We have
, which, squared, gives
, and reducing modulo 10000 gives simply 625. So
. However, that makes
. Therefore, no solutions exist in this case.
We turn to our last case, . We have
, and reducing modulo 10000 gives
, which must be equivalent to
. So we must have
being equivalent to
modulo 1000. So, the units digit of
must be equal to
. Since
is odd,
must be odd. Lo and behold, the only possibility for
is
. Therefore,
, so our answer is
.
See also
2014 AIME I (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.