Maths Olympiad Prep

Library / /18 of 18

Number theory Difficulty 7.6 National Olympiad, round 2 Prove it Italy

Problem:

A three-digit number with distinct nonzero digits (say abca b c) is called petaloso [petal-like] if there exists an integer n1n \geq 1 such that the number cba000n zerosc b a \underbrace{00 \cdots 0}_{n \text{ zeros}} is a multiple of abca b c. The smallest nn for which this divisibility holds is called the flower of abca b c.

Example. The number 132 is petaloso, since 132 divides 23100. Since 23100/132=17523100/132 = 175 is an integer but 2310/132=17,52310 / 132=17,5 is not, the flower of 132 is 2.

a. Let abca b c be a three-digit number (with distinct nonzero digits) of the form 2x3y5z2^{x} \cdot 3^{y} \cdot 5^{z} with x,y,zx, y, z nonnegative integers and y2y \leq 2. Prove that abca b c is petaloso.

b. What is the maximum possible value of the flower of a petaloso (three-digit) number?

c. Let abca b c be a petaloso number. Prove that abca b c is not divisible by 13.

Solution

Solution:

a.
We must show that, for nn sufficiently large, the number abc=2x3y5za b c=2^{x} \cdot 3^{y} \cdot 5^{z} divides cba10n=cba2n5nc b a \cdot 10^{n}=c b a \cdot 2^{n} \cdot 5^{n}. We will show that this condition is satisfied with n=max{x,z}n=\max \{x, z\}. Certainly with this choice of nn we have that 2x5z2^{x} \cdot 5^{z} divides 2n5n2^{n} \cdot 5^{n}. It therefore suffices to verify that 3y3^{y} divides cba10nc b a \cdot 10^{n}, and clearly to do this it is enough to show that 3y3^{y} divides cbac b a. For y=0y=0 there is nothing to prove (30=13^{0}=1 divides any number). For y=1y=1 we have that 3 divides abca b c, that is, by the well-known divisibility criterion for 3, that 3 divides a+b+ca+b+c. By the same divisibility criterion we then have that 3=3y3=3^{y} divides cbac b a (whose digit sum is again a+b+ca+b+c), which gives the claim. In the case y=2y=2 we proceed similarly: the divisibility criterion for 9 guarantees that a+b+ca+b+c is a multiple of 9, and hence cbac b a is also a multiple of 3y=93^{y}=9, as desired.

Second solution.
Let us write more properly abc=100a+10b+ca b c=100 a+10 b+c and cba=100c+10b+ac b a=100 c+10 b+a. We are asked to show that 100a+10b+c=2x3y5z100 a+10 b+c=2^{x} \cdot 3^{y} \cdot 5^{z} divides (100c+10b+a)10n(100 c+10 b+a) \cdot 10^{n} for nn sufficiently large. An integer kk divides an integer mm if and only if kk divides mtkm-t k, where tt is any integer. In particular, taking t=10nt=10^{n}, we have that 100a+10b+c100 a+10 b+c divides (100c+10b+a)10n(100 c+10 b+a) \cdot 10^{n} if and only if it divides (100c+10b+a)10n(100a+10b+c)10n=911(ca)10n(100 c+10 b+a) \cdot 10^{n}-(100 a+10 b+c) \cdot 10^{n}=9 \cdot 11 \cdot(c-a) \cdot 10^{n}. Since by hypothesis y2y \leq 2, it is clear that for n=max{x,z}n=\max \{x, z\} we obtain the desired divisibility, since 3y3^{y} divides 9 and 2x5z2^{x} \cdot 5^{z} divides 10max{x,z}=2max{x,z}5max{x,z}10^{\max \{x, z\}}=2^{\max \{x, z\}} \cdot 5^{\max \{x, z\}}.

b.
Let us consider for which kk the number abca b c divides cba10k=cba2k5kc b a \cdot 10^{k}=c b a \cdot 2^{k} \cdot 5^{k}. Let us write the prime factorization of abca b c as 2x5yp1e1pkek2^{x} \cdot 5^{y} \cdot p_{1}^{e_{1}} \cdots p_{k}^{e_{k}}, where p1,,pkp_{1}, \ldots, p_{k} are primes distinct from each other and distinct from 2 and 5. Similarly, let us write the factorization of cbac b a as 2X5Yq1f1qrfr2^{X} \cdot 5^{Y} \cdot q_{1}^{f_{1}} \cdots q_{r}^{f_{r}}. The divisibility condition is that every prime appears in the factorization of abca b c with an exponent less than or equal to the one with which it appears in cba10kc b a \cdot 10^{k}. For primes other than 2 and 5, this means that every pip_{i} also appears in the factorization of cbac b a, and that the exponent with which it divides cbac b a is greater than or equal to the one with which it divides abca b c. This condition does not depend on kk. For the primes 2 and 5, however, the condition
2x5y divides cba10k=2X+k5Y+kq1f1qrfr 2^{x} \cdot 5^{y} \text{ divides } c b a \cdot 10^{k}=2^{X+k} \cdot 5^{Y+k} \cdot q_{1}^{f_{1}} \cdots q_{r}^{f_{r}}
translates into xX+kx \leq X+k and yY+ky \leq Y+k. We then claim that a value of kk strictly greater than 9 can never be necessary: indeed k=10k=10 could only be necessary if x10x \geq 10 or y10y \geq 10, but in that case abca b c would be divisible either by 210=10242^{10}=1024 or by 510>10005^{10}>1000, and hence could not be a three-digit number. This shows that the maximum flower cannot exceed 9. On the other hand, taking abc=512=29a b c=512=2^{9}, we have that the minimum kk for which abca b c divides cba10k=2152k5kc b a \cdot 10^{k}=215 \cdot 2^{k} \cdot 5^{k} is exactly 9 (the factors of 2 in this last product are exactly kk). The maximum flower of a three-digit petaloso number is therefore 9.

c.
Suppose for contradiction that 13 divides the petaloso number abca b c. By what was proved in the previous point we see that 13 also divides cbac b a. Writing these numbers explicitly in terms of their base-10 representation we have abc=100a+10b+ca b c=100 a+10 b+c and cba=100c+10b+ac b a=100 c+10 b+a. If 13 divides both of these numbers, then it must divide their difference, which is 99(ca)99(c-a). Now observe that 13 is a prime number, so the product 99(ca)99(c-a) is divisible by 13 if and only if one of the two factors is. However 99 is not divisible by 13, as is easily checked by direct computation, and cac-a is not divisible by 13 since it is the difference of two distinct nonzero digits: indeed we have 0<ca80<|c-a| \leq 8, and hence certainly cac-a is not a multiple of 13. We have reached a contradiction, so the original assumption that 13 divided abca b c must have been false, which proves the claim.

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.