Diophantine Equation

Source: An Introduction to Diophantine Equations - A Problem-Based Approach

A Diophantine equation is a polynomial equation with two or more unknowns of which only integer solutions are interested. In other words, a Diophantine equation is an equation of the form, ƒ(x₁,x₂,…,xₙ)=0 where ƒ is an n-variable function with n≥2. A Diophantine equation is an algeraic Diophantine equation, if ƒ is a polynomial with integral coefficients. An n-uple (x₁⁰,x₂⁰,…,xₙ⁰)∈ℤⁿ satisfying the algebraic Diophantine equation is called a solution to the algebraic Diophantine equation. An equation having one or more solutions is called solvable.

The most common general bivariate quadratic Diophantine equation is of the form, Ax²  + Bxy + Cy²  + Dx + Ey + F = 0 in which all variables and solutions should be integer numbers in general.

The three basic problems of a Diophantine equation are

• Is the equation solvable?
• If it si solvable, is the number of its solutions finite or infinite?
• If it si solvable, determine all of its solutions.

Solving Diophantine Equation

The Factoring Method

For a given Diophantine equation ƒ(x₁,x₂,…,xₙ)=0, if the equation can be expressed in the equivalent form
ƒ₁(x₁,x₂,…,xₙ)ƒ₂(x₁,x₂,…,xₙ)⋯ƒₖ(x₁,x₂,…,xₙ)=a
where   ƒ₁, ƒ₂,… , ƒₖ∈ℤ[x₁,x₂,…,xₙ] and a∈ℤ, then the prime factorizations of a can be used to construct a system of equations.
Let the finite decompositions of a are k integer prime factors a₁, a₂,…, aₖ. Each such factorization can then yield a system of equations.

• ƒ₁(x₁,x₂,…,xₙ)=a₁
• ƒ₂(x₁,x₂,…,xₙ)=a₂
• …
• ƒₖ(x₁,x₂,…,xₙ)=aₖ

The complete set of solutions to the Diophantine equation can be obtained by solving the system of equations.

For example

 x²-y²=pq
⇒(x+y)(x-y)=pq
⇒(x+y)=p and (x-y)=q, (x+y)=q and (x-y)=p, (x+y)=1 and (x-y)=pq, or (x+y)=pq and (x-y)=1
If x²-y²=35 then
⇒(x+y)=5and (x-y)=7⇒x=6, y=-1
⇒(x+y)=7 and (x-y)=5⇒x=6, y=1
⇒(x+y)=1 and (x-y)=35⇒x=18, y=-17
⇒(x+y)=35 and (x-y)=1⇒x=18, y=17

Method of Interval

For a given Diophantine equation ƒ(x₁,x₂,…,xₙ)=0, if the variables of equation can be restricted within intervals by appropriate inequalities, then the solutions of the equation may lead to only finitely many possibile values.

For example

 x³+y³=(x+y)²,
All pairs of the form (k, -k), k∈ℤ, are solutions of the equation. If x+y≠0, then
(x+y)(x₂-xy+y₂)=(x+y)₂
⇒(x₂-xy+y₂)=(x+y)
⇒x₂-xy+y₂-x-y=0
⇒2(x₂-xy+y₂-x-y+1)=2
⇒x₂-2xy+y₂+x₂-2x+1+y₂-2y+1=2
⇒(x-y)₂+(x-1)₂+(y-1)₂=2

Because of square terms on the left hand side and the sum of 2 on the right hand side, one of the three terms on the left hand side must be equal to zero and each term on the left hand side must be less than or equal to 1, (x-y)₂≤1, (x-1)₂≤1, and (y-1)₂≤1. Therefore the variables x, y are restricted between the interval [0,2]. The other solutions of the equation is then equal to (0,1), (1,0), (1,2), (2,1), and (2,2) besides (k,-k).

The Parametric Method

In some cases, the integral solutions of a Diophantine equation, ƒ(x₁,x₂,…,xₙ)=0, can be expressed in a parametric form, that is x₁=g₁(k₁,k₂,…,kₗ), x₂=g₂(k₁,k₂,…,kₗ), …, x₂=gₖ(k₁,k₂,…,kₗ), where g₁, g₂, …, gₖ are integer-valued l-variable functions and k₁,k₂,…,kₗ∈ℤ. Sometimes the set of solutions may have multiple parametric representations. However, for most Diophantine equations it is not possible to find all solutions explicitly. In many such cases,the parametric method provides a proof of the existence of infinitely many solutions.

For example

 x³+y³+z³=x²+y²+z²
Let z=-y,
⇒x³+y³-y³=x²+y²+y²⇒x³=x²+2y²
Let y=mx. m∈ℤ
⇒x³=x²+2(mx)²⇒x=1+2m²
Therefore the infinite family of solutions of the equation are
x=2m²+1, y=m(2m²+1), z=-m(2m²+1)

