Difference between revisions of "Diophantine equation"

(Linear combination: cleanup)
Line 7: Line 7:
 
== Linear combination ==
 
== Linear combination ==
 
A Diophantine equation in the form <math>ax+by=c</math> 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 <math>3x-9y=3(x-3y)=17</math>.  3 is a divisor of the LHS (also notice that <math>x-3y</math> must always be an integer).  However, 17 will never be a multiple of 3, hence, no solutions exist.
 
A Diophantine equation in the form <math>ax+by=c</math> 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 <math>3x-9y=3(x-3y)=17</math>.  3 is a divisor of the LHS (also notice that <math>x-3y</math> must always be an integer).  However, 17 will never be a multiple of 3, hence, no solutions exist.
:'''How to Solve a Linear Congruence'''
+
=== Methods of Solving ===
:(1) Geometrically
+
==== Coordinate Plane ====
Note that any linear congruence can be transformed into the linear equation <math>y=\frac{-b}{a}x+\frac{c}{a}</math>, which is just the slope-intercept equation for a line.  The solutions to the diophantine equation correspond to [[lattice point]]s that lie on the line.  For example, consider the equation <math>-3x+4y=4</math> or <math>y=\frac{3}{4}x+1</math>. 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]] <math>x=4t, y=3t+1</math> (if we think of (0,1) as a "starting point").   
+
Note that any linear congruence can be transformed into the linear equation <math>y=\frac{-b}{a}x+\frac{c}{a}</math>, which is just the slope-intercept equation for a line.  The solutions to the diophantine equation correspond to [[lattice point]]s that lie on the line.  For example, consider the equation <math>-3x+4y=4</math> or <math>y=\frac{3}{4}x+1</math>. 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]] <math>x=4t, y=3t+1</math> (if we think of <math>(0,1)</math> as a "starting point").   
:(2) Modular Arithmetical-ly 
+
==== Modular Arithmetic ==== 
(example needed)
+
{{incomplete|section}}
  
 
== Examples ==
 
== Examples ==

Revision as of 17:14, 16 December 2007

This is an AoPSWiki Word of the Week for Dec 13-19

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.

Linear combination

A Diophantine equation in the form $ax+by=c$ 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.

Methods of Solving

Coordinate Plane

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").

Modular Arithmetic

Template:Incomplete

Examples

$a^2$$+b^2=c^2$ is the general form of any Pythagorean triple $(a,b,c)$.

$x^n+y^n=z^n$ 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.

Solving Diophantine Equations

Sometimes, modular arithmetic can be used to prove that no solutions to a given Diophantine equation exist. Specifically, if we show that the equation in question is never true mod $m$, for some integer $m$, then we have shown that the equation is false. However, this technique cannot be used to show that solutions to a Diophantine equation do exist.

Sometimes, when a few solutions have been found, induction can be used to find a family of solutions. Techniques such as infinite descent can also show that no solutions to a particular equation exist, or that no solutions outside of a particular family exist.

It is natural to ask whether there is a general solution for Diophantine equations. This was Hilbert's Tenth Problem. Unfortunately, the answer to this question is "no."

Problems

Introductory

Intermediate

Olympiad

References

See also

This article is a stub. Help us out by expanding it.