Unit 7: Non-Linear Diophantine Equations & Fermat's Descent

1. Pythagorean Triples

Definition 7.1 (Pythagorean Triple): A Pythagorean triple is a triplet of positive integers $(x, y, z) \in \mathbb{N}^3$ satisfying the Pythagorean equation:

The triple is called primitive if $\gcd(x, y, z) = 1$.

Lemma 7.1 (Parity in Primitive Triples): In any primitive Pythagorean triple $(x, y, z)$:

1. Exactly one of $x, y$ is even and the other is odd.
2. The hypotenuse $z$ is always odd.

Proof: If both $x$ and $y$ were even, then $4 \mid (x^2 + y^2) = z^2 \implies 2 \mid z$, contradicting $\gcd(x, y, z) = 1$. If both $x$ and $y$ were odd, then $x \equiv 1 \text{ or } 3 \pmod 4 \implies x^2 \equiv 1 \pmod 4$, and $y^2 \equiv 1 \pmod 4$. Thus $z^2 = x^2 + y^2 \equiv 1 + 1 = 2 \pmod 4$. But a square of an integer can only be $0$ or $1$ modulo $4$, never $2$! Thus, one of $x, y$ is even and the other is odd, which forces $z^2$ (and hence $z$) to be odd. $\blacksquare$

2. Complete Classification of Primitive Pythagorean Triples

