#9 Китайская теорема об остатках и построения

Подставим: \(9t+4\equiv 7\pmod {11}\), то есть \(9t\equiv 3\pmod {11}\). Так как \(9^{-1}\equiv 5\pmod {11}\), имеем \(t\equiv 15\equiv 4\pmod {11}\). Поэтому \(x=9(11s+4)+4=99s+40\). Ответ: \(x\equiv 40\pmod {99}\).

Из первых двух условий: \(x=4a+1\), \(4a+1\equiv 2\pmod 5\), значит \(4a\equiv 1\), \(a\equiv 4\pmod 5\). Тогда \(x\equiv 17\pmod {20}\). Теперь \(20b+17\equiv 3\pmod 7\), то есть \(6b\equiv 0\pmod 7\), значит \(b\equiv 0\pmod 7\). Наименьшее положительное решение \(x=17\).

Если \(x\equiv 2\pmod 6\), то \(x\equiv 2\pmod 3\). Если \(x\equiv 3\pmod 9\), то \(x\equiv 0\pmod 3\). Одно и то же число не может иметь два разных остатка по модулю \(3\). Значит решений нет.

Общий делитель \(12\) и \(18\) равен \(6\), а \(17-5=12\) делится на \(6\), значит система совместна. Пусть \(x=12t+5\). Тогда \(12t+5\equiv 17\pmod {18}\), то есть \(12t\equiv 12\pmod {18}\). Делим на \(6\): \(2t\equiv 2\pmod 3\), значит \(t\equiv 1\pmod 3\). Поэтому \(x=12(3s+1)+5=36s+17\). Ответ: \(x\equiv 17\pmod {36}\).

Условия означают \(N\equiv -1\pmod 3\), \(N\equiv -1\pmod 5\), \(N\equiv -1\pmod 7\). Значит \(N\equiv -1\pmod {105}\). Например, \(N=104\).

Нужно \(N\equiv 3\pmod 4\), \(N\equiv 3\pmod 5\), \(N\equiv 6\pmod 9\). Первые два условия дают \(N\equiv 3\pmod {20}\). Пусть \(N=20t+3\). Тогда \(20t+3\equiv 6\pmod 9\), то есть \(2t\equiv 3\pmod 9\). Обратный к \(2\) по модулю \(9\) равен \(5\), значит \(t\equiv 15\equiv 6\pmod 9\). Наименьшее \(N=20\cdot 6+3=123\).

Из \(4n+1\equiv 0\pmod 9\) получаем \(4n\equiv 8\), значит \(n\equiv 2\pmod 9\). Из \(5n-2\equiv 0\pmod {11}\) получаем \(5n\equiv 2\), а \(5^{-1}\equiv 9\pmod {11}\), значит \(n\equiv 18\equiv 7\pmod {11}\). Решаем \(n=9t+2\), \(9t+2\equiv 7\pmod {11}\), то есть \(9t\equiv 5\). Так как \(9^{-1}\equiv 5\), \(t\equiv 25\equiv 3\pmod {11}\). Ответ: \(n\equiv 29\pmod {99}\).

Зададим \(N+1\equiv 0\pmod 2\), \(N+2\equiv 0\pmod 3\), \(N+3\equiv 0\pmod 5\), \(N+4\equiv 0\pmod 7\). То есть \(N\equiv 1\pmod 2\), \(N\equiv 1\pmod 3\), \(N\equiv 2\pmod 5\), \(N\equiv 3\pmod 7\). По CRT есть решение по модулю \(210\). Одно решение \(N=157\). Тогда \(158,159,160,161\) делятся соответственно на \(2,3,5,7\) и больше этих делителей, значит составные.

Имеем \(385=5\cdot 7\cdot 11\). По каждому из модулей \(5,7,11\) сравнение \(x^2\equiv 1\) имеет два решения: \(x\equiv 1\) и \(x\equiv -1\). Модули попарно взаимно просты, значит решения комбинируются независимо. Всего \(2^3=8\) решений по модулю \(385\).

Получаем четыре системы. \((1,1)\) даёт \(x\equiv 1\). \((-1,-1)\) даёт \(x\equiv -1\equiv 34\). Для \(x\equiv 1\pmod 5\), \(x\equiv -1\pmod 7\): числа \(1,6,11,16,21,26,31\), подходит \(6\). Для \(x\equiv -1\pmod 5\), \(x\equiv 1\pmod 7\): подходит \(29\). Ответ: \(1,6,29,34\pmod {35}\).

Пусть \(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\) можно выбрать. Значит система совместна.

