AlgebraDifficulty 7.3National olympiad, round 2Prove it
Lemma 3 Let x1,x2,y1,y2 be any integers, then (x12+y12)(x22+y22)=(x1x2+y1y2)2+(x1y2−x2y1)2.
Solution
Prove that expanding both sides immediately yields the proof. (10) tells us that if m1,m2 are two positive integers, both of which can be expressed as the sum of two squares of integers, then m1,m2 must also be expressible as the sum of two squares of integers. Let n be any given positive integer with the factorization n=m2n1,μ(n1)=0
Here μ 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.
Thus (11) means that m2 is the largest square factor of n, and n1 no longer contains any square factors. Since m2=m2+o2 is clearly the sum of the squares of two integers m and o, by Lemma 3, as long as n1 can be expressed as the sum of two squares of integers, then n must also be expressible as the sum of two squares of integers. Since n1 has no square factors, there must be a factorization n1=p1⋯ps,s⩾1,p1<⋯<ps
If each pi(1⩽i⩽s) is a prime of the form 4k+1, or the smallest p1=2=12+12, then by Theorem 2 of the previous section, each pi(1⩽i⩽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 n must be the sum of two squares of integers.
Conversely, we naturally ask: if n can be expressed as the sum of two squares of integers, must each prime factor in the factorization (13) of n1 be a prime of the form 4k+1?
Assume some coefficient p11=4k+3,p0∣n1, is an odd number. Let (x,y)=d, then x=dx1,y=dy1,(x1,y1)=1,J, so n=d2(x12+y12) If p0∣y1, this contradicts (x1⋅y1)=1, i.e., x12+y12=0(modp0),p0+x1y1.
From p0+x1, there must be some x2,p10+x2 such that x1x2≡1(modp0)
Using (15) and (16), we get 0≡x22(x12+y12)=(x1x2)2+(x2y1)2≡1+(x2y1)2(modp0)
This indicates that -1 must be a quadratic residue of p0, which contradicts p0=3(mod4). 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.