Задача
NT-B1-M04-P021 Критерий совместимости двух сравнений
#21
★★★★☆ Уровень 4 из 5
Докажите: система \(x\equiv r\pmod m\), \(x\equiv s\pmod n\) имеет решение тогда и только тогда, когда \(r\equiv s\pmod{\gcd(m,n)}\).
Необходимость следует из того, что \(x-r\) делится на \(m\), а \(x-s\) делится на \(n\). Для достаточности сведите к линейному сравнению.
Пусть \(d=\gcd(m,n)\). Если решение \(x\) есть, то \(x-r\) делится на \(m\), а \(x-s\) делится на \(n\), значит, оба делятся на \(d\). Тогда \(r-s=(x-s)-(x-r)\) делится на \(d\).
Обратно, пусть \(d\mid r-s\). Ищем \(x=r+mk\). Нужно \(r+mk\equiv s\pmod n\), то есть \(mk\equiv s-r\pmod n\). Это линейное сравнение имеет решение ровно потому, что \(\gcd(m,n)=d\mid s-r\). Значит, исходная система совместна.
Это главный теоретический результат для не взаимно простых модулей.