#13 Китайская теорема об остатках

Числа \(x\equiv1\pmod4\): \(1,5,9,13,17,\ldots\). Первое из них, дающее остаток \(2\) по модулю \(5\), равно \(17\). Ответ: \(17\), все решения \(x\equiv17\pmod{20}\).

Числа \(4,9,14,19,24,29,34,\ldots\). Первое, сравнимое с \(6\) по модулю \(7\), равно \(34\). Ответ: \(x\equiv34\pmod{35}\).

Подставим: \(8k+5\equiv7\pmod9\), значит, \(8k\equiv2\pmod9\). Так как \(8\equiv-1\), получаем \(-k\equiv2\), то есть \(k\equiv7\pmod9\). Тогда \(x=8(9t+7)+5=72t+61\). Ответ: \(x\equiv61\pmod{72}\).

Если \(x\equiv0\pmod4\), то \(x\) четно, то есть \(x\equiv0\pmod2\). Это противоречит \(x\equiv1\pmod2\). Решений нет.

Условия означают, что \(x-3\) делится и на \(5\), и на \(7\). Так как \(5\) и \(7\) взаимно просты, \(35\mid x-3\). Поэтому \(x\equiv3\pmod{35}\).

Из \(x\equiv2\pmod4\) проверяем \(2,6,10,14,\ldots\). Остаток \(1\) по модулю \(3\) впервые дает \(10\), значит, \(x\equiv10\pmod{12}\). Теперь \(10,22,34,46,58,\ldots\); первое число с остатком \(3\) по модулю \(5\) равно \(58\). Ответ: \(x\equiv58\pmod{60}\).

Получаем \(n\equiv1\pmod2\), \(n\equiv1\pmod3\), \(n\equiv2\pmod5\). Число \(7\) подходит: \(8\) делится на \(2\), \(9\) на \(3\), \(10\) на \(5\). Так как модули попарно взаимно просты, все решения \(n\equiv7\pmod{30}\), и наименьшее положительное \(n=7\).

Остатки \(5\) и \(9\) оба равны \(1\) по модулю \(4\), значит, система совместна. Проверяем числа \(5,13,21,\ldots\) по модулю \(8\); \(21\equiv9\pmod{12}\). Ответ: \(x\equiv21\pmod{24}\).

Пусть \(x=6k+4\). Тогда \(6k+4\equiv10\pmod{15}\), то есть \(6k\equiv6\pmod{15}\). Делим на \(3\): \(2k\equiv2\pmod5\), значит, \(k\equiv1\pmod5\). Тогда \(x=6(5t+1)+4=30t+10\). Ответ: \(x\equiv10\pmod{30}\).

Из \(x\equiv4\pmod6\) следует, что \(x\) четно. Из \(x\equiv9\pmod{10}\) следует, что \(x\) нечетно. Противоречие. Решений нет.

Условия равносильны \(x\equiv-1\pmod3\), \(x\equiv-1\pmod5\), \(x\equiv-1\pmod7\). Поэтому \(x+1\) делится на \(3\cdot5\cdot7=105\). Наименьшее положительное \(x=104\). Все решения: \(x\equiv104\pmod{105}\).

Первые три сравнения дают \(x\equiv23\pmod{30}\). Проверяем \(23,53,83,\ldots\) по модулю \(7\). \(53\equiv4\pmod7\). Значит, наименьшее решение \(53\), а все решения \(x\equiv53\pmod{210}\).

Пусть \(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\). Значит, система имеет решение.

Возьмем \(n=60\). Тогда \(n+2=62\) делится на \(2\), \(n+3=63\) делится на \(3\), \(n+4=64\) делится на \(4\), \(n+5=65\) делится на \(5\). Все эти числа больше соответствующих делителей, значит, составные.

Рассмотрим числа \((k+1)!+2,(k+1)!+3,\ldots,(k+1)!+(k+1)\). Для каждого \(r=2,3,\ldots,k+1\) число \((k+1)!+r\) делится на \(r\), потому что \((k+1)!\) делится на \(r\). Оно больше \(r\), значит, составное. Таких чисел \(k\).

