PAIBOTLearn
Sign inSign up

Linear Diophantine equations

Number theory basics

Japanese school year: Math A

What you learn

You will learn how to find all integer solutions to equations with fewer equations than variables. This approach is widely used in discrete mathematics and problems requiring integer constraints. Mastering the Euclidean algorithm beforehand will make finding particular solutions much easier.

Go to practice

Key points

Use this step to find all integer solutions to ax+by=cax + by = c. Subtract the equation with one known solution (x0,y0)(x_0, y_0) from the original to make the right side 0.

a(x−x0)+b(y−y0)=0a(x - x_0) + b(y - y_0) = 0

This formula expresses all integer solutions of a linear Diophantine equation. Starting from one known solution (x0,y0)(x_0, y_0), any integer kk generates all possible solutions (x,y)(x, y).

x=x0+bk,y=y0−ak(k∈Z)x = x_0 + bk, \quad y = y_0 - ak \quad (k \in \mathbb{Z})

Use this condition to check whether the equation ax+by=cax + by = c has integer solutions. Solutions exist if and only if cc is divisible by the GCD of aa and bb.

gcd⁡(a,b)∣c\gcd(a, b) \mid c

Choose a set to practice.