Задача за числови сравнения - Помощ

[tengam]

Имам нужда от помощ по следната задача (решение):
Да се намерят всички естествени числа n, за които е в сила сравнението: 11n + 8 ≡ 3 (mod 79)

Благодаря!

[nikko]

По алгоритъма на Евклид
79=7.11+2
11=5.2+1, НОД е 1 и изразяваме 1 като линейна комбинация на 11 и 79
2=1.79-7.11
1=11-5.2=11-5(1.79-7.11)=36.11-5.79
Сега да преобразуваме сравнението
[tex]11n\equiv -8+3\equiv -5(\text{mod}\;79)[/tex]
Умнижаваме полученото равенство за 1-цата с -5 и го разглеждаме по модул 79
[tex]-5\equiv74\equiv -5.36.11\equiv -180.11(\text{mod}\;79)[/tex]
-180=-3*79+57
и отговорът е [tex]n\equiv 57(\text{mod}\;79)[/tex]

[tengam]

Много благодаря за бързият отговор и поясненията!