BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Saturday , July 22 2017
Home / Elementary Number Theory / Diophantine equation

# Diophantine equation

Diophantine equation: Any linear equation in two variables having integral coefficient can be put in the form

ax + by = c ——————————–(i)

where a, b, c are given integers. We consider the problem of identifying all solutions of two equation in which x and y are integers. If a = b = c = 0 then every pair (x, y) of integers is a solution of (i), where if a = b = 0.

Condition for solvability: The Diophantine equation ax + by + c admits a solution if and only if d\c, where d = gcd(a, b). We know that there are integers r and s for which a = dr and b = ds. If a solution of ax + by = c exists , so that ax0 + byo = c for suitable x0 and yo, then

c = ax0 + byo = dr x0 + ds0 = d(rx0 + sy0), which simply says that d\c.

Conversely assume that d\c, say c = dt. Since d = gcd(a, b) there exist integers x0 and y0 satisfying d = ax0 + b + byo.

When this relativity is multiplied by t, we get

c = dt = (ax0 + by0)t = a (tx0) + b(ty0)

Hence the Diophantine equation ax + by = c has x = tx0 and y = ty0 as a particular solution.

Theorem: The linear Diophantine equation ax + by = c has a solution if and only if d\c, where d = gcd(a, b). If x0, y0 is any particular solution of this equation, then all other solutions are given by

x = x0 + (b/d)t

y = y0 – (a/d)t

Where t is an arbitrary integer.

Proof: To established the second assertion of the theorem, let us suppose that a solution x0, y0 of the given equation is known. If xʹ, yʹ is any other solution, then ax0 + by0 = c = axʹ + byʹ; which is equivalent to

a(xʹ – x0) = b(y0 – yʹ)

Since d = gcd(a, b), there exist relatively prime integers r and s such that a = dr, b = ds. Substituting these values into the last written equation and cancelling the common factor d, we find that

r(xʹ – x0) = s(y0 – yʹ)

This situation is now this: r\s(y0-yʹ), with gcd(r, s) =1.

Using Euclid’s lemma, it must be the case that r\(y0-yʹ); or, in other words, y0 – yʹ = rt for some integer t. Substituting, we obtain

xʹ – x0 = st

This leads us to the formulas

xʹ = x0 + st = x0 + (b/d)t

yʹ = y0 – rt = y0 – (a/d)t

It is easy to see that these values satisfying the Diophantine equation regardless of the choice of the integers; for

axʹ + byʹ = a[x0 + (b/d)t] + b[y0 – (a/d)t] = (ax0 + by0) + (ab/d – ab/d) = c + t.0 = c

Thus there are an infinite number of solutions of the given equation, one for each value of t.

## Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...