Difference between revisions of "2014 AIME I Problems/Problem 8"
(→Solution (bashing)) |
|||
Line 21: | Line 21: | ||
we have that: | we have that: | ||
− | <math>20cd=20c\equiv 10c | + | <math>20cd=20c\equiv 10c \pmod {100}</math> |
so <math>c= 0</math> | so <math>c= 0</math> | ||
considering the hundreds place we have that | considering the hundreds place we have that | ||
− | <math>200bd+100c^2= 200b \equiv 100b | + | <math>200bd+100c^2= 200b \equiv 100b \pmod{1000}</math> |
so again <math>b=0</math> | so again <math>b=0</math> | ||
now considering the thousands place we have that | now considering the thousands place we have that | ||
− | <math>2000ad+2000bc = 2000a \equiv 1000a | + | <math>2000ad+2000bc = 2000a \equiv 1000a \pmod {10000}</math> |
so we get <math>a=0</math> but <math>a</math> cannot be equal to 0 so we consider <math>d=5</math> | so we get <math>a=0</math> but <math>a</math> cannot be equal to 0 so we consider <math>d=5</math> | ||
Line 38: | Line 38: | ||
we have that: | we have that: | ||
− | <math>20cd+20=100c+20\equiv 20 \equiv 10c | + | <math>20cd+20=100c+20\equiv 20 \equiv 10c \mod {100}</math> |
( the extra 20 is carried from <math>d^2</math> which is equal to 25) | ( the extra 20 is carried from <math>d^2</math> which is equal to 25) | ||
so <math>c=2</math> | so <math>c=2</math> | ||
Line 44: | Line 44: | ||
considering the hundreds place we have that | considering the hundreds place we have that | ||
− | <math>200bd+100c^2+100c= 1000b+600 \equiv600\equiv 100b | + | <math>200bd+100c^2+100c= 1000b+600 \equiv600\equiv 100b \pmod{1000}</math> |
( the extra 100c is carried from the tenths place) | ( the extra 100c is carried from the tenths place) | ||
so<math> b=6</math> | so<math> b=6</math> | ||
Line 50: | Line 50: | ||
now considering the thousands place we have that | now considering the thousands place we have that | ||
− | <math>2000ad+2000bc +1000b= 10000a+24000+ 6000\equiv0\equiv 1000a | + | <math>2000ad+2000bc +1000b= 10000a+24000+ 6000\equiv0\equiv 1000a \pmod {10000}</math> |
( the extra 1000b is carried from the hundreds place) | ( the extra 1000b is carried from the hundreds place) | ||
so a is equal 0 again | so a is equal 0 again | ||
Line 58: | Line 58: | ||
we have that: | we have that: | ||
− | <math>20cd+30=120c+30\equiv 30+20c \equiv 10c | + | <math>20cd+30=120c+30\equiv 30+20c \equiv 10c \pmod {100}</math> |
( the extra 20 is carried from <math>d^2</math> which is equal to 25) | ( the extra 20 is carried from <math>d^2</math> which is equal to 25) | ||
if <math>c=7</math> then we have | if <math>c=7</math> then we have | ||
− | <math>30+20*7 \equiv 70\equiv7*10 | + | <math>30+20*7 \equiv 70\equiv7*10 \pmod{100}</math> |
so <math>c=7</math> | so <math>c=7</math> | ||
Line 68: | Line 68: | ||
considering the hundreds place we have that | considering the hundreds place we have that | ||
− | <math>200bd+100c^2+100c+100= 1200b+4900+700 \equiv200b+700\equiv 100b | + | <math>200bd+100c^2+100c+100= 1200b+4900+700 \equiv200b+700\equiv 100b \pmod{1000}</math> |
( the extra 100c+100 is carried from the tenths place) | ( the extra 100c+100 is carried from the tenths place) | ||
if <math>b=3</math> then we have | if <math>b=3</math> then we have | ||
− | <math>700+200*3 \equiv 300\equiv3*100 | + | <math>700+200*3 \equiv 300\equiv3*100 \pmod {1000}</math> |
so <math>b=3</math> | so <math>b=3</math> | ||
Line 79: | Line 79: | ||
now considering the thousands place we have that | now considering the thousands place we have that | ||
− | <math>2000ad+2000bc +1000b+5000+1000= 12000a+42000+ 3000+6000\equiv0\equiv 2000a+1000\equiv 1000a | + | <math>2000ad+2000bc +1000b+5000+1000= 12000a+42000+ 3000+6000\equiv0\equiv 2000a+1000\equiv 1000a \pmod {10000}</math> |
( the extra 1000b+6000 is carried from the hundreds place) | ( the extra 1000b+6000 is carried from the hundreds place) | ||
if <math>a=9</math> then we have | if <math>a=9</math> then we have | ||
− | <math>2000*9+1000 \equiv 9000\equiv9*1000 | + | <math>2000*9+1000 \equiv 9000\equiv9*1000 \pmod {1000}</math> |
so <math>a=9</math> | so <math>a=9</math> |
Revision as of 19:49, 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 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.