The Modular Arithmetic Method

In some cases, simple modular arithmetic considerations are used to prove the Diophantine equation is not solvable or in reducing the range of their possible solutions.

For example

(x+1)²+(x+2)²+…+(x+2001)²=y²
Let x=z-1001
⇒(z-1000)²+(z-999)²+…+(z-1)²+z²+(z+1)²+…+(z+1000)²=y²
⇒2001z²+2(1²+2²+…+999²+1000²)=y²
⇒2001z²+2((1000*(1000+1)*(2*1000+1))/6)=y²
⇒2001z²+1000*1001*667=y²⇒2001z²+667667000=y²
⇒2=y² (mod 3)
Since the left hand side 2 (mod 3) cannot be a perfect square, therefore the equation is not solvable.

The Method of Mathematical Induction

Mathematical induction is a tool for proving statements depending on nonnegative integers. Let (P(n))n≥0 be a sequence of propositions. The method of mathematical induction can then be used to prove that P(n) is true for all n≥n₀, where n₀ is a given nonnegative integer.

Mathematical Induction (weak form)

Suppose

• P(n₀) is true
• For all k≥n₀, when P(k) is true implies P(k) is true

Then P(n) is true for all n≥n₀.

Mathematical Induction (with step s)

Let s be a fixed positive integer. Suppose

• P(n₀), P(n₀+1), …, P(n₀+s-1) are true
• For all k≥n₀, when P(k) is true implies P(k+s) is true

Then P(n) is true for all n≥n₀.

Mathematical Induction (strong form)

Suppose

• P(n₀) is true
• For all k≥n₀, when P(m) is true for all m with n₀≤m≤k implies P(k+1) is true

Then P(n) is true for all n≥n₀.

For example

x²+y²+z²=59ⁿ, there exist positive integers x,y, z for all integer n≥3

Let step s=2 and n₀=1
For (x₁,y₁,z₁)=(1,3,7)⇒xₙ²+yₙ²+zₙ²=59ⁿ⇒1²+3²+7²=59¹⇒x₁²+y₁²+z₁²=59¹
For (x₂,y₂,z₂)=(14,39,42)⇒xₙ²+yₙ²+zₙ²=59ⁿ⇒14²+39²+42²=59²⇒x₂²+y₂²+z₂²=59²

For n≥3, let xₙ₊₂=59xₙ, yₙ₊₂=59yₙ, zₙ₊₂=59zₙ

Therefore, for all n≥1 then
⇒xₖ₊₂²+yₖ₊₂²+zₖ₊₂²=(59xₖ)²+(59yₖ)²+(59zₖ)²
⇒xₖ₊₂²+yₖ₊₂²+zₖ₊₂²=59²(xₖ²+yₖ²+zₖ²)
Since step s=2 and n=k=1,2 are true
⇒xₖ₊₂²+yₖ₊₂²+zₖ₊₂²=59²(59k)
⇒xₖ₊₂²+yₖ₊₂²+zₖ₊₂²=59k+2

In other words, for all n≥1 then
Since xₙ₊₂=59xₙ, yₙ₊₂=59yₙ, zₙ₊₂=59zₙ
for i=2n-1={1,3,5,…)
⇒(x₁,y₁,z₁)=(1,3,7)=(1(59⁰),3(59⁰),7(59⁰))=59=592(1)-1
⇒(x₁₊₂,y₁₊₂,z₁₊₂)=(1(59),3(59),7(59))=(1(59¹),3(59¹),7(59¹))=1²(59²)+3²(59²)+7²(59²)=59(59²)=591+2=592(2)-1
⇒(x₁₊₂₊₂,y₁₊₂₊₂,z₁₊₂₊₂)=(1(59)(59),3(59)(59),7(59)(59))=(1(59²),3(59²),7(59²))=1²(59²59²)+3²(59²59²)+7²(59²59²)=59(59²59²)=591+2+2=592(3)-1
Therefore
⇒(x₂ₙ₋₁,y₂ₙ₋₁,z₂ₙ₋₁)=(x₁₊₂₍ₙ₋₁₎,y₁₊₂₍ₙ₋₁₎,z₁₊₂₍ₙ₋₁₎)
⇒(x₂ₙ₋₁,y₂ₙ₋₁,z₂ₙ₋₁)=(x₁(59n-1),y₁(59n-1),z₁(59n-1))
⇒(x₂ₙ₋₁,y₂ₙ₋₁,z₂ₙ₋₁)=(1(59n-1),3(59n-1),7(59n-1))
⇒(x₂ₙ₋₁,y₂ₙ₋₁,z₂ₙ₋₁)=1²(59n-1)²+3²(59n-1)²+7²(59n-1)²
⇒(x₂ₙ₋₁,y₂ₙ₋₁,z₂ₙ₋₁)=59(592(n-1))=592n-1
for j=2n={2,4,6,…)
⇒(x₂,y₂,z₂)=(14,39,42)=(14(59⁰),39(59⁰),42(59⁰))=592=592(1)
⇒(x₂₊₂,y₂₊₂,z₂₊₂)=(14(59),39(59),42(59))=(14(59¹),39(59¹),42(59¹))=14²(59²)+39²(59²)+42²(59²)=59²(59²)=592+2=592(2)
⇒(x₂₊₂₊₂,y₂₊₂₊₂,z₂₊₂₊₂)=(14(59)(59),39(59)(59),42(59)(59))=(14(59²),39(59²),42(59²))=14²(59²59²)+39²(59²59²)+42²(59²59²)=59²(59²59²)=592+2+2=592(3)
Therefore
⇒(x₂ₙ,y₂ₙ,z₂ₙ)=(x₂₊₂₍ₙ₋₁₎,y₂₊₂₍ₙ₋₁₎,z₂₊₂₍ₙ₋₁₎)
⇒(x₂ₙ,y₂ₙ,z₂ₙ)=(x₂(59n-1),y₂(59n-1),z₂(59n-1))
⇒(x₂ₙ,y₂ₙ,z₂ₙ)=(14(59n-1),39(59n-1),42(59n-1))
⇒(x₂ₙ,y₂ₙ,z₂ₙ)=14²(59n-1)²+39²(59n-1)²+42²(59n-1)²
⇒(x₂ₙ,y₂ₙ,z₂ₙ)=59²(592(n-1))=592n