Система равносильна \(n\equiv4\pmod5\), \(n\equiv5\pmod7\), \(n\equiv8\pmod{11}\). Одно решение \(n=19\). Так как модули попарно взаимно просты, все решения имеют вид \(n\equiv19\pmod{385}\).

Получаем \(n\equiv2\pmod3\), \(n\equiv3\pmod5\), \(n\equiv4\pmod7\). Проверка или последовательное склеивание дает \(n=53\). Все решения \(n\equiv53\pmod{105}\), поэтому наименьшее положительное \(n=53\).

Сначала \(x\equiv3\pmod4\), \(x\equiv7\pmod9\). Число \(7\) по модулю \(9\) дает последовательность \(7,16,25,34,43,\ldots\); первое с остатком \(3\) по модулю \(4\) равно \(7\). Значит, \(x\equiv7\pmod{36}\). Теперь решаем \(x=36k+7\equiv12\pmod{25}\). Получаем \(36k\equiv5\pmod{25}\), то есть \(11k\equiv5\pmod{25}\). Обратный к \(11\) равен \(16\), значит, \(k\equiv80\equiv5\pmod{25}\). Тогда \(x=36(25t+5)+7=900t+187\). Ответ: \(x\equiv187\pmod{900}\).

Из \(x\equiv3\pmod8\): \(3,11,19,27,35,43,\ldots\). Остаток \(1\) по модулю \(5\) впервые дает \(11\), значит, \(x\equiv11\pmod{40}\). Теперь \(11,51,91,131,171,211,\ldots\); первое число с остатком \(4\) по модулю \(9\) равно \(211\). Ответ: \(x\equiv211\pmod{360}\).

Числа \(2,9,16,23,30,37,44,51,58,\ldots\) дают остаток \(5\) по модулю \(9\) при \(x=23\). Значит, \(x\equiv23\pmod{63}\). Проверяем \(23,86,149,212,275,338,\ldots\); \(338\equiv8\pmod{11}\). Ответ: \(x\equiv338\pmod{693}\).

По китайской теореме об остатках существует решение \(x_0\) по модулю \(M=m_1m_2\cdots m_s\). Тогда каждое число \(x=x_0+kM\), где \(k\in\mathbb Z\), имеет те же остатки по всем модулям \(m_i\). Так как \(k\) можно выбирать бесконечно многими способами, решений бесконечно много.

Условия \(d_i\mid n+i\) равносильны \(n\equiv-i\pmod{d_i}\). Так как модули \(d_i\) попарно взаимно просты, по CRT существует решение \(n_0\) по модулю \(D=d_1\cdots d_k\). Тогда все \(n=n_0+tD\) тоже подходят. При \(t=0,1,2,\ldots\) получаем бесконечно много решений.

Нужно решить систему \(n\equiv-1\pmod5\), \(n\equiv-2\pmod7\), \(n\equiv-3\pmod{11}\), \(n\equiv-4\pmod{13}\), \(n\equiv-5\pmod{17}\), \(n\equiv-6\pmod{19}\). Модули попарно взаимно просты, поэтому по CRT решение существует. Для любого такого \(n\) числа \(n+1,\ldots,n+6\) имеют требуемые делители. Взяв достаточно большое положительное решение, получаем натуральные числа больше своих делителей.

Выберем попарно различные простые \(p_1,\ldots,p_k\). Рассмотрим систему \(n\equiv-1\pmod{p_1^2}\), \(n\equiv-2\pmod{p_2^2}\), \(\ldots\), \(n\equiv-k\pmod{p_k^2}\). Модули \(p_i^2\) попарно взаимно просты, поэтому по CRT существует решение \(n_0\). Тогда для каждого \(i\) число \(n_0+i\) делится на \(p_i^2\), то есть не является свободным от квадратов. Прибавляя к \(n_0\) кратные произведения \(p_1^2\cdots p_k^2\), можно выбрать положительное \(n\). Значит, такие \(k\) последовательных чисел существуют.