扩展：什么是丢番图方程？

Warm-Up

You and your best friend Diophantus (who doesn't have a friend named Diophantus?) are in a candy store. You are entirely captivated by two types of candy - chocolates and caramels. One package of chocolates cost $\$3$, while one package of caramels cost $\$4$. You reach into your pockets and find that you have $\$21$. How should you spend your money if you want to spend all your money on chocolates and/or caramels?

Fortunately, your friend Diophantus is here to help out. He teaches you about Diophantine equations so you don't need to guess and check all the different spending possibilities.

Definitions

Definition: A Diophantine equation is an equation solving only for integer solutions.

Linear equations, such as $3x+4y=21$, are called linear Diophantine equations. A linear Diophantine equation is of the general form $aX+bY=c$, for which $a, b, c \in \mathbb{Z}$.

Conditions for Yielding Solutions

Does a Diophantine equation equation always yield solutions? For example, does $8X+12Y=2$ have any solutions? Try substituting different values into the equation.

Why do the coefficients $8$ and $12$ prevent the Diophantine equation $8X+12Y=2$ from having any solution? You may have noticed $8$ and $12$ share a common factor of $4$, while the right hand side is not divisible by $4$. This means there cannot be any integer solutions if the right hand side is not divisible by the GCD of the coefficients on the left hand side.

Theorem: The linear Diophantine equation $aX+bY=c$ has integer solutions if and only if $\gcd(a,b) | c$.

Why is $\sqrt{2}$ irrational?

Suppose for the sake of contradiction that $a^2=2$ has a rational solution $a=\frac{p}{q}$. Let $\gcd(p,q)=1$, so that the fraction is in lowest terms. Since it is a solution, $\frac{p^2}{q^2}=2$. Rearranging gives $$p^2=2q^2.$$ Since the right side is even, $p$ must be even. Thus, $p=2k$ for some integer $k$. Substituting this into our equation, we have $$4k^2=2q^2\implies 2k^2=q^2.$$

That means $q$ is even too! So, we know that $2\mid p$ and $2\mid q$. That means $\gcd(p,q)\neq 1$, which is a contradiction. Therefore, $a^2=2$ has no rational solution.

Linear Diophantine Equations

Let $a, b\in{Z}$. The equation $ax + by = c$ has a solution $(x,y) \in{Z^2}$ if and only if $c$ is a multiple of the $gcd(a, b)$. The equation $ax + by = c$ is called a Linear Diophantine Equation.

Examples:

$25x + 16y = 1$ has a solution

$50x + 32y = 2$ has a solution

$50x + 32y = 3$ does not have a solution

Proof:

$(\Rightarrow)$ Suppose that $ax + by = c$ has a solution $(x,y) \in{Z^2}$. The $gcd(a, b)$ will divide $ax + by$ and will therefore divide $c$.

$(\Leftarrow)$Suppose that the $gcd(a, b)\vert{c}$. We need to prove that $ax + by = c$ has a solution. Note that $\frac{a}{gcd(a, b)}$ and $\frac{b}{gcd(a, b)}$ are relatively prime integers. Thus, $\exists m, n \in Z$ such that $\frac{a}{gcd(a, b)}m + \frac{b}{gcd(a, b)}n = 1 \Rightarrow am + bn = gcd(a, b)$. Since the $gcd(a, b)\vert{c}$ and $c = k \cdot gcd(a, b)$ where $k \in Z$. $a(km) + b(kn) = kgcd(a,b) \Rightarrow c = kgcd(a, b)$. Take $x=km$ and $y=kn$, then $ax + by = c$.

Fermat's Last Theorem

Around 1637, Fermat famously wrote

It is impossible to separate a cube into two cubes, or a fourth power into two fourth powers, or in general, any power higher than the second, into two like powers. I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

In other words, Fermat claimed that the equation $x^n + y^n = z^n$ has no positive integer solutions for $n \geq 3$. Contrast with the case of squares: there are plenty of Pythagorean triples, or solutions to $x^2 + y^2 = z^2$ (like the famous $3^2 + 4^2 = 5^2$).

Today this is known as Fermat's Last Theorem. But it is highly unlikely that Fermat actually proved his claim. Not until Sir Andrew Wiles published a proof in the 1990s (with the help of his former student Richard Taylor, and building upon countless recent technical advances in number theory) had anyone actually written down a formal proof. Nonetheless, some today (especially amateurs) are still looking for an "elementary" proof—one that would've been accessible in Fermat's time.

Square+Cube=Square!