2014 AIME I Problem 8

Below is the professionally curated solution for Problem 8 of the 2014 AIME I, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2014 AIME I solutions, or check the answer key.

All of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:modular arithmeticChinese Remainder Theoremdigits

Difficulty rating: 2710

8.

The positive integers NN and N2N^2 both end in the same sequence of four digits abcdabcd when written in base 10,10, where digit aa is not zero. Find the three-digit number abc.abc.

Solution:

The condition is N2N(mod104),N^2 \equiv N \pmod{10^4}, that is, N(N1)0(mod2454).N(N-1) \equiv 0 \pmod{2^4 \cdot 5^4}. Since consecutive integers are coprime, 1616 divides one of N,N, N1N - 1 and 625625 divides one of them. This gives four cases modulo 10000:10000: N0,N \equiv 0, N1,N \equiv 1, N625N \equiv 625 (which is 00 mod 625625 and 11 mod 1616), and N9376N \equiv 9376 (which is 00 mod 1616 and 11 mod 625625).

The last four digits abcdabcd must have a0,a \ne 0, which rules out 0000,0000, 0001,0001, and 0625.0625. So abcd=9376abcd = 9376 — for instance 93762=879093769376^2 = 87909376 — and abc=937.abc = 937.

← Problem 7Full ExamProblem 9

Problem 8 in Other Years