We know that the Pythagorean triples can be generated by the Euclid's formula $a=m^2-n^2$, $b=2mn$, $c=m^2+n^2$ for any positive integers $m,n$ and $m>n$.

I am trying to prove the statement:

The triple generated by Euclid's formula is primitive if and only if $m$ and $n$ are coprime and $m-n$ is odd.

I could prove the $\Rightarrow$ direction. Now I am trying to show the $\Leftarrow$ proof.

I am trying to prove by contradiction. If $m$ and $n$ are coprime and $m-n$ is odd, let's assume the triple generated is not primitive. Then there is a factor $k$ in each term. But since $m$ and $n$ are coprime and $m-n$ is odd, we can deduce that $(m^2-n^2)^2$ is odd, $(2mn)^2$ is even and $(m^2+n^2)^2$ is odd. Then $k$ can only be odd. Let $k=2p+1$ where $p$ is an integer. But then I am not sure how to proceed to obtain a contradiction.

Any helps are greatly appreciated. Many thanks!


Informal outline Suppose for example that $(m^2-n^2)^2$ and $(2mn)^2$ are not relatively prime. Then there is a prime $p$ that divides $m^2-n^2$ and $2mn$. Since $m$ and $n$ have opposite parity, $p\ne 2$.

Since $p$ divides $2mn$, and $p\ne 2$, it follows that $p$ divides one of $m$ or $n$, say $m$. Since $p$ divides $m^2-n^2$, it follows that $p$ divides $n^2$, and hence $n$. This contradicts the fact that $m$ and $n$ are relatively prime.

Remark: We started, as you did, from the assumption that the numbers $(m^2-n^2)^2$, $(2mn)^2$, and $(m^2+n^2)^2$ are not pairwise relatively prime. However, a triple $(x,y,z)$ such that $x^2+y^2=z^2$ is usually called primitive if $x$, $y$, and $z$ are pairwise relatively prime. It makes no real difference, since $x^2$, $y^2$, and $z^2$ are pairwise relatively prime if and only if $x$, $y$, and $z$ are.

  • $\begingroup$ In your remark, I believe you meant $(m^2-n^2)^2$. $\endgroup$ – Hayden May 20 '14 at 4:37
  • $\begingroup$ Thanks Andre. But just a question, according to mathworld.wolfram.com/PrimitivePythagoreanTriple.html, primitive triples are where gcd(a,b,c)=1 right? So they are not necessarily have to be pairwise coprime? For example gcd(2,4,5)=1, but they are not pairwise coprime. Which one is correct? Thanks. $\endgroup$ – user71346 May 20 '14 at 4:39
  • $\begingroup$ Thanks for spotting it. Yes, that is what was meant. $\endgroup$ – André Nicolas May 20 '14 at 4:40
  • 2
    $\begingroup$ @user71346: Both are correct, and equivalent. If they are pairwise relatively prime, then $\gcd(a,b,c)=1$. Conversely, if $\gcd(a,b,c)=1$, then they are pairwise relatively prime. Suppose for example to the contrary that $\gcd(a,b)\gt 1$. Then some prime $p$ divides $a$ and $b$. From $a^2+b^2=c^2$ we conclude that $p$ divides $c$, contradicting the fact $\gcd(a,b,c)=1$. In principle the $\gcd(a,b,c)=1$ is a bit better, since it is "weaker." However, the proof of equivalence is so simple that it really doesn't matter. $\endgroup$ – André Nicolas May 20 '14 at 4:45
  • $\begingroup$ If we start from weaker assumptions, we get an at least apparently stronger theorem, although in this case the two assumptions are so clearly equivalent that it makes no practical difference. I guess one can imagine a situation, in a domain that doesn't have unique factorization, where the exact assumptions could make a difference. $\endgroup$ – André Nicolas May 20 '14 at 4:59

Suppose $k | (m^2-n^2)$ and $k | (m^2+n^2)$, then $k | 2m^2$ and $k | 2n^2$. But then $k$ divides $\gcd(2m^2,2n^2)=2\gcd(m^2,n^2)=2$. The last step follows from the fact that $\gcd(m,n)=1$. Thus $k=1$ or $k=2$. Ask yourself why can't $k$ be $2$?

  • $\begingroup$ Yes, you are right, if k=2 then it is not primitive. Thanks. $\endgroup$ – user71346 May 20 '14 at 4:45

I thought I had a proof that, if $m,n$ are mutually prime, $m,n$ would generate only primitive Pythagorean triples. The $proof$ is between the asterisk below. $$\text{*************************}$$

$\text{We are given }\quad A=m^2n^2\quad B=2mn\quad C=m^2+n^2$

Let $x$ be the GCD of $m,n$ and let $p$ and $q$ be the cofactors of $m$ and $n$ respectively. Then we have

$$A=(xp)^2-(xq)^2\quad B=2xpxq\quad C=(xp)^2+(xq)^2$$ $$A=x^2(p^2-q^2)\quad B=2x^2(pq)\quad C=x^2(p^2+q^2)$$

If $GCD(m,n)=1$, then $GCD(A,B,C)=1$ and $(A,B,C)$ is a primitive triple. This means that $m$ and $n$ must be co-prime to generate a primitive.


However, a counter-example destroys to so-called proof: $\quad\text{Let }m,n=7,3$. $$A=49-9=40\quad B=2*7*3=42\quad C=49+9=58\quad GCD(40,42,58)=2$$ $$\therefore GCD(m,n)=1\neg\implies GCD(A,B,C)=1$$ I believe but do not know that the proof may be valid if we insist that $m$ and $n$ be of opposite parity.

The only two formulas I know about that will generate only primitive triplets do not generate all of them but $C-B=1$ in the first one and $C-A=2$ in the second one.

$$A=2n^2+1\quad B=2n^2+2n\quad C=2n^2+2n+1$$ $$A=4n^2-1\quad B=4n\quad C=4n^2+1$$

$\mathbf{UPDATE:}$ I did some looking and found a variation of Euclid's formula that can let us prove when we have found a primitive with more confidence.

$$\text{Let}\quad A=(2m-1+n)^2-n^2\quad B=2(2m-1+n)n\quad C=(2m-1+n)^2+n^2\quad m,n\in\mathbb{N}$$

This formula generates only and all triples where $GCD(A,B,C)=(2k-1)^2,k\in\mathbb{N}$ which includes all primitives.

If we let $GCD((2m-1),n)=x$ and $p,q$ be the respective cofactors, then we have $$A=(xp+xq)^2-(xq)^2\quad B=2(xp+xq)xq\quad C=(xp+xq)^2+(xq)^2$$ $$A=x^2(p+q)^2-x^2q^2\quad B=2x^2(p+q)q\quad C=x^2(p+q)^2+x^2q^2$$ We can see by inspection that if $(2m-1)$ and $n$ have common factors, then GCD(A,B,C) an odd square and, if GCD((2m-1),n)=1, the triple is primitive.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.