VCE Stuff > VCE Specialist Mathematics

U1 Linear Diophantine equations

(1/1)

bluechai:
Hello, could someone please explain linear diophantine equations and how to use inspection to find one solution(x0,y0) and input into x=x0+b/d x t and y = etc..

e.g. find all solutions for  22x + 6y = 2


thank u :))

S_R_K:
This is one of those beautiful topics in 1/2 which unfortunately is not continued in 3/4! (Despite having so many interesting connections to geometry and complex numbers) Such a shame...

Firstly, an equation of the form \(ax+by=c\) has integer solutions if and only if HCF(a,b) divides c.

Secondly, to find a solution, we use the Euclidean algorithm to find HCF(a, b) and then "reverse" the algorithm to rewrite HCF(a, b) as a linear combination of a and b.

Here's an example: find all integer solutions to \(27x + 8y =4\).

Firstly, notice by inspection that HCF(27,8) = 1, which is a divisor of 4, so integer solutions exist.

Secondly, we use the Euclidean algorithm to find HCF(a,b):



As we expect, the penultimate remainder is HCF(27,8). We now "reverse" the algorithm to write HCF(27,8) as a linear combination of 27 and 8: (starting from the second last line)



This shows that \(x=3,y=-10\) is a solution to \(27x+10y=1\), but since 1 is a divisor of 4, it also shows that \(x=3n,y=-10n\), where n is any integer multiple of 4, is a solution to \(27x+10y=4\).

To get all integer solutions, we note that \(27x+8y=4\) is the equation of a line with gradient \(-\frac{27}{8}\), which shows that \(x=n(3+8t),y=n(-10-27t)\), where \(t\) is any integer, gives all integer solutions.

The connection between the Euclidean algorithm and integer solutions to diophantine equations is Bezout's identity: that HCF(a,b) = ax + by for some integers x, y. The proof of this is essentially just applying the Euclidean algorithm to a and b.

As for finding solutions by inspection, that is generally just done by a bit of trial and error - ie. for the example you've given, first write it as 11x + 3y = 1, then i'd notice that 2*11 = 22, which is 21 + 1, and 21 = 3*7. So x = 2, y = -7 is a solution.

Navigation

[0] Message Index