Fermat's Method of Infinite Descent (FMID)

The method of infinite descent is an indirect method that is proved by contradiction and relies on the least integer principle. One typical application is to prove an equation has no solutions or is false for all large enough nonnegative integer. 

Both finite and infinite descent methods assume a property P concerning the nonnegative integers and a nonnegative integer n such that (P(n))n≥1 be the sequence of propositions where {P(n): n satisfies property P}. To prove the proposition P(n) is false for all large enough n.
For the finite descent method, let k be a nonnegative integer. Suppose that:

• P(k) is not true
• whenever P(m) is true for a nonnegative integer m>k, then there must be some smaller j, m>j≥k, for which P(j) is true.

Then P(n) is false for all n≥k. That is, P(n) is false for any nonnegative integer n since P(k) is not true.

For the Fermat's Method of Infinite Descent (FMID), let k be a nonnegative integer. Suppose that:

• P(k) is not true
• whenever P(m) is true for an integer m>k, then there must be some smaller integer j, m>j>k, for which P(j) is true.

Then P(n) is false for all n>k. That is, P(n) is false for any nonnegative integer n since no infinite descending sequence, P(n) exists for nonnegative integers n, such that n₁>n₂>⋯>k.

In other words, there is no infinite descending sequence of nonnegative integers, n₁>n₂>⋯. if P(k) is not true, then there is no no infinite descending sequence of nonnegative integers, n₁>n₂>⋯>k and If n₀ is the smallest positive integer n for which P(n₀) is true, then P(n) is false for all n<n₀.

And, If the sequence of nonnegative integers (nᵢ)i≥1 satisfies the inequalities n₁≥n₂≥⋯ then there esists i₀ such that nᵢ₀=nᵢ₀₊₁=⋯.

For example

x³+2y³=4z³, (0,0,0) is the only solution and there are no other nonnegative integer solutions.

Assume (x₁, y₁, z₁) is a nontrivial solution. Since ³√2, ³√4 are both irrational, x₁>0, y₁>0, z₁>0.

Subsitute (x₁, y₁, z₁) into x³+2y³=4z³, imply x₁³+2y₁³=4z₁³,
therefore 2|x₁, let x₁=2x₂, x₂∈ℤ₊, then 8x₂³+2y₁³=4z₁³⇒4x₂³+y₁³=2z₁³
therefore 2|y₁, let y₁=2y₂, y₂∈ℤ₊, then 4x₂³+8y₂³=2z₁³⇒2x₂³+4y₂³=z₁³
therefore 2|z₁, let z₁=2z₂, z₂∈ℤ₊, then 2x₂³+4y₂³=8z₂³⇒x₂³+2y₂³=4z₂³
A new solution (x₂, y₂, z₂) is obtained where  x₁> x₂, y₁> y₂, z₁> z₂,
Similarly, a sequence of positive integral solutions (xₙ,yₙ,zₙ)n≥1 such that x₁>x₂>x₃>⋯, y₁>y₂>y₃>⋯, z₁>z₂>z₃>⋯.
Since there is no  infinite descending sequence of nonnegative integers, n₁>n₂>⋯, there are no other nonnegative integer solutions.