Difference between revisions of "2014 AIME I Problems/Problem 8"
(→Solution (not bashing)) |
|||
Line 93: | Line 93: | ||
== Solution (not bashing) == | == 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: | By the Chinese Remainder Theorem, the equation <math>N(N-1)\equiv 0\pmod{10000}</math> is equivalent to the two equations: | ||
− | \begin{align*} | + | <cmath>\begin{align*} |
N(N-1)&\equiv 0\pmod{16},\\ | N(N-1)&\equiv 0\pmod{16},\\ | ||
N(N-1)&\equiv 0\pmod{625}. | N(N-1)&\equiv 0\pmod{625}. | ||
− | \end{align*} | + | \end{align*}</cmath> |
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>. | 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>. | ||
Revision as of 18: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:
Since
and
are coprime, the only solutions are when
.
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
.