Maths Olympiad Prep

Library / /3 of 13

Number theory Difficulty 5.5 AIME, harder Prove it Italy

Problem:
Find all three-digit natural numbers nn (100n999)(100 \leq n \leq 999) that are equal to the number formed by the last three digits of n2n^{2}.

Solutions — 2

Solution 1

Solution:
The required numbers are 376376 and 625625.
The square of nn has the same last three digits as nn if and only if n2n=n(n1)n^{2}-n=n(n-1) is divisible by 1000=23531000=2^{3} \cdot 5^{3}. Since nn and n1n-1 are coprime, only one of the two is even and only one of the two can be divisible by 55. Therefore we have the following possibilities:
- nn is divisible both by 232^{3} and by 535^{3}, hence nn is divisible by 10001000: no three-digit number nn has this property;
- n1n-1 is divisible both by 232^{3} and by 535^{3}, hence n1n-1 is divisible by 10001000: no three-digit number nn has this property;
- nn is divisible by 232^{3} and n1n-1 is divisible by 535^{3}; the only three-digit number with these properties is n=376n=376, (a direct check indeed gives n2=141376n^{2}=141376);
- nn is divisible by 535^{3} and n1n-1 is divisible by 232^{3}; the only three-digit number with these properties is n=625n=625, (a direct check indeed gives n2=390625n^{2}=390625).

Solution 2

Solution:
Let us represent nn as ABCABC, where A,B,CA, B, C are its decimal digits. We must obtain ABC2=XYZABCABC^{2}=XYZABC. Observe that, in general, the last digit of n2n^{2} depends only on the last digit of nn, just as the last two digits of n2n^{2} depend only on the last two digits of nn.
By direct verification, the units digit CC can only be 0,1,5,60,1,5,6.
If C=0C=0, then nn is divisible by 1010, so n2n^{2} is divisible by 100100 and hence also B=0B=0. But then nn is divisible by 100100, n2n^{2} is divisible by 1000010000 and hence also A=0A=0, which is not allowed.
If C=1C=1, since (10B+1)2=100B2+20B+1(10B+1)^{2}=100B^{2}+20B+1, we must have 2B=B2B=B, that is B=0B=0, or 2B=10+B2B=10+B, which is impossible. If B=0B=0, since (100A+1)2=10000A2+200A+1(100A+1)^{2}=10000A^{2}+200A+1, we obtain as above A=0A=0, that is n=1n=1, which is not allowed.
If C=5C=5, since (10B+5)2=100B2+100B+25(10B+5)^{2}=100B^{2}+100B+25, we must have B=2B=2. Similarly, from (100A+25)2=10000A2+5000A+625(100A+25)^{2}=10000A^{2}+5000A+625 we obtain A=6A=6. Indeed, 6252=390625625^{2}=390625 and hence n=625n=625 is a solution.
If C=6C=6, since (10B+6)2=100B2+120B+36(10B+6)^{2}=100B^{2}+120B+36, we must have 2B+3=B2B+3=B, which is impossible, or 2B+3=10+B2B+3=10+B, that is B=7B=7. Finally, from (100A+76)2=10000A2+15200A+5776(100A+76)^{2}=10000A^{2}+15200A+5776, we obtain 2A+7=A2A+7=A, which is impossible, or 2A+7=10+A2A+7=10+A, that is A=3A=3. Indeed, 3762=141376376^{2}=141376 and hence n=376n=376 is a solution.

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

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.