Number theoryDifficulty 8.0National olympiad, round 2Prove it
Lemma 2 If 2∤s, then s3=a2+3b2,(a,b)=1
is satisfied if and only if there exist α,β, such that s=α2+3β2,(α,3β)=1
and a=α3−9αβ2,b=3α2β−3β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+y−3. From equation (3), we have s=(α+−3β)(α−−3β), thus s3=(α+−3β)3(α−−3β)3={(α3−9αβ2)+−3(3α2β−3β3)}×{(α3−9αβ2)−−3(3α2β−3β3)}=(α3−9αβ2)2+3(3α2β−3β3)2.
From this and equation (4), we can deduce that s3=a2+3b2. Given (α,3β)=1 (note: 2∤s, 2∤α±β), (a,b)=(α2−9β2,α2−β2)=(8β2,α2−β2)=(β2,α2−β2)=1.
This proves that equation (2) holds.
Proof of Necessity: Suppose equation (2) holds. In this case, 3∤s, so any prime factor p of s must satisfy p>3,(p,ab)=1.
This implies (why) that (p−3)=1.
Let Ω(s) denote the number of prime factors of s (counting multiplicities), and define Ω(1)=0. For example, Ω(6)=2, Ω(4)=2. We use induction on Ω(s) to prove the necessity. When Ω(s)=0, i.e., s=1, we have a=±1, b=0. In this case, we can take α=±1, β=0. Therefore, the necessity holds. Assume the necessity holds for Ω(s)=n(⩾0). When Ω(s)=n+1, let s=pt, where p is a prime and Ω(t)=n. Since p satisfies equation (6), by Theorem 4 in §2, p=α12+3β12 and clearly, (α1,3β1)=1.
From the proof of sufficiency, we have p3=c2+3d2,(c,d)=1c=α13−9α1β12,d=3α12β1−3β13.
From this and equation (2), we get p6t3=p3s3=(c2+3d2)(a2+3b2)={(c+−3d)(a−−3b)(c−−3d)(a+−3b)(c+−3d)(a+−3b)(c−−3d)(a−−3b)={(ac+3bd)2+3(ad−bc)2,(ac−3bd)2+3(ad+bc)2.
We now prove that among ad−bc and ad+bc, exactly one is divisible by p. Using equations (2), (9), and s=pt, (ad−bc)(ad+bc)=(a2+3b2)d2−(c2+3d2)b2=s3d2−p3b2=p3(t3d2−b2).
Thus, p divides at least one of these numbers. However, if p∣(ad−bc,ad+bc), then p∣(ad,bc) (since p>3). By equation (9), p∤cd, so p∣(a,b), which contradicts (a,b)=1. This proves the desired result, and by equation (12), the number divisible by p must be divisible by p3. Assume p3∣ad−bc (the case p3∣ad+bc can be treated similarly). From equation (11), t3=u2+3v2u=(ac+3bd)/p3,v=(ad−bc)/p3.
We now prove that (u,v)=1.
From equations (9) and (14), ac+3bd=u(c2+3d2)ad−bc=v(c2+3d2).
This implies (eliminating b and a), a=uc+3vd,b=ud−vc.
From these two equations and (a,b)=1, we conclude that equation (15) holds. Thus, we have Ω(t)=n and equations (13) and (15) hold, so by the induction hypothesis, there exist α2,β2 such that t=α22+3β22,(α2,3β2)=1 and u=α23−9α2β22,v=3α22β2−3β23.
From equations (7) and (17), we get (similar to equation (11)) s=pt=(α12+3β12)(α22+3β22)=α2+3β2, where α=α1α2+3β1β2,β=α2β1−β2α1.
To prove that the necessity holds when Ω(s)=n+1, we need to show that for the chosen α,β, equation (4) holds and (α,3β)=1. For clarity, we use complex number operations. Equation (16) can be written as a+−3b=(c+−3d)(u−−3v).
Equation (10) can be written as c+−3d=(α1+−3β1)3.
Equation (18) can be written as u−−3v=(α2−−3β2)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.
Comparing the real and imaginary parts of the above equation, we deduce that equation (4) holds. From equation (2), we have (a,3b)=1, and from equation (4), we get (α,3β)=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.