Difference between revisions of "2014 AIME I Problems/Problem 8"
(→Problem 8) |
|||
Line 90: | Line 90: | ||
so we have that the last 4 digits of N are <math>9376</math> | so we have that the last 4 digits of N are <math>9376</math> | ||
and <math>abc</math> is equal to <math>937</math> | and <math>abc</math> is equal to <math>937</math> | ||
+ | |||
+ | == Solution (not bashing) == | ||
+ | By the Chinese Remainder Theorem, the equation <math>N(N-1)\equiv 0\pmod{10000}</math> is equivalent to the two equations: | ||
+ | \begin{align*} | ||
+ | N(N-1)&\equiv 0\pmod{16},\ | ||
+ | N(N-1)&\equiv 0\pmod{625}. | ||
+ | \end{align*} | ||
+ | Since <math>N</math> and <math>N-1</math> are coprime, the only solutions are when <math>(N\mod{16},N\mod{625})\in\{(0,0),(0,1),(1,0),(1,1)\}</math>. | ||
+ | |||
+ | Let <math>\varphi:\mathbb Z/10000Z\to\mathbb Z/16Z\times\mathbb Z/625Z</math>, <math>x\mapsto (x\mod{16},x\mod{625})</math>. The statement of the Chinese Remainder theorem is therefore that <math>\varphi</math> is an isomorphism between the two rings. In this language, the solutions are <math>\phi^{-1}(0,0)</math>, <math>\phi^{-1}(0,1)</math>, <math>\phi^{-1}(1,0)</math>, and <math>\phi^{-1}(1,1)</math>. Now we easily see that <math>\phi^{-1}(0,0)=0</math> and <math>\phi^{-1}(1,1)=1</math>. Noting that <math>625\equiv 1\pmod{16}</math>, it follows that <math>\phi^{-1}(1,0)=625</math>. To compute <math>\phi^{-1}(0,1)</math>, note that <math>(1,0)=15(0,1)+(1,1)</math> in <math>\mathbb Z/16Z\times\mathbb Z/625Z</math>, so since <math>\phi</math> is linear in its arguments (by virtue of being an isomorphism), <math>\phi^{-1}(1,0)=15\phi^{-1}(0,1)+\phi^{-1}(1,1)=15\times 625+1=9376</math>. | ||
+ | |||
+ | The four candidate digit strings <math>abcd</math> are then <math>0000,0001,0625,9376</math>. Of those, only <math>9376</math> has nonzero first digit, and therefore the answer is <math>\boxed{937}</math>. |
Revision as of 17:24, 14 March 2014
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 (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:
Let , . The statement of the Chinese Remainder theorem is therefore 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 .