Maths Olympiad Prep

Library / /56 of 101

Number theory Difficulty 6.2 National olympiad Prove it Estonia

Find all positive integers nn for which you can replace a digit 44 with the digits 2222 and obtain a number divisible by nn.

Solution

Let nn satisfy the condition and nn' be the number obtained by the replacement of digits. Denote by xx the number formed by the digits to the left of the replaced digit and denote by yy the number formed by the digits to the right of the replaced digit. Let kk be the number of digits in yy. Then n=x10k+1+410k+yn = x \cdot 10^{k+1} + 4 \cdot 10^k + y and n=x10k+2+2210k+yn' = x \cdot 10^{k+2} + 22 \cdot 10^k + y. As nn' is divisible by nn, then so must also be nnn' - n and 10nn10n - n', which yields
x10k+1+410k+y9x10k+1+1810k,(2) x \cdot 10^{k+1} + 4 \cdot 10^k + y \mid 9x \cdot 10^{k+1} + 18 \cdot 10^k, \qquad (2)
x10k+1+410k+y1810k+9y.(3) x \cdot 10^{k+1} + 4 \cdot 10^k + y \mid 18 \cdot 10^k + 9y. \qquad (3)
We will consider the following cases.

* If x=0x = 0, then by (2), t(410k+y)=1810kt (4 \cdot 10^k + y) = 18 \cdot 10^k for some integer tt. As
5(410k+y)5410k>1810k>3510k>3(410k+y)5 (4 \cdot 10^k + y) \ge 5 \cdot 4 \cdot 10^k > 18 \cdot 10^k > 3 \cdot 5 \cdot 10^k > 3 (4 \cdot 10^k + y),
the only option is t=4t = 4. The equation 4(410k+y)=1810k4 (4 \cdot 10^k + y) = 18 \cdot 10^k yields
y=210k4=510k1<10ky = \frac{2 \cdot 10^k}{4} = 5 \cdot 10^{k-1} < 10^k. Altogether n=4510k1n = 45 \cdot 10^{k-1}.

* If x=1x = 1, then by (2), t(1410k+y)=10810kt (14 \cdot 10^k + y) = 108 \cdot 10^k for some integer tt. As
8(1410k+y)81410k>10810k>61510k>6(1410k+y)8 (14 \cdot 10^k + y) \ge 8 \cdot 14 \cdot 10^k > 108 \cdot 10^k > 6 \cdot 15 \cdot 10^k > 6 (14 \cdot 10^k + y),
the only option is t=7t = 7, but the equation 7(1410k+y)=10810k7 (14 \cdot 10^k + y) = 108 \cdot 10^k has no integer solutions, because 710810k7 \nmid 108 \cdot 10^k.

* If x=2x = 2, then by (2), t(2410k+y)=19810kt (24 \cdot 10^k + y) = 198 \cdot 10^k for some integer tt. As
9(2410k+y)92410k>19810k>72510k>7(2410k+y)9 (24 \cdot 10^k + y) \ge 9 \cdot 24 \cdot 10^k > 198 \cdot 10^k > 7 \cdot 25 \cdot 10^k > 7 (24 \cdot 10^k + y),
the only option is t=8t = 8. The equation 8(2410k+y)=19810k8 (24 \cdot 10^k + y) = 198 \cdot 10^k yields y=610k8=7510k2<10ky = \frac{6 \cdot 10^k}{8} = 75 \cdot 10^{k-2} < 10^k. Altogether n=247510k2n = 2475 \cdot 10^{k-2}.

* If x3x \ge 3, then by (3) we have x10k+1+410k+y1810k+9yx \cdot 10^{k+1} + 4 \cdot 10^k + y \le 18 \cdot 10^k + 9y, which yields x10k+11410k+8yx \cdot 10^{k+1} \le 14 \cdot 10^k + 8y. On the other hand x10k+13010k>2210k>1410k+8yx \cdot 10^{k+1} \ge 30 \cdot 10^k > 22 \cdot 10^k > 14 \cdot 10^k + 8y. The equations contradict each other, so no such nn can exist.

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 and solution reproduced as published; topic and difficulty added by this site.