# Proof of Euclid's formula for primitive Pythagorean Triples

It says that a pythagorean triple consists of 3 positive integer's $$a, b, c$$ such that $$a^2 + b^2 = c^2$$.

Also if all the integers in a triple say $$a, b, c$$ are relatively prime then the triplet is called Primitive Pythagorean triplet.

the formula is as follows :

$$a = m^2 - n^2, b = 2mn, c = m^2 + n^2$$ where $$m > n > 0$$

for any 2 values of $$m$$ and $$n$$ the above formula will give a Pythagorean Triple.

To get a Primitive Pythagorean triple, $$m$$ and $$n$$ have to co-prime and not both odd.

I wanted to understand the proof of this formula.

I don't understand this part of the proof which is also given in the wiki page.

"As $${{\tfrac {m}{n}}}$$ is fully reduced, m and n are coprime, and they cannot both be even. If they were both odd, the numerator of $${\displaystyle {\tfrac {m^{2}-n^{2}}{2mn}}}$$ would be a multiple of 4 (because an odd square is congruent to 1 modulo 4), and the denominator 2mn would not be a multiple of 4. Since 4 would be the minimum possible even factor in the numerator and 2 would be the maximum possible even factor in the denominator, this would imply a to be even despite defining it as odd. Thus one of m and n is odd and the other is even, and the numerators of the two fractions with denominator 2mn are odd. Thus these fractions are fully reduced (an odd prime dividing this denominator divides one of m and n but not the other; thus it does not divide m2 ± n2). One may thus equate numerators with numerators and denominators with denominators, giving Euclid's formula"

The only thing I don't [understand] is the last part where it's given as "One may thus equate numerators with numerators and denominators with denominators, giving Euclid's formula"

It uses unique fractionization $$\Rightarrow$$ uniqueness of reduced fractions (with denominators $$> 0),\,$$ i.e.

