Difference between revisions of "Diophantine equation"
m (tidy a bit) |
|||
| Line 5: | Line 5: | ||
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. | 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 == | |
| − | == ax+by=c | + | 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''' | :'''How to Solve a Linear Congruence''' | ||
:(1) Geometrically | :(1) Geometrically | ||
| Line 14: | Line 13: | ||
(example needed) | (example needed) | ||
| − | === | + | == Examples == |
| − | + | <math>a^2</math><math>+b^2=c^2</math> is the general form of any Pythagorean triple <math>(a,b,c)</math>. | |
| + | <math>x^n+y^n=z^n</math> is known as [[Fermat's Last Theorem]] for the condition <math>n\geq3</math>. 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. | ||
| + | == Problems == | ||
| + | === Introductory === | ||
| + | * [[2006_AMC_10A_Problems/Problem_22 | 2006 AMC 10A Problem 22]] | ||
| − | == | + | === Intermediate === |
| − | + | === Olympiad === | |
| − | |||
| − | == | ||
| − | |||
| − | |||
| − | = | ||
| − | |||
==References== | ==References== | ||
| − | [http://www.ams.org/notices/199507/faltings.pdf Proof of Fermat's Last Theorem] | + | *[http://www.ams.org/notices/199507/faltings.pdf Proof of Fermat's Last Theorem] |
| + | ==See also== | ||
| + | * [[Number Theory]] | ||
| − | |||
| − | |||
| − | |||
{{stub}} | {{stub}} | ||
| − | |||
[[Category:Number Theory]] | [[Category:Number Theory]] | ||
Revision as of 15:58, 13 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.
Contents
Linear combination
A Diophantine equation in the form 
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 
. 3 is a divisor of the LHS (also notice that 
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 
, 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 
or 
. 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 
(if we think of (0,1) as a "starting point").
- (2) Modular Arithmetical-ly
(example needed)
Examples
is the general form of any Pythagorean triple 
.
is known as Fermat's Last Theorem for the condition 
. 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.
Problems
Introductory
Intermediate
Olympiad
References
See also
This article is a stub. Help us out by expanding it.
