Maths Olympiad Prep

Library / /16 of 22

Number theory Difficulty 5.3 AIME, harder Prove it United States

Problem:

Denote by f(n)f(n) the integer obtained by reversing the digits of a positive integer nn. Find the greatest integer that is certain to divide n4f(n)4n^{4}-f(n)^{4} regardless of the choice of nn.

Solution

Solution:

The answer is 9999.

Let x=dn1d2d1d0x = \overline{d_{n-1} \ldots d_{2} d_{1} d_{0}}, i.e. x=10n1dn1++102d2+10d1+d0x = 10^{n-1} d_{n-1} + \cdots + 10^{2} d_{2} + 10 d_{1} + d_{0}. Then y=f(x)=10n1d0+10n2d1++10dn2+dn1y = f(x) = 10^{n-1} d_{0} + 10^{n-2} d_{1} + \cdots + 10 d_{n-2} + d_{n-1}.

Let us show separately that 9x4y49 \mid x^{4} - y^{4} and that 11x4y411 \mid x^{4} - y^{4}.

Since 101(mod9)10 \equiv 1 \pmod{9}, xydn1+dn2++d1+d0(mod9)x \equiv y \equiv d_{n-1} + d_{n-2} + \cdots + d_{1} + d_{0} \pmod{9}, so 9xy9 \mid x - y and therefore also 9(xy)(x3+x2y+xy2+y3)=x4y49 \mid (x - y)(x^{3} + x^{2} y + x y^{2} + y^{3}) = x^{4} - y^{4}.

Since 101(mod11)10 \equiv -1 \pmod{11}, xdn1dn2+d1±d0(mod11)x \equiv d_{n-1} - d_{n-2} + \cdots \mp d_{1} \pm d_{0} \pmod{11} and yd0+d1+dn2±dn1(mod11)y \equiv d_{0} + d_{1} + \cdots \mp d_{n-2} \pm d_{n-1} \pmod{11}, i.e. x±yx \equiv \pm y. In either case x4y4(mod11)x^{4} \equiv y^{4} \pmod{11}, so 11x4y411 \mid x^{4} - y^{4}.

Since 99 and 1111 are relatively prime, their product 9999 must divide x4y4x^{4} - y^{4}.

To see that there is no larger integer that always divides n4f(n)4n^{4} - f(n)^{4}, let n=10n = 10, so that f(n)=01=1f(n) = 01 = 1, n4f(n)4=9999=3211101n^{4} - f(n)^{4} = 9999 = 3^{2} \cdot 11 \cdot 101, and let n=21n = 21, so that f(n)=12f(n) = 12 and n4f(n)4=173745=3551113n^{4} - f(n)^{4} = 173745 = 3^{5} \cdot 5 \cdot 11 \cdot 13. The greatest common divisor of these two values of n4f(n)4n^{4} - f(n)^{4} is 3211=993^{2} \cdot 11 = 99, so there is no larger integer certain to divide n4f(n)4n^{4} - f(n)^{4}.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.