Maths Olympiad Prep

Library / /8 of 70

Number theory Difficulty 7.6 National Olympiad, round 2 Prove it Romania

A Pythagorean triple is a solution of the equation x2+y2=z2x^2 + y^2 = z^2 in positive integers such that x<yx < y. Given any non-negative integer nn, show that some positive integer appears in precisely nn distinct Pythagorean triples.
AMM Magazine

Solutions — 2

Solution 1

We show by induction on n0n \ge 0, that 2n+12^{n+1} appears in precisely nn distinct Pythagorean triples. Since no Pythagorean triple contains 22, the assertion holds for n=0n=0.

For the induction step, let n1n \ge 1, and assume that 2n2^n appears in exactly n1n-1 distinct Pythagorean triples. The latter produce n1n-1 distinct non-primitive Pythagorean triples each containing 2n+12^{n+1}. To conclude the proof, we show that 2n+12^{n+1} appears exactly once in a primitive Pythagorean triple. Recall that the primitive Pythagorean triples are described by the well-known formulae x=v2u2x = v^2 - u^2, y=2uvy = 2uv, z=u2+v2z = u^2 + v^2, where uu and vv are coprime positive integers, not both odd, and u<vu < v. Since xx and zz are both odd, if 2n+12^{n+1} appears in the triple, then 2n+1=y=2uv2^{n+1} = y = 2uv, and since u<vu < v and uu and vv have opposite parity, necessarily u=1u=1 and v=2nv = 2^n. Consequently, 2n+12^{n+1} appears in exactly nn distinct Pythagorean triples.

Solution 2

Alternative solution 1:
If P(m)P(m) is the number of Pythagorean triples containing the positive integer mm, and if P0(m)P_0(m) is the number of primitive such triples, then P(m)=dmP0(d)P(m) = \sum_{d|m} P_0(d). Since P0(1)=P0(2)=0P_0(1) = P_0(2) = 0 and P0(2k)=1P_0(2^k) = 1, k2k \ge 2 (as in the previous solution), it follows that P(2n+1)=nP(2^{n+1}) = n, so 2n+12^{n+1} appears in exactly nn distinct Pythagorean triples.

Alternative solution 2:
We show that if pp is a prime congruent to 33 modulo 44, then pnp^n appears in exactly nn Pythagorean triples, and is moreover always the smallest entry of any such.
Since pp is congruent to 33 modulo 44, 1-1 is a quadratic non-residue modulo pp, so no power of pp can be the largest entry of a Pythagorean triple. Hence, if pnp^n is a member of a Pythagorean triple, then p2n=b2a2p^{2n} = b^2 - a^2 for some positive integers a<ba < b, so ba=pkb - a = p^k and b+a=p2nkb + a = p^{2n-k} for some non-negative integer k<nk < n. Clearly, every such kk corresponds to a solution and there are precisely nn distinct Pythagorean triples containing pnp^n, namely,
pn,pk(p2(nk)1)/2,pk(p2(nk)+1)/2,k=0,1,,n1. p^n, \quad p^k(p^{2(n-k)} - 1)/2, \quad p^k(p^{2(n-k)} + 1)/2, \quad k = 0, 1, \dots, n-1.
It is worth noticing that this argument avoids appealing to the parametric representation of Pythagorean triples.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.