mersenneforum.org > Math Basic Number Theory 13: Pythagorean triples and a few Diophantine equations
 Register FAQ Search Today's Posts Mark Forums Read

 2016-12-18, 13:46 #1 Nick     Dec 2012 The Netherlands 110111001012 Posts Basic Number Theory 13: Pythagorean triples and a few Diophantine equations If a right-angled 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^2-s^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^4-2r^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 $$p|a$$ and $$p|b$$. Then $$p|a^2+b^2=c^2$$ and $$p$$ is prime so $$p|c$$ (and $$p|-c$$ too). Thus $$p$$ divides both $$r^2-s^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^2-s^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)(a-bi)=c^2$$. Take any Gaussian integer $$z=x+yi$$ such that $$z|a+bi$$ and $$z|a-bi$$. Then $$z$$ divides their sum $$2a$$ and their difference $$2bi$$, and $$i$$ is a unit so $$z|2b$$. As $$\gcd(a,b)=1$$, it follows that $$z|2$$ so, by proposition 48(iii), $$N(z)|N(2)$$ i.e. $$x^2+y^2|4$$. 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 $$2|a+bi$$ and $$2|a-bi$$ so $$4|(a+bi)(a-bi)=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+i|a+bi$$ and $$1+i|a-bi$$ (and $$-i$$ is a unit) so $$2=-i(1+i)^2|(a+bi)(a-bi)=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)(a-bi)=c^2$$ but no prime Gaussian integer divides both $$a+bi$$ and $$a-bi$$, 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^2-s^2)+2rsi=a+bi$$ so $$a=r^2-s^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 $$p|r$$ and $$p|s$$ then $$p|a$$ and $$p|b$$, 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)(x-i)=y^3$$. For any Gaussiain integer $$z$$, if $$z|x+i$$ and $$z|x-i$$ then $$z$$ divides their difference $$2i$$ and $$i$$ is a unit so $$z|2$$. Thus $$z$$ divides $$x+i$$ and it also divides $$2t=x$$ so $$z|i$$, i.e. $$z$$ is a unit. So no prime Gaussian integer divides both $$x+i$$ and $$x-i$$. 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^2-3d^2)+d(3c^2-d^2)i$$ so $$x=c(c^2-3d^2)$$ and $$1=d(3c^2-d^2)$$. Thus $$d|1$$ (in $$\mathbb{Z}$$) so $$d=\pm 1$$ and therefore $$d^2=1$$. And $$3c^2-d^2=3c^2-1$$ 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^2-3d^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 non-negative 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 2016-12-18 at 14:47 Reason: Typo in 2nd example (as pointed out by LaurV below)
 2016-12-18, 14:39 #2 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 1002110 Posts In integers modulo 4, 3^3=3 (mod 4), not 1. (example 2). "so x is even, therefore y is odd 1 (mod 4).", fixed it for you 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 2016-12-18 at 14:55
2016-12-18, 14:49   #3
Nick

Dec 2012
The Netherlands

5·353 Posts

Quote:
 Originally Posted by LaurV In integers modulo 4, 3^3=3, not 1. (example 2). The rest seems fine.
Thank you for your sharp-eyed checking!
I have fixed it now.

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 17 2017-12-23 20:10 a nicol Miscellaneous Math 21 2017-12-19 11:34 Nick Number Theory Discussion Group 4 2017-03-27 06:01 Rokas Math 3 2005-01-02 03:50 jinydu Puzzles 6 2003-12-13 10:10

All times are UTC. The time now is 19:11.

Thu Aug 18 19:11:33 UTC 2022 up 16:40, 0 users, load averages: 1.85, 1.56, 1.55