20161218, 13:46  #1 
Dec 2012
The Netherlands
2·7·131 Posts 
Basic Number Theory 13: Pythagorean triples and a few Diophantine equations
If a rightangled triangle has sides of length \(a,b\) and \(c\) (where \(c\) is the length of the longest side) then we know from the theorem of Pythagoras that \(a^2+b^2=c^2\).
For example, if \(a=1\) and \(b=1\) then \(c=\sqrt{2}\). If \(a,b,c\) are all positive integers with \(a^2+b^2=c^2\), then we call them a Pythagorean triple. For example, \((3,4,5)\) is a Pythagorean triple since \(3^2+4^2=5^2\). For every positive integer \(n\), it follows that \((3n,4n,5n)\) is also a Pythagorean triple, but these are all just scalings of the same triangle, so they do not give us anything new. We therefore prefer to focus on primitive Pythagorean triples, i.e. Pythagorean triples \((a,b,c)\) where \(a,b\) and \(c\) have no prime factors in common. If a prime number divides any two of \(a,b,c\) then it divides all three of them (since \(a^2+b^2=c^2\)), so this is equivalent to requiring that \(\gcd(a,b)=1\). Our first goal this time is to find all primitive Pythagorean triples. Proposition 65 Let \(r,s\) be coprime integers, exactly one of which is odd. Define \(a=r^2s^2\), \(b=2rs\) and \(c=\pm(r^2+s^2)\). Then \(a^2+b^2=c^2\) and \(\gcd(a,b)=1\). proof By direct calculation, \[ a^2+b^2=r^42r^2s^2+s^4+4r^2s^2=r^4+2r^2s^2+s^4=(r^2+s^2)^2=c^2. \] Take any prime number \(p\) and suppose \(pa\) and \(pb\). Then \(pa^2+b^2=c^2\) and \(p\) is prime so \(pc\) (and \(pc\) too). Thus \(p\) divides both \(r^2s^2\) and \(r^2+s^2\) so it also divides their sum \(2r^2\) and their difference \(2s^2\). If \(p\) does not divide 2 then (as \(p\) is prime) it divides \(r\) and similarly it divides \(s\). But \(r,s\) are coprime, so \(p\) does divide 2 and (again since \(p\) is prime) it follows that \(p=2\). But exactly one of \(r,s\) is odd, so exactly one of \(r^2,s^2\) is odd, and hence \(c\) is odd, so \(p\) does not divide \(c\), a CONTRADICTION. Thus there is no such prime number \(p\), and \(\gcd(a,b)=1\). ∎ We now have a way of generating an unlimited supply of primitive Pythagorean triples. What's more, they are all obtainable in this way, and we can prove it using what we have learned about the Gaussian integers. Proposition 66 Let \(a,b,c\) be integers with \(\gcd(a,b)=1\) such that \(a^2+b^2=c^2\). Then there exist coprime integers \(r,s\), exactly one of which is odd, such that (after swapping \(a\) and \(b\) if necessary) \(a=r^2s^2\), \(b=2rs\) and \(c=\pm(r^2+s^2)\). proof In the integers modulo 4, we have \(\bar{0}^2=\bar{2}^2=\bar{0}\) and \(\bar{1}^2=\bar{3}^2=\bar{1}\), so \(a\) and \(b\) cannot both be odd (that would give \(\bar{a}^2+\bar{b}^2=\bar{2}\), so \(\bar{c}^2=\bar{2}\), which is impossible). But \(a\) and \(b\) are coprime so they are not both even either. Thus exactly one of \(a,b\) is odd and we may swap them if necessary so that \(a\) is odd and \(b\) is even. It also follows that \(c\) is odd. In the Gaussian integers, we have \((a+bi)(abi)=c^2\). Take any Gaussian integer \(z=x+yi\) such that \(za+bi\) and \(zabi\). Then \(z\) divides their sum \(2a\) and their difference \(2bi\), and \(i\) is a unit so \(z2b\). As \(\gcd(a,b)=1\), it follows that \(z2\) so, by proposition 48(iii), \(N(z)N(2)\) i.e. \(x^2+y^24\). Thus \[ (x,y)\in\{(0,\pm 1),(0,\pm 2),(\pm 1,0),(\pm 2,0),(\pm 1,\pm 1)\}. \] If \((x,y)=(2,0)\) then \(2a+bi\) and \(2abi\) so \(4(a+bi)(abi)=c^2\), which is impossible as \(c\) is odd. Similarly, \((x,y)\) cannot be \((2,0)\) or \((0,\pm 2)\). And if \((x,y)=(1,1)\) then \(1+ia+bi\) and \(1+iabi\) (and \(i\) is a unit) so \(2=i(1+i)^2(a+bi)(abi)=c^2\), also impossible as \(c\) is odd. Thus \((x,y)\in\{(0,\pm 1),(\pm 1,0)\}\) i.e. \(z\) is a unit. We therefore have \((a+bi)(abi)=c^2\) but no prime Gaussian integer divides both \(a+bi\) and \(abi\), so (considering the prime factorization of \(c^2\)) it follows that \(a+bi=u(r+si)^2\) for some unit \(u\) and some integers \(r,s\). Moreover, if \(u=i\) then the real part of \(u(r+si)^2\) is \(2rs\), which is impossible as \(a\) is odd, and similarly for \(u=i\), so \(u\) is also a square and we can choose \(r,s\) so that \(u=1\). Thus \((r^2s^2)+2rsi=a+bi\) so \(a=r^2s^2\), \(b=2rs\) and \(c^2=a^2+b^2=(r^2+s^2)^2\) so \(c=\pm(r^2+s^2)\). Exactly one of \(r,s\) is odd since \(c=r^2+s^2\) is odd. And, for any prime number \(p\), if \(pr\) and \(ps\) then \(pa\) and \(pb\), which is impossible (since \(a,b\) are coprime) so \(r,s\) are coprime too. ∎ Finding solutions in the integers (or the rational numbers) to polynomial equations is, in general, very difficult. (Fermat's Last Theorem was one special case of this general problem!) This is often referred to as solving Diophantine equations. It is now known that there is no algorithm for finding solutions in general (look up Hilbert's Tenth Problem). We can use what we have learned so far to tackle specific examples, however. Example Consider the equation \(3x^2+2=y^2\). If \(x,y\) are integers satisfying this equation then, in the integers modulo 3, we have \(\bar{y}^2=\bar{2}\). But \(\bar{0}^2=\bar{0}\) and \(\bar{1}^2=\bar{2}^2=\bar{1}\), so no such \(y\) exists. Thus there are no integer solutions to this equation. Example Consider the equation \(x^2+1=y^3\). Suppose \(x,y\) are integers satisfying this equation. If \(x\) is odd then, in the integers modulo 4, \(\bar{x}^2=\bar{1}\) so \(\bar{y}^3=\bar{x}^2+\bar{1}=\bar{2}\) but \(\bar{2}\) is not a cube (\(\bar{0}^3=\bar{0}\), \(\bar{1}^3=\bar{1}\), \(\bar{2}^3=\bar{0}\) and \(\bar{3}^3=\bar{3}\)) so that is impossible. Thus \(x\) is even and therefore \(y\) is odd. Let \(t\) be the integer for which \(x=2t\). In the Gaussian integers, we have \((x+i)(xi)=y^3\). For any Gaussiain integer \(z\), if \(zx+i\) and \(zxi\) then \(z\) divides their difference \(2i\) and \(i\) is a unit so \(z2\). Thus \(z\) divides \(x+i\) and it also divides \(2t=x\) so \(zi\), i.e. \(z\) is a unit. So no prime Gaussian integer divides both \(x+i\) and \(xi\). Considering the prime factorization of \(y^3\), we therefore have \(x+i=u(c+di)^3\) for some unit \(u\) and integers \(c,d\). Moreover, every unit is a cube in the Gaussian integers, so we can choose \(c,d\) so that \(u=1\). Now \((c+di)^3=c(c^23d^2)+d(3c^2d^2)i\) so \(x=c(c^23d^2)\) and \(1=d(3c^2d^2)\). Thus \(d1\) (in \(\mathbb{Z}\)) so \(d=\pm 1\) and therefore \(d^2=1\). And \(3c^2d^2=3c^21\) divides 1 as well, so \(3c^2\) is either 0 or 2. As \(c\) is an integer, it follows that \(c=0\), and therefore \(d^3=1\) so \(d=1\). Hence \(x=c(c^23d^2)=0\) and \(y^3=x^2+1=1\) so \(y=1\). Conclusion: the only candidate for a solution is \(x=0\) with \(y=1\), and \(0^2+1=1^3\) so this is the unique solution. Exercises 59. Let \((a,b,c)\) be a Pythagorean triple. Show that the 3 positive integers are all distinct. 60. If there exists a triangle whose sides have lengths \(a,b\) and \(c\) then, by proposition 45(iii), \(a\leq b+c\), \(b\leq c+a\) and \(c\leq a+b\). Show the converse, i.e. for all nonnegative real numbers \(a,b,c\), if \(a\leq b+c\), \(b\leq c+a\) and \(c\leq a+b\) then there exists a triangle (in the Euclidean plane) whose sides have lengths \(a,b\) and \(c\). 61. Find all pairs of integers \((x,y)\) for which \(x^2+4=y^3\) (hint: consider the cases \(x\) is even and \(x\) is odd separately). 62. Prove that there are infinitely many prime numbers \(p\) such that \(p\equiv 1\pmod{4}\). Last fiddled with by Nick on 20161218 at 14:47 Reason: Typo in 2nd example (as pointed out by LaurV below) 
20161218, 14:39  #2 
Romulan Interpreter
"name field"
Jun 2011
Thailand
2^{4}·643 Posts 
In integers modulo 4, 3^3=3 (mod 4), not 1. (example 2). "so x is even, therefore y is
The rest seems fine. You have a patience of steel to write all this, for which you have all my admiration! Last fiddled with by LaurV on 20161218 at 14:55 
20161218, 14:49  #3 
Dec 2012
The Netherlands
2·7·131 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Basic Number Theory 1 & 2  Nick  Number Theory Discussion Group  17  20171223 20:10 
Final Lucas Lehmer residuals and Pythagorean triples  a nicol  Miscellaneous Math  21  20171219 11:34 
Basic Number Theory 18: quadratic equations modulo n  Nick  Number Theory Discussion Group  4  20170327 06:01 
Pythagorean triples  Rokas  Math  3  20050102 03:50 
Pythagorean Triples  jinydu  Puzzles  6  20031213 10:10 