Maths Olympiad Prep

Library / /129 of 136

Number theory Difficulty 8.6 Shortlist Prove it Hong Kong

A positive integer nn is said to be good if there exist positive integers aa and bb such that a+b=na+b=n and abab is divisible by nn. For instance, 99 is good since 3+6=93+6=9 and 3×63 \times 6 is divisible by 99. Furthermore, nn is said to be very good if we can choose aa and bb to be distinct. Hence 99 is very good.

a. Given that 20032003 is a prime, show that 20032003 is not good.

b. Is 20022002 good?

c. Find all positive integers which are good but not very good. Justify your answers.

Solution

a. Suppose there exist a,bZ+a, b \in \mathbb{Z}^+ such that a+b=2003a+b = 2003 and 2003ab2003 \mid ab. Since 20032003 is a prime, we must have 2003a2003 \mid a or 2003b2003 \mid b. WLOG assume 2003a2003 \mid a. Then we have a+b2003+1>2003a+b \ge 2003+1 > 2003, which is a contradiction. Therefore, 20032003 is not good.

b. No. Suppose there exist a,bZ+a, b \in \mathbb{Z}^+ such that a+b=2002a+b = 2002 and 2002ab2002 \mid ab. Note that 2002=2×7×11×132002 = 2 \times 7 \times 11 \times 13. For each prime p2002p \mid 2002, we have pabp \mid ab, and so pap \mid a or pbp \mid b. In either case, since pa+bp \mid a+b, we must have pap \mid a and pbp \mid b. As this holds for p=2,7,11,13p = 2, 7, 11, 13, we must have 2002a,b2002 \mid a, b. This yields a+b2002+2002>2002a+b \ge 2002+2002 > 2002, which is a contradiction. Therefore, 20022002 is not good.

c. All positive integers of the form 4p1p2ps4p_1p_2\cdots p_s or 8p1p2ps8p_1p_2\cdots p_s where p1,p2,,psp_1, p_2, \dots, p_s are distinct odd primes (possibly s=0s=0) are good but not very good.

In view of the proof of part (b), all squarefree positive integers are not good. For any non-squarefree positive integer nn, we can write n=p2mn = p^2m for some prime pp and positive integer mm. Since we can take a=pma = pm and b=(p1)pmb = (p-1)pm such that
a+b=p2m=n a + b = p^2m = n
and
ab=(p1)p2m2=(p1)mn, ab = (p-1)p^2m^2 = (p-1)mn,
we know that nn is good by definition. Also, note that aa and bb are distinct unless p=2p=2. This shows nn is very good if nn is divisible by the square of an odd prime.

Thus, it remains to consider n=2kmn = 2^k m for some k2k \ge 2 and odd mm which is squarefree. If k4k \ge 4, we can take a=2k2ma = 2^{k-2}m and b=32k2mb = 3 \cdot 2^{k-2}m such that
a+b=2km=n a + b = 2^k m = n
and
ab=322k4m2=32k4mn. ab = 3 \cdot 2^{2k-4}m^2 = 3 \cdot 2^{k-4}mn.
Since aba \neq b, this shows nn is very good.

Lastly, if k=2,3k=2,3, we show that nn is not very good. Indeed, suppose a+b=na+b=n and nabn|ab. As in part (b), we deduce mam|a and mbm|b. Let a=mca=mc and b=mdb=md. Then we need c+d=2kc+d=2^k and 2kcd2^k|cd. It is routine to check that there is no solution except c=dc=d when k=2,3k=2,3 (note that there are only a few pairs of (c,d)(c,d) satisfying c+d=2kc+d=2^k). Therefore, nn is not very good.

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.