# Linear Diophantine Equations

A Diophantine equation is defined as the equation where the solutions are limited to positive integers (for some cases, all integers).

A **linear Diophantine equation** is an equation of the form \(ax + by = c,\) where the degree of each variables is exactly 1. This has integral solutions if and only if \(\gcd(a, b)|c.\) (This can be verified by Bezout's lemma.) Otherwise, it doesn't.

For any linear Diophantine equation (for 2-variables), the integral solutions are given by the following form:

\[x = x(0) + (b/d)t ~\text{ and }~ y = y(0) - (a/d)t,\]

where \((x(0), y(0))\) is any integral solution (that you find trivially for some), \(a\) and \(b\) are the coefficients of the variables, \(d = \gcd(a, b),\) and \(t\) is an assigned parameter.

There exists another solution \((x(0), y(0))\) for the Diophantine equation \(ax + by = c.\) We also divide both sides of the whole equation by \(d = \gcd(a,b).\) This implies \[(a/d)x + (b/d)y = (a/d)x(0) + (b/d)y(0) (a/d)(x - x(0)) = (b/d)(y(0) - y),\] which is equivalent to \[(d/b)(x - x(0)) = (d/a)(y(0) - y).\] Here, we set a parameter \(t\) to equate the two quantities stated above. Hence, \[(d/b)(x - x(0)) = (d/a)(y(0) - y) = t,\] which further implies that \[x = x(0) + (b/d)t ~\text{ and }~ y = y(0) - (a/d)t.\ _\square\]

(11\(^\text{th}\) PMO 2008 - 2009) Find the number of positive integral solutions to the Diophantine equation \(2x + 5y = 100.\)

Solution 1(Trivial): Use the formula above where \(x = x(0) + 5t\) and \(y = y(0) - 2t.\) Since \((0, 20)\) is one solution to the equation, we can let \(x = 5t\) and \(y = 20 - 2t.\) In this problem, we consider only positive integers, so we set \(x\) and \(y > 0\) giving \(5a > 0 \Rightarrow a > 0\) and \(20 - 2a > 0 \Rightarrow 10 > a,\) implying that the values of \(a\) must be in the interval \((0, 10).\) This gives 9 positive integral solutions for the said equation. \(_\square\)

Solution 2: Consider modulo 5 for the Diophantine equation. This implies that \(2x + 5y \equiv 100 \pmod 5\) and furthermore, \(2x \equiv 0 \pmod 5.\) In this simplified congruence, this will have a solution if \(x = 5a\) (parameter \(a\)). Plugging this to the original equation gives \(10a + 5y = 100 \Rightarrow 2a + y = 20 \Rightarrow y = 20 - 2a.\) In this problem, we consider only positive integers, so we set \(x, y > 0\) giving \(5a > 0 \Rightarrow a > 0\) and \(20 - 2a > 0 \Rightarrow 10 > a,\) implying that the values of \(a\) must be in the interval \((0, 10).\) This gives 9 positive integral solutions for the said equation. \(_\square\)

**Cite as:**Linear Diophantine Equations.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/linear-diophantine-equations/