Линеарна Диофантова једначина
има решења ако и само ако
, где је
највећи заједнички делилац бројева
и
.
Својства релације конгруенције у скупу
где се једно посебно (партикуларно) решење
једначине
добија Еуклидовим алгоритмом.
Сва решења једначине
су облика
где је
- узајамно прости.