mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Number Theory Discussion Group (https://www.mersenneforum.org/forumdisplay.php?f=132)
-   -   Basic Number Theory 13: Pythagorean triples and a few Diophantine equations (https://www.mersenneforum.org/showthread.php?t=21850)

 Nick 2016-12-18 13:46

Basic Number Theory 13: Pythagorean triples and a few Diophantine equations

1 Attachment(s)
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$$.
[ATTACH]15352[/ATTACH]
For example, if $$a=1$$ and $$b=1$$ then $$c=\sqrt{2}$$.
If $$a,b,c$$ are all [I]positive integers[/I] with $$a^2+b^2=c^2$$, then we call them a [B]Pythagorean triple[/B].
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 [B]primitive[/B] 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.

[U]Proposition 65[/U]
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$$.

[U]proof[/U]
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.

[U]Proposition 66[/U]
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)$$.

[U]proof[/U]
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 [B]Diophantine equations[/B].
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.

[U]Example[/U]
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.

[U]Example[/U]
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.

[U]Exercises[/U]
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}$$.

 LaurV 2016-12-18 14:39

In integers modulo 4, 3^3=3 (mod 4), not 1. (example 2). "so x is even, therefore y is [STRIKE]odd[/STRIKE] 1 (mod 4).", fixed it for you :razz:
The rest seems fine.
You have a patience of steel to write all this, for which you have all my admiration!

 Nick 2016-12-18 14:49

[QUOTE=LaurV;449431]In integers modulo 4, 3^3=3, not 1. (example 2).
The rest seems fine.
[/QUOTE]
Thank you for your sharp-eyed checking!
I have fixed it now.

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