Theorem 7.1 (Euclid's Formula for Pythagorean Triples): Without loss of generality, let $y$ be the even member. Then $(x, y, z)$ is a primitive Pythagorean triple if and only if there exist coprime positive integers $m > n > 0$ of opposite parity ($\gcd(m, n) = 1$ and $m \not\equiv n \pmod 2$) such that:

Proof: Verification ($\impliedby$): $x^2 + y^2 = (m^2 - n^2)^2 + (2mn)^2 = m^4 - 2m^2 n^2 + n^4 + 4m^2 n^2 = m^4 + 2m^2 n^2 + n^4 = (m^2 + n^2)^2 = z^2$. Coprimality follows because any prime dividing both $z$ and $x$ must divide $z + x = 2m^2$ and $z - x = 2n^2$, forcing $p \mid 2$ (ruled out since $z$ is odd) or $p \mid \gcd(m, n) = 1$.

Derivation ($\implies$): Rearrange $x^2 + y^2 = z^2$ with $y$ even:

Since $x$ and $z$ are both odd, $\frac{z - x}{2}$ and $\frac{z + x}{2}$ are integers. Let $d = \gcd\left(\frac{z - x}{2}, \frac{z + x}{2}\right)$. Then $d \mid \left(\frac{z + x}{2} + \frac{z - x}{2}\right) = z$, and $d \mid \left(\frac{z + x}{2} - \frac{z - x}{2}\right) = x$. Since $\gcd(x, z) = 1$, we have $d = 1$. Two coprime positive integers whose product is a perfect square must each be perfect squares! Therefore:

for some positive integers $m > n > 0$ with $\gcd(m, n) = 1$. Adding and subtracting these two equations gives:

And:

1. The Method of Infinite Descent

Pierre de Fermat invented the Method of Infinite Descent (descente infinie), a proof-by-contradiction technique based on the Well-Ordering Principle of $\mathbb{N}$:

1. Assume a Diophantine equation possesses a non-trivial solution in positive integers.
2. Select a solution that minimizes a specific positive invariant (such as $z > 0$).
3. Use the algebraic properties of the equation to construct a strictly smaller positive integer solution ($0 < z' < z$).
4. The existence of an infinite descending sequence of positive integers $z > z' > z'' > \dots > 0$ contradicts the Well-Ordering Principle!
5. Conclude that no positive integer solutions exist.

2. Impossibility of $x^4 + y^4 = z^2$

Theorem 7.2 (Fermat's Theorem on Sums of Fourth Powers): The Diophantine equation:

has no solutions in non-zero integers $x, y, z \in \mathbb{Z} \setminus \{0\}$.

Proof: Suppose for contradiction that non-zero solutions exist. We may assume $x, y, z > 0$ and $\gcd(x, y) = 1$ (dividing out any common factors). By the Well-Ordering Principle, choose a solution with the smallest possible positive value of $z$. Write the equation as:

This is a primitive Pythagorean triple $(x^2, y^2, z)$. By Theorem 7.1, exactly one of $x^2, y^2$ is even; without loss of generality, let $x^2$ be odd and $y^2$ be even. Then there exist coprime integers $m > n > 0$ of opposite parity such that:

Rewrite $x^2 = m^2 - n^2$ as:

Since $\gcd(x, y) = 1$ and $y^2 = 2mn$, we have $\gcd(m, n) = 1$, so $(x, n, m)$ is also a primitive Pythagorean triple! Since $x$ is odd, $n$ must be even. Applying Euclid's formula (Theorem 7.1) a second time:

where $\gcd(a, b) = 1$ and $a, b > 0$. Now examine $y^2 = 2 m n = 2(a^2 + b^2)(2 a b) = 4 a b (a^2 + b^2)$:

Since $\gcd(a, b) = 1$, the three integers $a, b,$ and $a^2 + b^2$ are pairwise coprime! Since their product is a square $(y/2)^2$, each factor must individually be a square:

for some positive integers $u, v, w > 0$. Substituting $a = u^2$ and $b = v^2$ into $a^2 + b^2 = w^2$:

Thus, $(u, v, w)$ is another positive integer solution to the original equation! We now compare $w$ with $z$:

Thus $0 < w < z$, contradicting the minimality of $z$! Therefore, no non-zero integer solutions exist. $\blacksquare$

1. Fermat's Last Theorem for $n = 4$

Corollary 7.1 (Fermat's Last Theorem for $n = 4$): The equation:

has no solutions in non-zero integers $x, y, z$.

Proof: If $x^4 + y^4 = z^4$ had a solution $(x, y, z)$, then setting $Z = z^2$ would yield:

By Theorem 7.2, $x^4 + y^4 = Z^2$ has no non-zero integer solutions. Thus $x^4 + y^4 = z^4$ has no non-zero integer solutions. $\blacksquare$

2. Non-Existence of Right Triangles with Square Area

Fermat noted in the margin of Diophantus's Arithmetica that the area of a right triangle with integer sides cannot be a square.

Theorem 7.3 (No Right Triangle with Square Area): There do not exist positive integers $a, b, c, w$ such that:

Proof: Suppose such a triangle exists. Adding and subtracting $4 w^2 = 2 a b$ from $c^2 = a^2 + b^2$:

Multiplying these two equations:

Setting $X = a^2 - b^2$, $Y = 2 w$, and $Z = c$:

This leads directly to a solution of $u^4 + v^4 = t^2$, which was proved impossible in Theorem 7.2! $\blacksquare$

1. Quadratic Residues

Definition 7.2 (Quadratic Residue and Non-Residue): Let $p$ be an odd prime and $\gcd(a, p) = 1$. $a$ is called a quadratic residue modulo $p$ if the congruence:

has an integer solution. If no solution exists, $a$ is called a quadratic non-residue modulo $p$.

Among the reduced residues $\{1, 2, \dots, p - 1\}$, exactly half ($\frac{p-1}{2}$) are quadratic residues, and the other half ($\frac{p-1}{2}$) are quadratic non-residues.

2. The Legendre Symbol

Definition 7.3 (The Legendre Symbol): For an odd prime $p$ and $a \in \mathbb{Z}$:

3. Euler's Criterion

Theorem 7.4 (Euler's Criterion, 1748): For any odd prime $p$ and integer $a$:

Proof: If $p \mid a$, then $0 \equiv 0 \pmod p$. Now assume $p \nmid a$.

• Case 1: $a$ is a quadratic residue.

Then $x^2 \equiv a \pmod p$ for some $x$. By Fermat's Little Theorem (Theorem 4.1):

• Case 2: $a$ is a quadratic non-residue.

For each $u \in \{1, 2, \dots, p - 1\}$, there is a unique $v \in \{1, 2, \dots, p - 1\}$ such that $u v \equiv a \pmod p$. Since $a$ is a non-residue, $u \ne v$ always. Thus the $p - 1$ integers pair up into $\frac{p-1}{2}$ pairs $\{u_i, v_i\}$ each having product $a$. Multiplying them all together:

By Wilson's Theorem (Theorem 4.6), $(p - 1)! \equiv -1 \pmod p$. Thus:

Corollary 7.2 (First Supplement to Quadratic Reciprocity): Setting $a = -1$ in Euler's Criterion:

Thus $-1$ is a quadratic residue modulo $p$ if and only if $p \equiv 1 \pmod 4$!

1. Gauss's Lemma

Theorem 7.5 (Gauss's Lemma, 1808): Let $p$ be an odd prime and $\gcd(a, p) = 1$. Consider the set of multiples:

Reduce each element to its least positive residue modulo $p$. Let $\nu$ be the number of these residues that exceed $p/2$. Then:

2. The Second Supplement: When is 2 a Quadratic Residue?

Theorem 7.6 (Second Supplement to Quadratic Reciprocity): For any odd prime $p$:

3. The Law of Quadratic Reciprocity

Gauss called this theorem the Theorema Aureum ("Golden Theorem"), publishing eight distinct proofs over his lifetime.

Theorem 7.7 (The Law of Quadratic Reciprocity - Gauss, 1796): Let $p$ and $q$ be distinct odd prime numbers. Then:

Equivalently:

Eisenstein's geometric proof counts integer lattice points inside the rectangle $\left[1, \frac{p-1}{2}\right] \times \left[1, \frac{q-1}{2}\right]$, establishing the identity through triangular partition.