2014 AIME I Problems/Problem 8
Contents
Problem 8
The positive integers and both end in the same sequence of four digits when written in base , 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 and a in its factorization, the other must end in either or , which is impossible for a number that is divisible by either or . Thus, one of them is divisible by , and the other is divisible by . Noting that , we see that would work for , except the thousands digit is . The other possibility is that is a multiple of and is a multiple of . In order for this to happen, Since , we know that . Thus, , so , and our answer is .
Solution 2 (bashing)
let for positive integer values . When we square we get that
However, we don't 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 so we consider
- Case 2
considering the tenths place we have that:
( the extra is carried from which is equal to ) so
considering the hundreds place we have that
( the extra is carried from the tenths place) so
now considering the thousands place we have that
( the extra is carried from the hundreds place) so a is equal 0 again
- Case 3
considering the tenths place we have that:
( the extra is carried from which is equal to ) if then we have
so
considering the hundreds place we have that
( the extra is carried from the tenths place)
if then we have
so
now considering the thousands place we have that
( the extra is carried from the hundreds place)
if then we have
so
so we have that the last 4 digits of 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 is taken, 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 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 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.