Линеарна Диофантова једначина

има решења ако и само ако, где јенајвећи заједнички делилац бројеваи.
Својства релације конгруенције у скупу

где се једно посебно (партикуларно) решењеједначинедобија Еуклидовим алгоритмом.