В теории чисел, криптографии и других областях науки часто возникает задача отыскания решений сравнения первой степени вида ах = Ь(тодт). Решение такого сравнения начинается с вычисления NOD(a, т) = = с1. При этом возможны два случая: • если b не кратно d, то у сравнения нет решений; • если b кратно d, то у сравнения существует единственное решение по модулю т / d или, что то же самое, d решений по модулю т. В этом случае в результате сокращения исходного сравнения на d получается сравнение а{х = ^(mod/Wj), где al = a/d,b^=b/dnml = m/ dявляются целыми числами, причем ах и /77[ взаимно просты...

Небольшое дополнение к статье про решение задач на деление с остатком. Более подробное описание, как решать сравнения первой степени. Ссылка на видео.