Нужно решить систему \(N\equiv -1\pmod 3\), \(N\equiv -2\pmod 5\), \(N\equiv -3\pmod 7\), \(N\equiv -4\pmod {11}\), \(N\equiv -5\pmod {13}\). Модули попарно взаимно просты, значит по CRT есть решение по модулю \(M=3\cdot 5\cdot 7\cdot 11\cdot 13\). Если \(N_0\) — одно решение, то все \(N=N_0+tM\) тоже решения. Таких \(N\) бесконечно много.

Потребуем \(n\equiv 0\pmod 5\), \(n+2\equiv 0\pmod 7\), \(n+6\equiv 0\pmod {11}\). Это система \(n\equiv 0\pmod 5\), \(n\equiv 5\pmod 7\), \(n\equiv 5\pmod {11}\). Модули взаимно просты, поэтому есть решение \(n_0\) по модулю \(385\). Все \(n=n_0+385t\) имеют те же делимости. При достаточно больших \(t\) числа \(n,n+2,n+6\) больше соответствующих делителей, значит составные. Таких \(t\) бесконечно много.

Модули \(8,3,5,7\) попарно взаимно просты. По модулю \(8\) все нечётные остатки \(1,3,5,7\) дают квадрат \(1\), значит \(4\) решения. По каждому из модулей \(3,5,7\) есть по \(2\) решения: \(\pm 1\). Всего по CRT получаем \(4\cdot 2\cdot 2\cdot 2=32\) решения.

Для \(k=2\) это обычная CRT. Пусть утверждение верно для \(k-1\) модулей. Тогда первые \(k-1\) условий дают одно сравнение \(x\equiv r\pmod M\), где \(M=m_1\cdots m_{k-1}\). Так как \(m_k\) взаимно просто с каждым \(m_i\), имеем \(\gcd(M,m_k)=1\). По CRT система \(x\equiv r\pmod M\), \(x\equiv r_k\pmod {m_k}\) совместна. Индукция завершена.

Пусть \(A=(k+1)!\). Тогда числа \(A+2,A+3,\ldots,A+(k+1)\) образуют \(k\) последовательных чисел. Для каждого \(j=2,\ldots,k+1\) число \(A+j\) делится на \(j\), потому что \(A\) делится на \(j\). Кроме того, \(A+j>j\), значит \(A+j\) составное. Получен нужный блок.

Выберем различные простые \(p_1,\ldots,p_k>k\). Рассмотрим систему \(N+i\equiv 0\pmod {p_i}\) для \(i=1,\ldots,k\), то есть \(N\equiv -i\pmod {p_i}\). Модули попарно взаимно просты, поэтому по CRT есть решение \(N_0\) по модулю \(P=p_1\cdots p_k\). Все числа \(N=N_0+tP\) также подходят. При достаточно большом \(t\) имеем \(N+i>p_i\), значит каждое \(N+i\) составное и имеет назначенный простой делитель \(p_i>k\).

Так как \(m_i>1\), можно выбрать остаток \(b_i\), отличный от \(a_i\) по модулю \(m_i\). По CRT существует \(x_0\), такое что \(x_0\equiv b_i\pmod {m_i}\) для всех \(i\). Тогда все числа \(x=x_0+tM\), где \(M=m_1\cdots m_k\), имеют те же остатки по всем модулям. Следовательно, они избегают всех запрещённых классов, и таких чисел бесконечно много.

Выберем попарно различные простые \(p_1,\ldots,p_k\), настолько большие, что \(p_i>|a_i-a_j|\) для всех \(i,j\), и \(p_i>0\). Система \(N\equiv -a_i\pmod {p_i}\) совместна по CRT. Пусть \(N_0\) — решение, \(P=p_1\cdots p_k\). Тогда \(N=N_0+tP\) сохраняет все делимости \(p_i\mid N+a_i\). При достаточно больших \(t\) все \(N+a_i\) положительны и больше \(p_i\), значит составные. Таких \(t\) бесконечно много.

Для нечётного простого \(p\) сравнение \(u^2\equiv 1\pmod p\) имеет только решения \(u\equiv \pm 1\pmod p\), потому что \((u-1)(u+1)\equiv 0\pmod p\). Поэтому требование “не сравнимо с \(\pm 1\) ни по одному модулю \(p_i\)” несовместимо с \(x^2\equiv 1\pmod {p_i}\) для любого нечётного простого. Значит такого \(x\) не существует ни при каких \(p_i\). Ответ: утверждение неверно.