Задача
NT-B1-M04-P013 Критерий линейного сравнения
#13
★★★☆☆ Уровень 3 из 5
Докажите, что сравнение \(ax\equiv b\pmod m\) имеет решение тогда и только тогда, когда \(\gcd(a,m)\mid b\).
Перепишите сравнение как \(ax-b=my\).
Сравнение эквивалентно уравнению \(ax-my=b\) в целых \(x,y\). Все числа вида \(ax-my\) делятся на \(d=\gcd(a,m)\), значит, необходимо \(d\mid b\). Обратно, если \(d\mid b\), то по тождеству Безу существуют \(u,v\), для которых \(au+mv=d\). Умножив на \(\frac bd\), получаем представление \(b\) в виде \(aX+mY\), то есть решение сравнения.
Это теоретический центр модуля.