Задача
NT-B2-M09-P011 Критерий совместимости
Пусть \(m,n,a,b\) — целые числа, \(m,n>0\). Докажите, что система \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) имеет решение тогда и только тогда, когда \(\gcd(m,n)\mid a-b\).
Для обратного направления запишите \(x=a+mt\) и сократите общий делитель.
Пусть \(d=\gcd(m,n)\). Если \(x\) — решение, то \(m\mid x-a\), \(n\mid x-b\), поэтому \(d\mid (x-a)\) и \(d\mid (x-b)\), значит \(d\mid a-b\). Обратно, пусть \(d\mid a-b\). Пишем \(m=dm_1\), \(n=dn_1\), \(\gcd(m_1,n_1)=1\). Ищем \(x=a+mt\). Нужно \(a+d m_1t\equiv b\pmod {dn_1}\), то есть \(m_1t\equiv \frac{b-a}{d}\pmod {n_1}\). Так как \(m_1\) взаимно просто с \(n_1\), обратный элемент существует, и \(t\) можно выбрать. Значит система совместна.
Теоретическая задача, вдохновлённая локальным сборником; нужна для строгого использования не взаимно простых модулей.