Difference between revisions of "Diophantine equation"

Latest revision as of 00:15, 4 July 2024

A Diophantine equation is an equation relating integer (or sometimes natural number or whole number) quanitites.

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.

Diophantine equations are named for the ancient Greek/Alexandrian mathematician Diophantus.

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)=1$ . If $\gcd(a,b)\nmid 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.

Now consider the case where $c=0$ . Thus, $ax=-by$ . If $a$ and $b$ are relatively prime, then all solutions are obviously in the form $(bk,-ak)$ for all integers $k$ . If they are not, we simply divide them by their greatest common divisor.

Pythagorean Triples

Main article: Pythagorean triple

A Pythagorean triple is a set of three integers that satisfy the Pythagorean Theorem, $a^2+b^2=c^2$ . There are three main methods of finding Pythagorean triples:

Method of Pythagoras

If $m>1$ is an odd number, then $m, \frac {m^2 -1}{2}, \frac {m^2 + 1}{2}$ is a Pythagorean triple.

Method of Plato

If $n>1$ , $2n, n^2 - 1, n^2 + 1$ is a Pythagorean triple.

Babylonian Method

For any $m,n$ ( $m>n$ ), we have $m^2 - n^2, 2mn, m^2 + n^2$ is a Pythagorean triple.

Sum of Fourth Powers

An equation of form $x^4+y^4=z^2$ has no integer solutions, as follows: We assume that the equation does have integer solutions, and consider the solution which minimizes $z$ . Let this solution be $(x_0,y_0,z_0)$ . If $\gcd (x_0,y_0)\neq 1$ then their GCD $d$ must satsify $d^2|z$ . The solution $\left(\frac{x_0}{d},\frac{y_0}{d},\frac{z_0}{d^2}\right)$ would then be a solution less than $z_0$ , which contradicts our assumption. Thus, this equation has no integer solutions.

If $\gcd(x_0,y_0)=1$ , we then proceed with casework, in $\mod 4$ .

Note that every square, and therefore every fourth power, is either $1$ or $0\mod 4$ . The proof of this is fairly simple, and you can show it yourself.

Case 1: $x_0^4 \equiv y_0^4 \equiv 1\mod 4$

This would imply $z^2 \equiv 2\mod 4$ , a contradiction.

Case 2: $x_0^4 \equiv y_0^4 \equiv 0\mod 4$

This would imply $z^2 \equiv 0\mod 4$ , a contradiction since we assumed $\gcd(x_0,y_0)=1$ .

Case 3: $x_0^4 \equiv 1\mod 4, y_0^4 \equiv 0\mod 4$ , and $z_0^2 \equiv 1\mod 4$

We also know that squares are either $-1, 0$ or $1 \mod 5$ . Thus, all fourth powers are either $0$ or $1 \mod 5$ .

By similar approach, we show that:

$x_0^4 \equiv 0\mod 5, y_0^4 \equiv 1\mod 5$ , so $z_0^2 \equiv 1\mod 5$ .

