Maths Olympiad Prep

Library / /519 of 520

Number theory Difficulty 8.0 National olympiad, round 2 Prove it

Lemma 2 If 2s2 \nmid s, then
s3=a2+3b2,(a,b)=1s^{3}=a^{2}+3 b^{2}, \quad(a, b)=1

is satisfied if and only if there exist α,β\alpha, \beta, such that
s=α2+3β2,(α,3β)=1s=\alpha^{2}+3 \beta^{2}, \quad(\alpha, 3 \beta)=1

and
a=α39αβ2,b=3α2β3β3.a=\alpha^{3}-9 \alpha \beta^{2}, \quad b=3 \alpha^{2} \beta-3 \beta^{3} .

Solution

Proof of Sufficiency: Suppose equations (3) and (4) hold. To make the derivation clear, we use complex number operations of the form x+y3x + y \sqrt{-3}. From equation (3), we have
s=(α+3β)(α3β), s = (\alpha + \sqrt{-3} \beta)(\alpha - \sqrt{-3} \beta),
thus
s3=(α+3β)3(α3β)3={(α39αβ2)+3(3α2β3β3)}×{(α39αβ2)3(3α2β3β3)}=(α39αβ2)2+3(3α2β3β3)2. \begin{aligned} s^{3} &= (\alpha + \sqrt{-3} \beta)^{3}(\alpha - \sqrt{-3} \beta)^{3} \\ &= \left\{\left(\alpha^{3} - 9 \alpha \beta^{2}\right) + \sqrt{-3}\left(3 \alpha^{2} \beta - 3 \beta^{3}\right)\right\} \\ & \quad \times \left\{\left(\alpha^{3} - 9 \alpha \beta^{2}\right) - \sqrt{-3}\left(3 \alpha^{2} \beta - 3 \beta^{3}\right)\right\} \\ &= \left(\alpha^{3} - 9 \alpha \beta^{2}\right)^{2} + 3\left(3 \alpha^{2} \beta - 3 \beta^{3}\right)^{2}. \end{aligned}

From this and equation (4), we can deduce that s3=a2+3b2s^{3} = a^{2} + 3 b^{2}. Given (α,3β)=1(\alpha, 3 \beta) = 1 (note: 2s2 \nmid s, 2α±β2 \nmid \alpha \pm \beta),
(a,b)=(α29β2,α2β2)=(8β2,α2β2)=(β2,α2β2)=1. \begin{aligned} (a, b) &= \left(\alpha^{2} - 9 \beta^{2}, \alpha^{2} - \beta^{2}\right) = \left(8 \beta^{2}, \alpha^{2} - \beta^{2}\right) \\ &= \left(\beta^{2}, \alpha^{2} - \beta^{2}\right) = 1. \end{aligned}

This proves that equation (2) holds.

Proof of Necessity: Suppose equation (2) holds. In this case, 3s3 \nmid s, so any prime factor pp of ss must satisfy
p>3,(p,ab)=1. p > 3, \quad (p, ab) = 1.

This implies (why) that
(3p)=1. \left(\frac{-3}{p}\right) = 1.

Let Ω(s)\Omega(s) denote the number of prime factors of ss (counting multiplicities), and define Ω(1)=0\Omega(1) = 0. For example, Ω(6)=2\Omega(6) = 2, Ω(4)=2\Omega(4) = 2. We use induction on Ω(s)\Omega(s) to prove the necessity. When Ω(s)=0\Omega(s) = 0, i.e., s=1s = 1, we have a=±1a = \pm 1, b=0b = 0. In this case, we can take α=±1\alpha = \pm 1, β=0\beta = 0. Therefore, the necessity holds. Assume the necessity holds for Ω(s)=n(0)\Omega(s) = n (\geqslant 0). When Ω(s)=n+1\Omega(s) = n + 1, let s=pts = p t, where pp is a prime and Ω(t)=n\Omega(t) = n. Since pp satisfies equation (6), by Theorem 4 in §2\S 2,
p=α12+3β12 p = \alpha_{1}^{2} + 3 \beta_{1}^{2}
and clearly,
(α1,3β1)=1. (\alpha_{1}, 3 \beta_{1}) = 1.

From the proof of sufficiency, we have
p3=c2+3d2,(c,d)=1c=α139α1β12,d=3α12β13β13. \begin{array}{c} p^{3} = c^{2} + 3 d^{2}, \quad (c, d) = 1 \\ c = \alpha_{1}^{3} - 9 \alpha_{1} \beta_{1}^{2}, \quad d = 3 \alpha_{1}^{2} \beta_{1} - 3 \beta_{1}^{3}. \end{array}

