Maths Olympiad Prep

Library / /193 of 213

, 2025

Number theory Difficulty 3.8 AMC 10/12 Find the answer Canada

The number 20132013 is
multiplied by a positive integer nn.
The last four digits of the result are 20252025. What is the sum of the digits of
the smallest possible value of nn?

Pick one

Solution

Solution 1:

Let the last three digits of nn
be abcabc. That is, nn has units digit cc, tens digit bb and hundreds digit aa.

(By the end of this solution, we will have demonstrated why considering
only the last three digits of nn was
sufficient.)

The units digit of the product $2013×\$2013\times
nisequaltotheunitsdigitof is equal to the units digit of 3×3\times c.. $[t] cccccc ! ! !2 ! ! ! ! ! !0 ! ! ! ! ! !1 ! ! ! ! ! !3 ! ! ! ! ! !a ! ! ! ! ! !b ! ! ! ! ! !c ! ! ! ! ! !2 ! ! ! ! ! !0 ! ! ! ! ! !2 ! ! ! ! ! !5 ! ! !\text{[t] cccccc ! ! !2 ! ! ! ! ! !0 ! ! ! ! ! !1 ! ! ! ! ! !3 ! ! ! ! ! !a ! ! ! ! ! !b ! ! ! ! ! !c ! ! ! ! ! !2 ! ! ! ! ! !0 ! ! ! ! ! !2 ! ! ! ! ! !5 ! ! !}

Since the units digit of the product 2013×n2013\times n is 5, then the units digit
of 3×c3\times c is 55, and so c=5c=5.

(You should confirm for yourself that this is the only possible value of
cc.) [t] cccccc ! !2 ! ! ! ! ! !0 ! ! ! ! ! !1 ! ! ! ! ! !3 ! ! ! ! ! ! ! ! !5 ! ! ! ! ! ! ! ! !1 ! ! ! ! ! ! ! ! ! !0 ! ! ! ! !0 ! ! ! ! ! !6 ! ! ! !5 ! ! !\text{[t] cccccc ! !2 ! ! ! ! ! !0 ! ! ! ! ! !1 ! ! ! ! ! !3 ! ! ! ! ! ! ! ! !5 ! ! ! ! ! ! ! ! !1 ! ! ! ! ! ! ! ! ! !0 ! ! ! ! !0 ! ! ! ! ! !6 ! ! ! !5 ! ! !}

Continuing the long multiplication, the tens digit of nn is bb, and so the tens digit of 2013×n2013\times n is equal to the units digit
of 6+3b6+3b, as shown.

Since the units digit of 6+3b6+3b is
22, then the units digit of 3b3b is 66, and so b=2b=2.

(You should confirm for yourself that this is the only possible value of
bb.) [t] cccccc ! ! !2 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! ! !1 ! ! ! ! ! !3 ! ! ! ! ! !b ! ! ! ! ! !5 ! ! ! ! ! !1 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! !6 ! ! ! ! ! !5 ! ! ! ! ! !3b ! ! ! ! ! !2 ! ! ! ! ! !5 ! ! !\text{[t] cccccc ! ! !2 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! ! !1 ! ! ! ! ! !3 ! ! ! ! ! !b ! ! ! ! ! !5 ! ! ! ! ! !1 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! !6 ! ! ! ! ! !5 ! ! ! ! ! !3b ! ! ! ! ! !2 ! ! ! ! ! !5 ! ! !}

The multiplication completed to this point is shown to the
right.

We have determined that the last two digits of the product 2013×n2013\times n are 2525 exactly when the last two digits of
nn are 2525. [t] cccccc ! ! !2 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! ! !1 ! ! ! ! ! !3 ! ! ! ! ! !2 ! ! ! ! ! !5 ! ! ! ! ! !1 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! ! !6 ! ! ! ! ! !5 ! ! ! ! ! !4 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !2 ! ! ! ! ! ! ! ! ! ! ! !6 ! ! ! ! ! !2 ! ! ! ! ! !5 ! ! !\text{[t] cccccc ! ! !2 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! ! !1 ! ! ! ! ! !3 ! ! ! ! ! !2 ! ! ! ! ! !5 ! ! ! ! ! !1 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! ! !6 ! ! ! ! ! !5 ! ! ! ! ! !4 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !2 ! ! ! ! ! ! ! ! ! ! ! !6 ! ! ! ! ! !2 ! ! ! ! ! !5 ! ! !}

Continuing the long multiplication, the hundreds digit of nn is aa, and so the hundreds digit of 2013×n2013\times n is equal to the units digit
of 1+0+2+3a1+0+2+3a (the 11 is the "carry" from the tens
column).

Since the units digit of 3+3a3+3a is
00, then the units digit of 3a3a is 77, and so a=9a=9.

