Problem:
The positive integers N and N2 both end in the same sequence of four digits abcd when written in base 10, where digit a is not zero. Find the three-digit number abc.
Solution:
Write N=10000M+k, where M is an integer, and 1000≤k≤9999. Then because N2 and N end in the same four digits,
N2−N=(104M+k)2−(104M+k)=104(104M2+2Mk−M)+(k2−k)
ends in four zeroes. Thus 10000=24⋅54 divides k2−k=k(k−1). Because k and k−1 are relatively prime, there are four possibilities.
-
104∣k so k=0,
-
104∣(k−1) so k=1,
-
54∣k and 24∣(k−1) so k=625, and
-
24∣k and 54∣(k−1) so k−1 must be 625m for a positive integer m where 16 divides 625m+1. Because 625≡1(mod16),15⋅625≡15(mod16) and 16 divides 15⋅625+1=9376 implying that k=9376.
The first three cases are not possible if k≥1000, but k=9376 does work. The requested three digit number is 937.
Note that for any positive integer r, if the positive integers N and N2 end in the same r digits, there are always exactly 4 possible sequences of r final digits.
The problems on this page are the property of the MAA's American Mathematics Competitions