From this and equation (2), we get
p6t3=p3s3=(c2+3d2)(a2+3b2)={(c+3d)(a3b)(c3d)(a+3b)(c+3d)(a+3b)(c3d)(a3b)={(ac+3bd)2+3(adbc)2,(ac3bd)2+3(ad+bc)2. \begin{aligned} p^{6} t^{3} &= p^{3} s^{3} = \left(c^{2} + 3 d^{2}\right)\left(a^{2} + 3 b^{2}\right) \\ &= \left\{\begin{array}{l} (c + \sqrt{-3} d)(a - \sqrt{-3} b)(c - \sqrt{-3} d)(a + \sqrt{-3} b) \\ (c + \sqrt{-3} d)(a + \sqrt{-3} b)(c - \sqrt{-3} d)(a - \sqrt{-3} b) \end{array}\right. \\ &= \left\{\begin{array}{l} (a c + 3 b d)^{2} + 3(a d - b c)^{2}, \\ (a c - 3 b d)^{2} + 3(a d + b c)^{2}. \end{array}\right. \end{aligned}

We now prove that among adbca d - b c and ad+bca d + b c, exactly one is divisible by pp. Using equations (2), (9), and s=pts = p t,
(adbc)(ad+bc)=(a2+3b2)d2(c2+3d2)b2=s3d2p3b2=p3(t3d2b2). \begin{aligned} (a d - b c)(a d + b c) &= \left(a^{2} + 3 b^{2}\right) d^{2} - \left(c^{2} + 3 d^{2}\right) b^{2} \\ &= s^{3} d^{2} - p^{3} b^{2} = p^{3}\left(t^{3} d^{2} - b^{2}\right). \end{aligned}

Thus, pp divides at least one of these numbers. However, if p(adbc,ad+bc)p \mid (a d - b c, a d + b c), then p(ad,bc)p \mid (a d, b c) (since p>3p > 3). By equation (9), pcdp \nmid c d, so p(a,b)p \mid (a, b), which contradicts (a,b)=1(a, b) = 1. This proves the desired result, and by equation (12), the number divisible by pp must be divisible by p3p^{3}. Assume p3adbcp^{3} \mid a d - b c (the case p3ad+bcp^{3} \mid a d + b c can be treated similarly). From equation (11),
t3=u2+3v2u=(ac+3bd)/p3,v=(adbc)/p3. \begin{array}{c} t^{3} = u^{2} + 3 v^{2} \\ u = (a c + 3 b d) / p^{3}, \quad v = (a d - b c) / p^{3}. \end{array}

We now prove that
(u,v)=1. (u, v) = 1.

From equations (9) and (14),
ac+3bd=u(c2+3d2)adbc=v(c2+3d2). \begin{array}{c} a c + 3 b d = u\left(c^{2} + 3 d^{2}\right) \\ a d - b c = v\left(c^{2} + 3 d^{2}\right). \end{array}

This implies (eliminating bb and aa),
a=uc+3vd,b=udvc. a = u c + 3 v d, \quad b = u d - v c.

From these two equations and (a,b)=1(a, b) = 1, we conclude that equation (15) holds.
Thus, we have Ω(t)=n\Omega(t) = n and equations (13) and (15) hold, so by the induction hypothesis, there exist α2,β2\alpha_{2}, \beta_{2} such that
t=α22+3β22,(α2,3β2)=1 t = \alpha_{2}^{2} + 3 \beta_{2}^{2}, \quad (\alpha_{2}, 3 \beta_{2}) = 1
and
u=α239α2β22,v=3α22β23β23. u = \alpha_{2}^{3} - 9 \alpha_{2} \beta_{2}^{2}, \quad v = 3 \alpha_{2}^{2} \beta_{2} - 3 \beta_{2}^{3}.

From equations (7) and (17), we get (similar to equation (11))
s=pt=(α12+3β12)(α22+3β22)=α2+3β2, s = p t = \left(\alpha_{1}^{2} + 3 \beta_{1}^{2}\right)\left(\alpha_{2}^{2} + 3 \beta_{2}^{2}\right) = \alpha^{2} + 3 \beta^{2},
where
α=α1α2+3β1β2,β=α2β1β2α1. \alpha = \alpha_{1} \alpha_{2} + 3 \beta_{1} \beta_{2}, \quad \beta = \alpha_{2} \beta_{1} - \beta_{2} \alpha_{1}.

To prove that the necessity holds when Ω(s)=n+1\Omega(s) = n + 1, we need to show that for the chosen α,β\alpha, \beta, equation (4) holds and (α,3β)=1(\alpha, 3 \beta) = 1. For clarity, we use complex number operations. Equation (16) can be written as
a+3b=(c+3d)(u3v). a + \sqrt{-3} b = (c + \sqrt{-3} d)(u - \sqrt{-3} v).

Equation (10) can be written as
c+3d=(α1+3β1)3. c + \sqrt{-3} d = \left(\alpha_{1} + \sqrt{-3} \beta_{1}\right)^{3}.

Equation (18) can be written as
u3v=(α23β2)3. u - \sqrt{-3} v = \left(\alpha_{2} - \sqrt{-3} \beta_{2}\right)^{3}.

From these three equations and equation (20), we get
a+3b={(α1α2+3β1β2)+3(α2β1β2α1)}3=(α+3β)3. \begin{aligned} a + \sqrt{-3} b &= \left\{\left(\alpha_{1} \alpha_{2} + 3 \beta_{1} \beta_{2}\right) + \sqrt{-3}\left(\alpha_{2} \beta_{1} - \beta_{2} \alpha_{1}\right)\right\}^{3} \\ &= (\alpha + \sqrt{-3} \beta)^{3}. \end{aligned}

Comparing the real and imaginary parts of the above equation, we deduce that equation (4) holds. From equation (2), we have (a,3b)=1(a, 3 b) = 1, and from equation (4), we get (α,3β)=1(\alpha, 3 \beta) = 1. Proof complete.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.