2014 AIME I Problem 8

Attempt Problem 8 of the 2014 AIME I below, then check your answer against the professionally curated solution 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 problems are used with official legal permission of the Mathematical Association of America (MAA).

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.

Answer: 937
Concepts:modular arithmeticChinese Remainder Theoremdigits
Difficulty rating: 2710
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 7#7
Full Exam

Problem 8 in Other Years