Difference between revisions of "2014 AIME I Problems/Problem 8"
(→Solution (bashing)) |
(→Solution (general)) |
||
Line 4: | Line 4: | ||
==Solution (general)== | ==Solution (general)== | ||
+ | |||
+ | We have that <math>N^2 - N = N(N - 1)\equiv 0\mod{10000}</math> | ||
+ | |||
+ | Thus, <math>N(N-1)</math> must be divisible by both <math>5^4</math> and <math>2^4</math>. Note, however, that if either <math>N</math> or <math>N-1</math> 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 <math>2^4 = 16</math>, and the other is divisible by <math>5^4 = 625</math>. Noting that <math>625 \equiv 1\mod{16}</math>, we see that 625 would work for <math>N</math>, except the thousands digit is 0. The other possibility is that <math>N</math> is a multiple of 16 and <math>N-1</math> is a multiple of 625. In order for this to happen, <math>N-1</math> must be congruent to -1 (mod 16). Since <math>625 \equiv 1 \mod{16}</math>, we know that <math>15*625 = 9375 \equiv 15 \equiv -1 \mod{16}</math>. Thus, <math>N-1 = 9375</math>, so <math>N = 9376</math>, and our answer is <math>\boxed{937}</math>. | ||
== Solution (bashing)== | == Solution (bashing)== |
Revision as of 12:19, 15 March 2014
Contents
[hide]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 (general)
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 (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: know we need to compare each decimal digit with and see whether the digits are congrount 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 (not bashing)
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 .
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.