Maths Olympiad Prep

Library / Balkan Mathematical Olympiad competition problems /2 of 16

Balkan Mathematical Olympiad competition problems

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 ∣a−b∣|a - b| is a prime number, prove that the number (a+b)2+4(a + b)^2 + 4 is composite.

Solution

We write p=∣a−b∣p = |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=∣a−b∣p = |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=(a−b)2+4(1+ab)=p2+4⋅2021c.(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 q≡1(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 4∣q4|q a contradiction.

b. If cc is odd then ab=2021c−1≡1(mod3)ab = 2021^c - 1 \equiv 1 \pmod 3. Thus a≡b(mod3)a \equiv b \pmod 3 implying that p=∣a−b∣≡0(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=4⋅2021c+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=∣a−b∣=43p = |a - b| = 43 and we may assume that a=43ka = 43k and b=43(k+1)b = 43(k + 1), for some k∈Nk \in \mathbb{N}. Then 2021c=43+43k(k+1)2021^c = 43 + 43k(k + 1) giving that
(2k+1)2=4k2+4k+4−3=4⋅43c−1⋅47−3. (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 k∈Nk \in \mathbb{N} such that
(2k+1)2=4⋅43c⋅47c−1−3. (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=47⋅6+47⋅7=47⋅13≡1(mod5)a + b = 47 \cdot 6 + 47 \cdot 7 = 47 \cdot 13 \equiv 1 \pmod 5. Thus q=(a+b)2+4≡0(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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.