Toolkit 111: Linear Diophantine Equations

Linear Diophantine Equations

x,y\in\mathbb Z:\qquad ax+by=n

Example:

15x+10y=99

Since

\gcd(15,10)=5\nmid 99

there is no answer.

15x+10y=100,\qquad x,y\in\mathbb Z

\gcd(15,10)=5\mid100

1) Divide both sides by gcd(15,10).

3x+2y=20

2) Try to find one x and y that satisfy the equation.

3(6)+2(1)=20

x_0=6,\qquad y_0=1

or

3(1)+2(-1)=1\Longrightarrow3(20)+2(-20)=20

General Solution

\text{Let }x_0=1,\qquad y_0=-1

x=x_0+2k,\qquad y=y_0-3k

x=1+2k,\qquad y=-1-3k

3(1+2k)+2(-1-3k)=20

In General

ax+by=n

1) Check gcd(a,b) | n.

2) Divide both sides by gcd(a,b).

a'x+b'y=n'

3) Find one answer that satisfies

a'x_0+b'y_0=1

4) Multiply by n'.

a'(n'x_0)+b'(n'y_0)=n'\Longrightarrow a'x_1+b'y_1=n'

(If finding one example to satisfy a'x+b'y=n' is easy, skip 3rd step.)

5) General Answers:

x=x_1+b'k,\qquad y=y_1-a'k

(coefficient of k cancel out)

\begin{aligned} a'(x_1+b'k)+b'(y_1-a'k) &=a'x_1+a'b'k+b'y_1-b'a'k\\ &=a'x_1+b'y_1=n' \end{aligned}

Reducing Coefficients (Scaling Trick)

25x-18y=10,\qquad x,y\in\mathbb Z

Solution 1

25x=18y+10=2(9y+5)

2\mid25x\Longrightarrow2\mid x\Longrightarrow x=2x'

18y=25x-10=5(5x-2)

5\mid18y\Longrightarrow5\mid y\Longrightarrow y=5y'

25(2x')-18(5y')=10

5x'-9y'=1

5(2)-9(1)=1

5(2+9k)-9(1+5k)=1

x'=2+9k,\qquad y'=1+5k,\qquad k\in\mathbb Z

x=2x'=4+18k,\qquad y=5y'=5+25k

Solution 2

25x-18y=10

x_0=4,\qquad y_0=5

25(4+18k)-18(5+25k)=10

coefficients of k cancel out.

x=4+18k,\qquad y=5+25k