mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2016-12-18, 13:46   #1
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

1,453 Posts
Default 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\).
Click image for larger version

Name:	triangle2.png
Views:	62
Size:	5.8 KB
ID:	15352
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)
Nick is online now   Reply With Quote
Old 2016-12-18, 14:39   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22A716 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2016-12-18, 14:49   #3
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

1,453 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
Nick is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Basic Number Theory 1 & 2 Nick Number Theory Discussion Group 17 2017-12-23 20:10
Final Lucas Lehmer residuals and Pythagorean triples a nicol Miscellaneous Math 21 2017-12-19 11:34
Basic Number Theory 18: quadratic equations modulo n Nick Number Theory Discussion Group 4 2017-03-27 06:01
Pythagorean triples Rokas Math 3 2005-01-02 03:50
Pythagorean Triples jinydu Puzzles 6 2003-12-13 10:10

All times are UTC. The time now is 15:15.

Tue Oct 27 15:15:29 UTC 2020 up 47 days, 12:26, 1 user, load averages: 3.00, 3.16, 3.13

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.