Solving a Linear Diophantine Equation in Two Variables by the Euclidean Algorithm

a

173

b

44

show more steps

2

3

4

5

c

30

show solutions

equation

one solution

{x,y}{-15,59}

all solutions

{x,y}{44k-15,59-173k}

equation

ax+by0

solution

{x,y}{44k,-173k}

equation

ax+byc

solution

{x,y}{44k-450,1770-173k}

This Demonstration shows the solutions of Diophantine equations of the form

ax+by=gcd(a,b)

,

ax+by=0

and

ax+by=c

using the Euclidean algorithm.