\qquad\qquad \begin{align}\gcd(\color{#c00}{c,b})=1\\ \gcd(j,k)= 1\end{align}, \ \ \dfrac{c}b = \dfrac{j}k\ \Rightarrow\ \begin{align} c&\,=\,j\\ b &\,=\, k\end{align},\ \ \ {\rm for}\ \ b,c,j,k\in \Bbb Z,\ b,k > 0

Follow the link for a simple proof using Euclid's Lemma (hint: $$\,j = ck/b\,\Rightarrow\,\color{#c00}{b\mid c}\,k\,\Rightarrow\,b\mid k)$$

Remark  A more conceptual way to derive this parametrization of Pythagorean triples is to employ arithmetic of Gaussian integers $$\,\Bbb Z[i] = \{ a + b\,i\,: a,b\in\Bbb Z\}$$. Like integers they enjoy (Euclidean) division (with smaller remainder) and this implies they too satisfy the analog of the Fundamental Theorem of Arithmetic = existence and uniqueness of factorization into primes (= irreducibles). This implies that coprime factors of a square must themselves be squares (up to unit factors $$\,\pm1,\pm i)$$

Thus if $$\ z^2 = x^2 + y^2 = (x-y\,i) (x+ y\,i)$$ and $$\,x,y\,$$ are coprime then one easily checks that $$\,x-y\,i,\,x+y\,i\,$$ are coprime, so being coprime factors of the square $$\,z^2$$ they must themselves be squares (up to a unit factor). Thus e.g. $$\ x + y\ i\, =\, (m + n\ i)^2 =\ m^2 - n^2 + 2mn\, i,\,$$ hence $$\,x = m^2-n^2,\ y = 2mn\,$$ (using the unit factor $$1$$; using the other unit factors $$\, -1,\pm i\,$$ merely changes signs or swaps $$\,x,y\,$$ values). Notice how very simple the solution is from this perspective.

This is a simple prototypical (arithmetical) example of the simplification that results from the transformation of nonlinear problems into linear problems by working in larger algebraic extension rings. See here for some further discussion of such.

This argument could be formulated easier :

" We want to get a primitive pythagorean triple.If $$\ m\$$ and $$\ n\$$ are both odd, then $$\ a=m^2-n^2\$$ as well as $$\ c=m^2+n^2\$$ must be even , hence the triple cannot be primitive. "

Giving the fraction is not necessary and perhaps confusing. I assume , this is the only part which is unclear. If not, just ask what else is unclear.

• No need to involve modulo 4. The difference and the sum of two of numbers are both even. That's it. Jul 6, 2019 at 12:24
• @Arthur You are right, I will edit the question. Jul 6, 2019 at 12:39
• @Peter thanks for the reply. After reading the answer I understood that in triple $(a, b, c)$, $c$ cannot be even since it will lead to $a^2 + b^2$ not equal $c^2$. Also $m$ and $n$ if both odd will give $a$ and $c$ as even so not primitive. The only thing I don't is the last part where it's given as "One may thus equate numerators with numerators and denominators with denominators, giving Euclid's formula". Jul 6, 2019 at 12:51
• @RakendChauhan Be careful ! The argument that $a^2+b^2=c^2$ cannot hold, if $c$ is even, is not valid. Only in a primitive triple , $c$ cannot be even. Jul 6, 2019 at 12:56
• I admit, that I neither understand the statement "One may thus equate ... " . The important part however is that if $\ m\$ and $\ n\$ are coprime and not both odd, then euclid's formula gives a primitive triple. Jul 6, 2019 at 13:02

Simple algebra can show that $$(m^2-n^2)^2+(2mn)^2=(m^2+n^2)^2$$ but we can more easily prove things about primitives if we use a variant of Euclid's formula that generates only triples where $$GCD(A,B,C)$$ is an odd square (which includes all primitives). This variant also generate's non-primitives only when $$m,n$$ share a common factor. Having both odd or both even does not matter.

$$A=(2m-1+n)^2-n^2\quad B=2(2m-1+n)n\quad C=(2m-1+n)^2+n^2$$ Expanding terms presents this in a different way, here replacing $$m,n$$ with $$n,k$$. $$A=(2n-1)^2+2(2n-1)k,\space\space B=2(2n-1)k+2k^2,\space\space C=(2n-1)^2+2(2n-1)+2k^2$$ In this form it is easy to prove that when $$(2n-1),k$$ are coprime, that the triple is primitive. Let $$x$$ be the GCD of $$(2n-1),k$$ and let $$p,q$$ be their respective cofactors. Then then $$x$$ is odd because $$2n-1$$ is odd and we have

$$A=(xp)^2+2(xp)xq,\space\space B=2(xp)xq+2x^2q^2,\space\space C=(xp)^2+2(xp)xq+2x^2q^2$$

$$A=x^2(p^2+2pq),\qquad B=x^2(2pq+2q^2),\qquad C=x^2(p^2+2pq+2x^2q^2)$$

We can see that, if $$x^2=GCD((2n-1),k)=1, GCD(A,B,C)=1$$ and $$A,B,C$$ is primitive.

The definition of primitive Pythagorean triples(ppt)is well documented in the literature so I will not repeat it here. The sides of a ppt a,b,c, one leg a is odd. I call this the odd leg. The leg b even (even leg) and the hypotenuse odd.

For ppts the sum of the even leg and hypotenuse is the square of an odd number.

For example (3,4,5) 4+5=9 (3^2) (20, 21,29) 20+29=49(7^2). This is true for all ppts.

Now an odd number is the sum of an even number and an odd number(simple number theory.

So let the even number be,m, and the odd numbe ,n. Or vice versa. M>N

The (odd number)^2 is (m+n)^2 which gives m^2+ 2mn +n^2.

M^2+ N^2 is an odd number the hypotenuse and 2MN an even number is the even leg. An even number squared is an even number and an odd number squared is an odd number.

Once the formulas for the hypotenuse and even leg are identified we can find the formula for the odd leg by using the Pythagorean theorem to get M^2-N^2.

Note if you scale up the sides of a PPt by the square of an odd number you will also find that the sum of the even leg and the hypotenuse is an odd number squared. However the scaled up Pythagorean triplet is not a PPt since the three sides now have a GCD of the odd number squared.

You will also find that that the M is identified in the hypotenuse and the even leg you can get the odd leg, since the sum of the odd leg and the hypotenuse is 2M^2 Example (8 15 17) M=4,N=1 15+17=32 =2(4)^2 You can use this fact to find the formula for the odd leg

Hence Euclids formula for generating PPTS.

Did the Babylonians and Euclid use the fact that the sum of the even leg and the hypotenuse is an odd number squared to generate the formulas?

• are you asking a question? if so, you might want to start a new post. Jun 22, 2020 at 4:19