MathGoldMedalist
Sign InRegister

Toolkit 111

Linear Diophantine Equations

Linear Diophantine Equations

x,y∈Z:ax+by=nx,y\in\mathbb{Z}:\quad ax+by=n

Example:

15x+10y=9915x+10y=99

Since

gcd⁡(15,10)=5∤99\gcd(15,10)=5\nmid99

there is no answer.

15x+10y=100x,y∈Z15x+10y=100\qquad x,y\in\mathbb{Z}
gcd⁡(15,10)=5∣100\gcd(15,10)=5\mid100

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

3x+2y=203x+2y=20

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

3(6)+2(1)=203(6)+2(1)=20
x0=6,y0=1x_0=6,\qquad y_0=1

or

3(1)+2(−1)=1⟹3(20)+2(−20)=203(1)+2(-1)=1\Longrightarrow3(20)+2(-20)=20

General Solution

Let x0=1,y0=−1Let\ x_0=1,\qquad y_0=-1
x=x0+2k,y=y0−3kx=x_0+2k,\qquad y=y_0-3k
x=1+2k,y=−1−3kx=1+2k,\qquad y=-1-3k
3(1+2k)+2(−1−3k)=203(1+2k)+2(-1-3k)=20

In General

ax+by=nax+by=n

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

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

a′x+b′y=n′a'x+b'y=n'

3) Find one answer that satisfies

a′x0+b′y0=1a'x_0+b'y_0=1
4) a′(n′x0)+b′(n′y0)=n′⟹a′x1+b′y1=n′4)\ 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=x1+b′k,y=y1−a′kx=x_1+b'k,\qquad y=y_1-a'k

(coefficient of k cancel out)

a′(x1+b′k)+b′(y1−a′k)a'(x_1+b'k)+b'(y_1-a'k)
=a′x1+a′b′k+b′y1−b′a′k=a'x_1+a'b'k+b'y_1-b'a'k
=a′x1+b′y1=n′=a'x_1+b'y_1=n'

Reducing Coefficients (Scaling Trick)

25x−18y=10,x,y∈Z25x-18y=10,\qquad x,y\in\mathbb{Z}

Solution 1

25x=18y+10=2(9y+5)25x=18y+10=2(9y+5)
2∣25x⟹2∣x⟹x=2x′2\mid25x\Longrightarrow2\mid x\Longrightarrow x=2x'
18y=25x−10=5(5x−2)18y=25x-10=5(5x-2)
5∣18y⟹5∣y⟹y=5y′5\mid18y\Longrightarrow5\mid y\Longrightarrow y=5y'
25(2x′)−18(5y′)=1025(2x')-18(5y')=10
5x′−9y′=15x'-9y'=1
5(2)−9(1)=15(2)-9(1)=1
5(2+9k)−9(1+5k)=15(2+9k)-9(1+5k)=1
x′=2+9k,y′=1+5k,k∈Zx'=2+9k,\qquad y'=1+5k,\qquad k\in\mathbb{Z}
x=2x′=4+18k,y=5y′=5+25kx=2x'=4+18k,\qquad y=5y'=5+25k

Solution 2

25x−18y=1025x-18y=10
x0=4,y0=5x_0=4,\qquad y_0=5
25(4+18k)−18(5+25k)=1025(4+18k)-18(5+25k)=10

coefficients of k cancel out.

x=4+18k,y=5+25kx=4+18k,\qquad y=5+25k
Back to Toolkit