Diophantine equation

A Diophantine equation is an equation which must be solved using only integers.

Finding the solution or solutions to a Diophantine equation is closely tied to modular arithmetic and number theory. Often, when a Diophantine equation has infinitely many solutions, parametric form is used to express the relation between the variables of the equation.

ax+by=c

This Diophantine equation is known as a linear combination. If two relatively prime integers a and b are written in this form with c=1, the equation will have an infinite number of solutions. More generally, there will always be an infinite number of solutions when gcd(a,b)=c. If gcd(a,b)=c, then there are no solutions to the equation. To see why, consider the equation $3x-9y=3(x-3y)=17$ . 3 is a divisor of the LHS (also notice that $x-3y$ must always be an integer). However, 17 will never be a multiple of 3, hence, no solutions exist.

How to Solve a Linear Congruence

(1) Geometrically

Note that any linear congruence can be transformed into the linear equation $y=\frac{-b}{a}x+\frac{c}{a}$ , which is just the slope-intercept equation for a line. The solutions to the diophantine equation correspond to lattice points that lie on the line. For example, consider the equation $-3x+4y=4$ or $y=\frac{3}{4}x+1$ . One solution is (0,1). If you graph the line, it's easy to see that the line intersects a lattice point as x and y increase or decrease by the same multiple of 4 and 3, respectively (wording?). Hence, the solutions to the equation may be written parametrically $x=4t, y=3t+1$ (if we think of (0,1) as a "starting point").

(2) Modular Arithmetical-ly

(example needed)

Example Problems

2006 AMC 10A Problem 22

$a^2$ $+b^2=c^2$

This is the general form of any Pythagorean triple (a,b,c).

$x^4+y^4=z^2$

$x^n+y^n=z^n$

This is known as Fermat's Last Theorem for the condition $n\geq3$ . In the 1600s, Fermat, as he was working through a book on Diophantine Equations, wrote a comment in the margins to the effect of "I have a truly marvelous proof of this proposition which this margin is too narrow to contain." Fermat actually made many conjectures and proposed plenty of "theorems," but wasn't one to write down the proofs or much other than scribbled comments. After he died, all his conjectures were re-proven (either false or true) except for Fermat's "Last" Theorem. After over 350 years of failing to be proven, FLT was finally solved by Andrew Wiles after he spent over 7 years working on the 200-page proof, and another year fixing an error in the original proof. There are several good books on the history of this problem.

References

Proof of Fermat's Last Theorem

Page

Toolbox

Search