Maths Olympiad Prep

Library / /2 of 17

Number theory Difficulty 5.9 AIME, harder Prove it Balkan Mathematical Olympiad

Let aa, bb and cc be positive integers satisfying the equation (a,b)+[a,b]=2021c(a, b) + [a, b] = 2021^c. If ab|a - b| is a prime number, prove that the number (a+b)2+4(a + b)^2 + 4 is composite.

Solution

We write p=abp = |a - b| and assume for contradiction that q=(a+b)2+4q = (a + b)^2 + 4 is a prime number.
Since (a,b)[a,b](a, b) \mid [a, b], we have that (a,b)2021c(a, b) \mid 2021^c. As (a,b)(a, b) also divides p=abp = |a - b|, it follows that (a,b){1,43,47}(a, b) \in \{1, 43, 47\}. We will consider all 3 cases separately:

(1) If (a,b)=1(a, b) = 1, then 1+ab=2021c1 + ab = 2021^c, and therefore
q=(a+b)2+4=(ab)2+4(1+ab)=p2+42021c.(1) q = (a + b)^2 + 4 = (a - b)^2 + 4(1 + ab) = p^2 + 4 \cdot 2021^c. \quad (1)

a. Suppose cc is even. Since q1(mod4)q \equiv 1 \pmod 4, it can be represented uniquely (up to order) as a sum of two (non-negative) squares. But (1) gives potentially two such representations so in order to have uniqueness we must have p=2p = 2. But then 4q4|q a contradiction.

b. If cc is odd then ab=2021c11(mod3)ab = 2021^c - 1 \equiv 1 \pmod 3. Thus ab(mod3)a \equiv b \pmod 3 implying that p=ab0(mod3)p = |a - b| \equiv 0 \pmod 3. Therefore p=3p = 3. Without loss of generality b=a+3b = a + 3. Then 2021c=ab+1=a2+3a+12021^c = ab + 1 = a^2 + 3a + 1 and so
(2a+3)2=4a2+12a+9=42021c+5. (2a + 3)^2 = 4a^2 + 12a + 9 = 4 \cdot 2021^c + 5.
So 5 is a quadratic residue modulo 47, a contradiction as
(547)=(475)=(25)=1. \left(\frac{5}{47}\right) = \left(\frac{47}{5}\right) = \left(\frac{2}{5}\right) = -1.

(2) If (a,b)=43(a, b) = 43, then p=ab=43p = |a - b| = 43 and we may assume that a=43ka = 43k and b=43(k+1)b = 43(k + 1), for some kNk \in \mathbb{N}. Then 2021c=43+43k(k+1)2021^c = 43 + 43k(k + 1) giving that
(2k+1)2=4k2+4k+43=443c1473. (2k + 1)^2 = 4k^2 + 4k + 4 - 3 = 4 \cdot 43^{c-1} \cdot 47 - 3.
So 3-3 is a quadratic residue modulo 47, a contradiction as
(347)=(147)(347)=(473)=(23)=1. \left(\frac{-3}{47}\right) = \left(\frac{-1}{47}\right) \left(\frac{3}{47}\right) = \left(\frac{47}{3}\right) = \left(\frac{2}{3}\right) = -1.

(3) If (a,b)=47(a, b) = 47 then analogously there is a kNk \in \mathbb{N} such that
(2k+1)2=443c47c13. (2k + 1)^2 = 4 \cdot 43^c \cdot 47^{c-1} - 3.
If c>1c > 1 then we get a contradiction in exactly the same way as in (2). If c=1c = 1 then (2k+1)2=169(2k + 1)^2 = 169 giving k=6k = 6. This implies that a+b=476+477=47131(mod5)a + b = 47 \cdot 6 + 47 \cdot 7 = 47 \cdot 13 \equiv 1 \pmod 5. Thus q=(a+b)2+40(mod5)q = (a + b)^2 + 4 \equiv 0 \pmod 5, a contradiction.

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.