Maths Olympiad Prep

Library / /489 of 520

Algebra Difficulty 7.3 National olympiad, round 2 Prove it

Lemma 3 Let x1,x2,y1,y2x_{1}, x_{2}, y_{1}, y_{2} be any integers, then
(x12+y12)(x22+y22)=(x1x2+y1y2)2+(x1y2x2y1)2.\left(x_{1}^{2}+y_{1}^{2}\right)\left(x_{2}^{2}+y_{2}^{2}\right)=\left(x_{1} x_{2}+y_{1} y_{2}\right)^{2}+\left(x_{1} y_{2}-x_{2} y_{1}\right)^{2} .

Solution

Prove that expanding both sides immediately yields the proof.
(10) tells us that if m1,m2m_{1}, m_{2} are two positive integers, both of which can be expressed as the sum of two squares of integers, then m1,m2m_{1}, m_{2} must also be expressible as the sum of two squares of integers. Let nn be any given positive integer with the factorization
n=m2n1,μ(n1)0n=m^{2} n_{1}, \mu\left(n_{1}\right) \neq 0

Here μ\mu is the Möbius function, defined as
μ(r)={1, when r=1,(1), when r is the product of l distinct primes, 0, when r is divisible by the square of a prime. \mu(r)=\left\{\begin{array}{l} 1, \text { when } r=1, \\ (-1)^{\prime}, \text { when } r \text { is the product of } l \text { distinct primes, } \\ 0, \text { when } r \text { is divisible by the square of a prime. } \end{array}\right.

Thus (11) means that m2m^{2} is the largest square factor of n\boldsymbol{n}, and n1n_{1} no longer contains any square factors. Since m2=m2+o2m^{2}=m^{2}+o^{2} is clearly the sum of the squares of two integers mm and oo, by Lemma 3, as long as n1n_{1} can be expressed as the sum of two squares of integers, then n\boldsymbol{n} must also be expressible as the sum of two squares of integers. Since n1n_{1} has no square factors, there must be a factorization
n1=p1ps,s1,p1<<psn_{1}=p_{1} \cdots p_{s}, s \geqslant 1, p_{1}<\cdots<p_{s}

If each pi(1is)p_{i}(1 \leqslant i \leqslant s) is a prime of the form 4k+14 k+1, or the smallest p1=2=12+12p_{1}=2=1^{2}+1^{2}, then by Theorem 2 of the previous section, each pi(1is)p_{i}(1 \leqslant i \leqslant s) can be expressed as the sum of two positive squares of integers. Repeatedly applying Lemma 3 to these sums of squares, it is easy to see that nn must be the sum of two squares of integers.

Conversely, we naturally ask: if nn can be expressed as the sum of two squares of integers, must each prime factor in the factorization (13) of n1\boldsymbol{n}_{1} be a prime of the form 4k+14 k+1?

Assume some coefficient p11=4k+3,p0n1p_{11}=4 k+3, p_{0} \mid n_{1}, is an odd number. Let (x,y)=d(x, y)=d, then x=dx1,y=dy1,(x1,y1)=1, Jx=d x_{1}, y=d y_{1},\left(x_{1}, y_{1}\right)=1, \mathrm{~J}, so
n=d2(x12+y12)n=d^{2}\left(x_{1}^{2}+y_{1}^{2}\right)
If p0y1p_{0} \mid y_{1}, this contradicts (x1y1)=1\left(x_{1} \cdot y_{1}\right)=1, i.e.,
x12+y12=0(modp0),p0+x1y1.x_{1}^{2}+y_{1}^{2}=0\left(\bmod p_{0}\right), p_{0}+x_{1} y_{1}.

From p0+x1p_{0}+x_{1}, there must be some x2,p10+x2x_{2}, p_{10}+x_{2} such that
x1x21(modp0)x_{1} x_{2} \equiv 1\left(\bmod p_{0}\right)

Using (15) and (16), we get
0x22(x12+y12)=(x1x2)2+(x2y1)21+(x2y1)2(modp0)\begin{aligned} 0 & \equiv x_{2}^{2}\left(x_{1}^{2}+y_{1}^{2}\right)=\left(x_{1} x_{2}\right)^{2}+\left(x_{2} y_{1}\right)^{2} \\ & \equiv 1+\left(x_{2} y_{1}\right)^{2}\left(\bmod p_{0}\right) \end{aligned}

This indicates that -1 must be a quadratic residue of p0p_{0}, which contradicts p0=3(mod4)p_{0}=3(\bmod 4). In summary, we have proven the following conclusion.

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.