(You should confirm that this is the only possible value of aa.) [t] cccccc ! ! !2 ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! !1 ! ! ! ! ! !3 ! ! ! ! ! !a ! ! ! ! ! ! !2 ! ! ! ! ! !5 ! ! ! ! ! !1 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! !6 ! ! ! ! ! !5 ! ! ! ! ! !4 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! ! ! !2 ! ! ! ! ! !6 ! ! ! ! ! !3a ! ! ! ! ! !0 ! ! ! ! ! !2 ! ! ! ! ! !5 ! ! !\text{[t] cccccc ! ! !2 ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! !1 ! ! ! ! ! !3 ! ! ! ! ! !a ! ! ! ! ! ! !2 ! ! ! ! ! !5 ! ! ! ! ! !1 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! !6 ! ! ! ! ! !5 ! ! ! ! ! !4 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !0 ! ! ! ! ! ! ! ! ! ! ! ! ! !2 ! ! ! ! ! !6 ! ! ! ! ! !3a ! ! ! ! ! !0 ! ! ! ! ! !2 ! ! ! ! ! !5 ! ! !}

The last three digits of $2013×\$2013\times
nare are 025$ exactly when the
last three digits of nn are 925925 (that is, a=9a=9, b=2b=2, c=5c=5 are the only possibilities for aa, bb, cc).

The multiplication completed to this point is shown below. [t] cccccccc ! ! !2 ! ! ! ! ! !0 ! ! ! ! ! !1 ! ! ! ! ! !3 ! ! ! ! ! !9 ! ! ! ! ! !2 ! ! ! ! ! !5 ! ! ! ! ! !1 ! ! ! ! ! !0 ! ! ! !0 ! ! ! ! !6 ! ! ! ! ! !5 ! ! ! ! ! !4 ! ! ! ! !0 ! ! ! !2 ! ! ! ! !6 ! ! ! ! ! !1 ! ! ! ! !8 ! ! ! ! !1 ! ! ! ! !1 ! ! ! !7 ! ! ! ! ! !1 ! ! ! ! ! ! !8 ! ! ! ! ! ! !6 ! ! ! ! ! ! ! !2 ! ! ! ! ! ! !0 ! ! ! ! ! !2 ! ! ! ! ! !5 ! ! !\text{[t] cccccccc ! ! !2 ! ! ! ! ! !0 ! ! ! ! ! !1 ! ! ! ! ! !3 ! ! ! ! ! !9 ! ! ! ! ! !2 ! ! ! ! ! !5 ! ! ! ! ! !1 ! ! ! ! ! !0 ! ! ! !0 ! ! ! ! !6 ! ! ! ! ! !5 ! ! ! ! ! !4 ! ! ! ! !0 ! ! ! !2 ! ! ! ! !6 ! ! ! ! ! !1 ! ! ! ! !8 ! ! ! ! !1 ! ! ! ! !1 ! ! ! !7 ! ! ! ! ! !1 ! ! ! ! ! ! !8 ! ! ! ! ! ! !6 ! ! ! ! ! ! ! !2 ! ! ! ! ! ! !0 ! ! ! ! ! !2 ! ! ! ! ! !5 ! ! !}

This shows that when n=925n=925, the
last four digits of the product $2013×\$2013\times
nare are 2025$, as
required.

Adding additional digits to nn will
increase the value of nn, and since
we are asked for the smallest possible value of nn, we stop here.

Thus, the smallest possible value of nn for which 2013×n2013\times n has last four digits 20252025,
is n=925n=925, and so the sum of the
digits of nn is 9+2+5=169+2+5=16.

Solution 2:

We begin by showing that every positive integer having last two
digits 2525 is a multiple of 2525.

(It is worth noting that it is not true that every multiple of
2525 has last two digits 2525.)

All positive integers whose last two digits are 2525, are 2525 more than some non-negative multiple
of 100100.

That is, all positive integers whose last two digits are 2525 can be expressed as 100k+25100k+25 for some integer k0k\geq0.

Since 100k100k is divisible by 2525, and 2525 is divisible by 2525, then 100k+25100k+25 is divisible by 2525.

Thus, every positive integer whose last two digits are 2525 is a multiple of 2525, and so 2013×n2013\times n is a multiple of 2525.

Since 2013=3×11×612013=3\times11\times61 does
not have a prime factor of 55, then
2013×n2013\times n is a multiple of 2525 exactly when nn is a multiple of 2525.

The last two digits of 2013×n2013\times n
are equal to the two-digit number formed by the last two digits of the
product of 1313 and the last two
digits of nn.

What are the last two digits of nn?
Since nn is a multiple of 2525, then the last two digits of nn could be 2525, 5050, 7575, or 0000.

(You should confirm that these are the only possibilities.)

Thus, the last two digits of $2013 ×\times
n are equal to the last two digits of 13×2513\times25or or 13×5013\times50or or 13×7513\times75or or 13×13\times 00,whichare, which are 25,, 50,, 75,and, and 00$ respectively.

Since we require the last two digits of 2013×n2013\times n to be 2525, then the last two digits of nn are 2525.

We have reduced the problem to finding the smallest value of the
positive integer nn with last two
digits 2525 so that the last four
digits of 2013×n2013\times n are 20252025.

We substitute $n=25, 125, 225, 325,425,
\dots,andsoon,inturn,intotheproduct, and so on, in turn, into the product 2013 ×\times n$.

Evaluating these products, we determine that 2013×925=18620252013\times 925 = 1\,862\,025 is the first
time that the last four digits of $2013×\$2013\times
nare are 2025$.

Thus, the smallest possible value of nn for which 2013×n2013\times n has last four digits 20252025 is n=925n=925, and the sum of the digits of nn is 9+2+5=169+2+5=16.

Want a route through all this instead of an archive? The track puts 2,444 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.