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