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
Small Hint:

The condition says N2≡N(mod104),N^2 \equiv N \pmod{10^4}, i.e. N(N−1)≡0(mod24⋅54)N(N-1) \equiv 0 \pmod{2^4 \cdot 5^4}

Big Hint:

NN and N−1N-1 are coprime, so 1616 and 625625 each divide one of them; only one of the four cases has nonzero leading digit aa

Solution:

The condition is N2≡N(mod104),N^2 \equiv N \pmod{10^4}, that is, N(N−1)≡0(mod24⋅54).N(N-1) \equiv 0 \pmod{2^4 \cdot 5^4}. Since consecutive integers are coprime, 1616 divides one of N,N, N−1N - 1 and 625625 divides one of them. This gives four cases modulo 10000:10000: N≡0,N \equiv 0, N≡1,N \equiv 1, N≡625N \equiv 625 (which is 00 mod 625625 and 11 mod 1616), and N≡9376N \equiv 9376 (which is 00 mod 1616 and 11 mod 625625).

The last four digits abcdabcd must have a≠0,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