Maths Olympiad Prep

Library / /82 of 86

Number theory Difficulty 7.1 National olympiad, round 2 Prove it Estonia

(a) Is it true that, for arbitrary integer nn greater than 11 and distinct positive integers ii and jj not greater than nn, the set of any nn consecutive integers contains distinct numbers ii' and jj' whose product iji'j' is divisible by the product ijij?

(b) Is it true that, for arbitrary integer nn greater than 22 and distinct positive integers i,j,ki, j, k not greater than nn, the set of any nn consecutive integers contains distinct numbers i,j,ki', j', k' whose product ijki'j'k' is divisible by the product ijkijk?

Solution

Answer: (a) Yes; (b) No.

(a) Consider nn consecutive integers k+1,k+2,,k+nk+1, k+2, \dots, k+n. As ini \le n, there must be a multiple of ii among them; denote it ii'. As jnj \le n, there must also be a multiple xx of jj among them. If xix \ne i' then one may choose j=xj' = x; then the product iji'j' is divisible by the product ijij. Suppose in the rest that x=ix = i'; then ii' as a common multiple of ii and jj is divisible by lcm(i,j)\text{lcm}(i, j).
Note that if gcd(i,j)>n2\text{gcd}(i, j) > \frac{n}{2} then gcd(i,j)\text{gcd}(i, j) could not have two distinct multiples ii and jj among 1,2,,n1, 2, \dots, n. Thus gcd(i,j)n2\text{gcd}(i, j) \le \frac{n}{2}, which in turn implies that gcd(i,j)\text{gcd}(i, j) must have two distinct multiples among k+1,k+2,,k+nk+1, k+2, \dots, k+n. At least one of them differs from ii'; let that be jj'. Then the product iji'j' is divisible by the product lcm(i,j) gcd(i,j)\text{lcm}(i, j)\ \text{gcd}(i, j) which equals ijij.

(b) Let n=143n = 143 and i=77=711i = 77 = 7 \cdot 11, j=91=713j = 91 = 7 \cdot 13, and k=143=1113k = 143 = 11 \cdot 13; then ijk=72112132ijk = 7^2 \cdot 11^2 \cdot 13^2. We show that among 143143 consecutive integers p71,p70,,p+70,p+71p-71, p-70, \dots, p+70, p+71, where p=6006=2371113p = 6006 = 2 \cdot 3 \cdot 7 \cdot 11 \cdot 13, no three distinct numbers can have a product divisible by 721121327^2 \cdot 11^2 \cdot 13^2. For that, note that the largest number less than pp that is divisible by at least two numbers among 7,117, 11 and 1313 is p77p-77, and similarly, the least number greater than pp that is divisible by at least two numbers among 7,117, 11 and 1313 is p+77p+77. Both lie outside the region under consideration. Consequently, at most one prime among 7,117, 11 and 1313 can belong to the canonical representation of any of the numbers p71,p70,,p1,p+1,,p+70,p+71p-71, p-70, \dots, p-1, p+1, \dots, p+70, p+71. Now choose any three numbers among p71,p70,,p+70,p+71p-71, p-70, \dots, p+70, p+71.
* Let pp be among these three numbers. The primes 7,117, 11 and 1313 have exponent 11 in its canonical representation. As shown above, only one of these three primes can occur in the canonical representation of either of the other two chosen numbers. Thus the product of the chosen three numbers cannot be divisible by 721121327^2 \cdot 11^2 \cdot 13^2.
* Let all these three numbers differ from pp. As shown above, each of these numbers can be divisible by at most one prime among 7,117, 11 and 1313. Hence, for their product to be divisible by 721121327^2 \cdot 11^2 \cdot 13^2, one of the numbers should be divisible by 13213^2. But p13=6776(mod13)\frac{p}{13} = 6 \cdot 77 \equiv -6 \pmod{13} which implies p613(mod132)p \equiv -6 \cdot 13 \pmod{13^2}. Thus the nearest to pp numbers divisible by 13213^2 are p713p-7 \cdot 13 and p+613p+6 \cdot 13 which lie outside the region under consideration. Consequently, the product of the chosen three number cannot be divisible by 721121327^2 \cdot 11^2 \cdot 13^2.

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.