Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Diophantine equation"

m (tidy a bit)
Line 17: Line 17:
  
 
<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.
 
<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.
 +
 +
== 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 <math>m</math>, for some integer <math>m</math>, 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 ==
 
== Problems ==
Line 30: Line 38:
 
==See also==
 
==See also==
 
* [[Number Theory]]
 
* [[Number Theory]]
 +
* [[Pell equation]]
  
 
{{stub}}
 
{{stub}}
 
[[Category:Number Theory]]
 
[[Category:Number Theory]]

Revision as of 00:13, 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.

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)

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Diophantine_equation&oldid=21282"