This is a contradiction, as $z_0^2 \equiv 1\mod 4$ implies $z_0$ is odd, and $z_0^2 \equiv 1\mod 5$ implies $z_0$ is even. QED [Oops, this doesn't work. 21 (or $3^4 = 81$ ) are equal to $1\mod 5$ and not even...]

Pell Equations

Main article: Pell equation

A Pell equation is a type of Diophantine equation in the form $x^2-Dy^2=\pm1$ for natural number $D$ . The solutions to the Pell equation when $D$ is not a perfect square are connected to the continued fraction expansion of $\sqrt D$ . If $a$ is the period of the continued fraction and $C_k=P_k/Q_k$ is the $k$ th convergent, all solutions to the Pell equation are in the form $(P_{ia},Q_{ia})$ for positive integer $i$ .

Methods of Solving

Coordinate Plane

Note that any linear combination 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

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.

Induction

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.

General Solutions

It is natural to ask whether there is a general solution for Diophantine equations, i.e., an algorithm that will find the solutions for any given Diophantine equations. This is known as Hilbert's tenth problem. The answer, however, is no.

Fermat's Last Theorem

Main article: Fermat's Last Theorem

$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, the theorem was finally proven 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.

Problems

Introductory

Two farmers agree that pigs are worth $300$ dollars and that goats are worth $210$ dollars. When one farmer owes the other money, he pays the debt in pigs or goats, with "change" received in the form of goats or pigs as necessary. (For example, a $390$ dollar debt could be paid with two pigs, with one goat received in change.) What is the amount of the smallest positive debt that can be resolved in this way?

$\mathrm{(A) \ } 5\qquad \mathrm{(B) \ } 10\qquad \mathrm{(C) \ } 30\qquad \mathrm{(D) \ } 90\qquad \mathrm{(E) \ } 210$

(Source)

Intermediate

Let $P(x)$ be a polynomial with integer coefficients that satisfies $P(17)=10$ and $P(24)=17.$ Given that $P(n)=n+3$ has two distinct integer solutions $n_1$ and $n_2,$ find the product $n_1\cdot n_2$ . (Source)

Olympiad

Determine the maximum value of $m^2 + n^2$ , where $m$ and $n$ are integers satisfying $m, n \in \{ 1,2, \ldots , 1981 \}$ and $( n^2 - mn - m^2 )^2 = 1$ . (Source)
Solve in integers the equation $x^3+x^2+x+1=y^2$ .

References

Proof of Fermat's Last Theorem

@@ Line 1: / Line 1: @@
-{{WotWAnnounce|week=Dec 13-19}}
+A '''Diophantine equation''' is an [[equation]] relating [[integer]] (or sometimes [[natural number]] or [[whole number]]) quanitites.
-A '''Diophantine equation''' is an [[equation]] which must be solved using only [[integer]]s.
+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.
+Diophantine equations are named for the ancient Greek/Alexandrian mathematician Diophantus.
+== Linear Combination ==
+A Diophantine equation in the form <math>ax+by=c</math> is known as a linear combination.  If two [[relatively prime]] integers <math>a</math> and <math>b</math> are written in this form with <math>c=1</math>, the equation will have an infinite number of solutions.  More generally, there will always be an infinite number of solutions when <math>\gcd(a,b)=1</math>.  If <math>\gcd(a,b)\nmid c</math>, then there are no solutions to the equation.  To see why, consider the equation <math>3x-9y=3(x-3y)=17</math>.  <math>3</math> is a divisor of the LHS (also notice that <math>x-3y</math> must always be an integer).  However, <math>17</math> will never be a multiple of <math>3</math>, hence, no solutions exist.
+Now consider the case where <math>c=0</math>. Thus, <math>ax=-by</math>. If <math>a</math> and <math>b</math> are relatively prime, then all solutions are obviously in the form <math>(bk,-ak)</math> for all integers <math>k</math>. If they are not, we simply divide them by their greatest common divisor.
+See also: [https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bézout's identity].
+== Pythagorean Triples ==
+{{main|Pythagorean triple}}
+A Pythagorean triple is a set of three [[integer]]s that satisfy the [[Pythagorean Theorem]], <math>a^2+b^2=c^2</math>. There are three main methods of finding Pythagorean triples:
+=== Method of Pythagoras ===
+If <math>m>1</math> is an [[odd]] number, then <math>m, \frac {m^2 -1}{2}, \frac {m^2 + 1}{2}</math> is a Pythagorean triple.
+=== Method of Plato ===
+If <math>n>1</math>, <math>2n, n^2 - 1, n^2 + 1</math> is a Pythagorean triple.
+=== Babylonian Method ===
+For any <math>m,n</math>(<math>m>n</math>), we have <math>m^2 - n^2, 2mn, m^2 + n^2</math> is a Pythagorean triple.
+== Sum of Fourth Powers ==
+An equation of form <math>x^4+y^4=z^2</math> has no [[integer]] solutions, as follows:
+<!-- taken from AoPS Vol. 2 -->
+We assume that the equation does have integer solutions, and consider the solution which minimizes <math>z</math>. Let this solution be <math>(x_0,y_0,z_0)</math>. If <math>\gcd (x_0,y_0)\neq 1</math> then their [[GCD]] <math>d</math> must satsify <math>d^2|z</math>. The solution <math>\left(\frac{x_0}{d},\frac{y_0}{d},\frac{z_0}{d^2}\right)</math> would then be a solution less than <math>z_0</math>, which contradicts our assumption. Thus, this equation has no integer solutions.
+If <math>\gcd(x_0,y_0)=1</math>, we then proceed with casework, in <math>\mod 4</math>.
+Note that every square, and therefore every fourth power, is either <math>1</math> or <math>0\mod 4</math>. The proof of this is fairly simple, and you can show it yourself.
+Case 1: <math>x_0^4  \equiv  y_0^4 \equiv 1\mod 4</math>
+This would imply <math>z^2 \equiv 2\mod 4</math>, a contradiction.
+Case 2: <math>x_0^4  \equiv  y_0^4 \equiv 0\mod 4</math>
+This would imply <math>z^2 \equiv 0\mod 4</math>, a contradiction since we assumed <math>\gcd(x_0,y_0)=1</math>.
+Case 3: <math>x_0^4  \equiv 1\mod 4,  y_0^4 \equiv 0\mod 4</math>, and <math>z_0^2 \equiv 1\mod 4</math>
+We also know that squares are either <math> -1, 0 </math> or <math>1 \mod 5</math>. Thus, all fourth powers are either <math>0</math> or <math>1 \mod 5</math>.
+By similar approach, we show that:
+<math>x_0^4  \equiv 0\mod 5,  y_0^4 \equiv 1\mod 5</math>, so <math>z_0^2 \equiv 1\mod 5</math>.
+This is a contradiction, as <math>z_0^2 \equiv 1\mod 4</math> implies <math>z_0</math> is odd, and <math>z_0^2 \equiv 1\mod 5</math> implies <math>z_0</math> is even.  QED [Oops, this doesn't work.  21 (or <math>3^4 = 81</math>) are equal to <math>1\mod 5</math> and not even...]
+== Pell Equations ==
+{{main|Pell equation}}
+A Pell equation is a type of Diophantine equation in the form <math>x^2-Dy^2=\pm1</math> for [[natural number]] <math>D</math>. The solutions to the Pell equation when <math>D</math> is not a perfect square are connected to the continued [[fraction]] expansion of <math>\sqrt D</math>. If <math>a</math> is the [[period]] of the continued fraction and <math>C_k=P_k/Q_k</math> is the <math>k</math>th convergent, all solutions to the Pell equation are in the form <math>(P_{ia},Q_{ia})</math> for [[positive]] integer <math>i</math>.
+== Methods of Solving ==
+=== Coordinate Plane ===
+Note that any linear combination 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 <math>4</math> and <math>3</math>, 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").
+=== Modular Arithmetic ===
+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.
+===Induction===
+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.
-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.
+=== General Solutions ===
-== Linear combination ==
+It is natural to ask whether there is a general solution for Diophantine equations, i.e., an algorithm that will find the solutions for any given Diophantine equations.  This is known as [[Hilbert's tenth problem]]. The answer, however, is no.
-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'''
-:(1) Geometrically
-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").
-:(2) Modular Arithmetical-ly
-(example needed)
-== Examples ==
+== Fermat's Last Theorem ==
-<math>a^2</math><math>+b^2=c^2</math> is the general form of any Pythagorean triple <math>(a,b,c)</math>.
+{{main|Fermat's Last Theorem}}
+<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, the theorem was finally proven 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.
-<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]]
+* Two farmers agree that pigs are worth <math>300</math> dollars and that goats are worth <math>210</math> dollars. When one farmer owes the other money, he pays the debt in pigs or goats, with "change" received in the form of goats or pigs as necessary. (For example, a <math>390</math> dollar debt could be paid with two pigs, with one goat received in change.) What is the amount of the smallest positive debt that can be resolved in this way?
+<math> \mathrm{(A) \ } 5\qquad \mathrm{(B) \ } 10\qquad \mathrm{(C) \ } 30\qquad \mathrm{(D) \ } 90\qquad \mathrm{(E) \ }  210</math>
+([[2006_AMC_10A_Problems/Problem_22|Source]])
 === Intermediate ===
+*Let <math> P(x) </math> be a polynomial with integer coefficients that satisfies <math> P(17)=10 </math> and <math> P(24)=17. </math> Given that <math> P(n)=n+3 </math> has two distinct integer solutions <math> n_1 </math> and <math> n_2, </math> find the product <math> n_1\cdot n_2</math>. ([[2005 AIME II Problems/Problem 13|Source]])
 === Olympiad ===
+*Determine the maximum value of <math>m^2 + n^2 </math>, where <math>m </math> and <math>n </math> are integers satisfying <math> m, n \in \{ 1,2, \ldots , 1981 \} </math> and <math>( n^2 - mn - m^2 )^2 = 1 </math>. ([[1981 IMO Problems/Problem 3|Source]])
+*Solve in integers the equation <math>x^3+x^2+x+1=y^2</math>.
 ==References==
@@ Line 30: / Line 98: @@
 ==See also==
 * [[Number Theory]]
+* [[Pell equation]]
-{{stub}}
+[[Category:Number theory]]
-[[Category:Number Theory]]

Page

Toolbox

Search