#13 Chinese Remainder Theorem

The numbers \(x\equiv1\pmod4\) are \(1,5,9,13,17,\ldots\). The first with residue \(2\) modulo \(5\) is \(17\). The answer is \(17\), and all solutions are \(x\equiv17\pmod{20}\).

The numbers are \(4,9,14,19,24,29,34,\ldots\). The first congruent to \(6\) modulo \(7\) is \(34\). Thus \(x\equiv34\pmod{35}\).

Substitute: \(8k+5\equiv7\pmod9\), so \(8k\equiv2\pmod9\). Since \(8\equiv-1\), \(-k\equiv2\), hence \(k\equiv7\pmod9\). Then \(x=8(9t+7)+5=72t+61\). The answer is \(x\equiv61\pmod{72}\).

If \(x\equiv0\pmod4\), then \(x\) is even, so \(x\equiv0\pmod2\). This contradicts \(x\equiv1\pmod2\). No solutions exist.

The conditions mean that \(x-3\) is divisible by both \(5\) and \(7\). Since \(5\) and \(7\) are coprime, \(35\mid x-3\). Hence \(x\equiv3\pmod{35}\).

From \(x\equiv2\pmod4\), check \(2,6,10,14,\ldots\). Residue \(1\) modulo \(3\) first occurs at \(10\), so \(x\equiv10\pmod{12}\). Now \(10,22,34,46,58,\ldots\); the first with residue \(3\) modulo \(5\) is \(58\). Thus \(x\equiv58\pmod{60}\).

We get \(n\equiv1\pmod2\), \(n\equiv1\pmod3\), \(n\equiv2\pmod5\). The number \(7\) works: \(8\) is divisible by \(2\), \(9\) by \(3\), \(10\) by \(5\). Since the moduli are pairwise coprime, all solutions are \(n\equiv7\pmod{30}\), and the smallest positive is \(7\).

The residues \(5\) and \(9\) are both \(1\) modulo \(4\), so the system is compatible. Check \(5,13,21,\ldots\) modulo \(8\); \(21\equiv9\pmod{12}\). The answer is \(x\equiv21\pmod{24}\).

Let \(x=6k+4\). Then \(6k+4\equiv10\pmod{15}\), so \(6k\equiv6\pmod{15}\). Divide by \(3\): \(2k\equiv2\pmod5\), hence \(k\equiv1\pmod5\). Then \(x=6(5t+1)+4=30t+10\). The answer is \(x\equiv10\pmod{30}\).

From \(x\equiv4\pmod6\), \(x\) is even. From \(x\equiv9\pmod{10}\), \(x\) is odd. Contradiction. No solutions exist.

The conditions are equivalent to \(x\equiv-1\pmod3\), \(x\equiv-1\pmod5\), \(x\equiv-1\pmod7\). Thus \(x+1\) is divisible by \(3\cdot5\cdot7=105\). The smallest positive \(x\) is \(104\). All solutions are \(x\equiv104\pmod{105}\).

The first three congruences give \(x\equiv23\pmod{30}\). Check \(23,53,83,\ldots\) modulo \(7\). We have \(53\equiv4\pmod7\). Thus the smallest solution is \(53\), and all solutions are \(x\equiv53\pmod{210}\).

Let \(d=\gcd(m,n)\). If a solution \(x\) exists, then \(x-a\) is divisible by \(m\), and \(x-b\) is divisible by \(n\), so both differences are divisible by \(d\). Hence \(a-b=(x-b)-(x-a)\) is divisible by \(d\).

Conversely, suppose \(d\mid a-b\). Look for \(x=a+mt\). We need \(a+mt\equiv b\pmod n\), i.e. \(mt\equiv b-a\pmod n\). This linear congruence is solvable because \(\gcd(m,n)=d\mid b-a\). Therefore the system has a solution.

Take \(n=60\). Then \(n+2=62\) is divisible by \(2\), \(n+3=63\) by \(3\), \(n+4=64\) by \(4\), and \(n+5=65\) by \(5\). All these numbers are larger than the corresponding divisors, so they are composite.

Consider \((k+1)!+2,(k+1)!+3,\ldots,(k+1)!+(k+1)\). For each \(r=2,3,\ldots,k+1\), the number \((k+1)!+r\) is divisible by \(r\), because \((k+1)!\) is divisible by \(r\). It is larger than \(r\), so it is composite. There are \(k\) such numbers.

The system is equivalent to \(n\equiv4\pmod5\), \(n\equiv5\pmod7\), \(n\equiv8\pmod{11}\). One solution is \(n=19\). Since the moduli are pairwise coprime, all solutions are \(n\equiv19\pmod{385}\).

We get \(n\equiv2\pmod3\), \(n\equiv3\pmod5\), \(n\equiv4\pmod7\). Checking or merging step by step gives \(n=53\). All solutions are \(n\equiv53\pmod{105}\), so the smallest positive \(n\) is \(53\).

First solve \(x\equiv3\pmod4\), \(x\equiv7\pmod9\). The sequence \(7,16,25,34,43,\ldots\) modulo \(9\) first has residue \(3\) modulo \(4\) at \(7\). Thus \(x\equiv7\pmod{36}\). Now solve \(x=36k+7\equiv12\pmod{25}\). We get \(36k\equiv5\pmod{25}\), i.e. \(11k\equiv5\pmod{25}\). The inverse of \(11\) is \(16\), so \(k\equiv80\equiv5\pmod{25}\). Hence \(x=36(25t+5)+7=900t+187\). The answer is \(x\equiv187\pmod{900}\).

From \(x\equiv3\pmod8\): \(3,11,19,27,35,43,\ldots\). Residue \(1\) modulo \(5\) first occurs at \(11\), so \(x\equiv11\pmod{40}\). Now \(11,51,91,131,171,211,\ldots\); the first with residue \(4\) modulo \(9\) is \(211\). Thus \(x\equiv211\pmod{360}\).

The numbers \(2,9,16,23,30,37,44,51,58,\ldots\) have residue \(5\) modulo \(9\) at \(x=23\). Thus \(x\equiv23\pmod{63}\). Check \(23,86,149,212,275,338,\ldots\); \(338\equiv8\pmod{11}\). The answer is \(x\equiv338\pmod{693}\).

By the Chinese Remainder Theorem, there is a solution \(x_0\) modulo \(M=m_1m_2\cdots m_s\). Then every number \(x=x_0+kM\), where \(k\in\mathbb Z\), has the same residues modulo all \(m_i\). Since \(k\) can be chosen in infinitely many ways, there are infinitely many solutions.

The conditions \(d_i\mid n+i\) are equivalent to \(n\equiv-i\pmod{d_i}\). Since the moduli \(d_i\) are pairwise coprime, CRT gives a solution \(n_0\) modulo \(D=d_1\cdots d_k\). Then all \(n=n_0+tD\) also work. For \(t=0,1,2,\ldots\), this gives infinitely many solutions.

We need to solve \(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}\). The moduli are pairwise coprime, so CRT gives a solution. For any such \(n\), the numbers \(n+1,\ldots,n+6\) have the required divisors. Taking a sufficiently large positive solution makes them positive and larger than their divisors.

Choose distinct primes \(p_1,\ldots,p_k\). Consider the system \(n\equiv-1\pmod{p_1^2}\), \(n\equiv-2\pmod{p_2^2}\), \(\ldots\), \(n\equiv-k\pmod{p_k^2}\). The moduli \(p_i^2\) are pairwise coprime, so CRT gives a solution \(n_0\). Then for each \(i\), the number \(n_0+i\) is divisible by \(p_i^2\), so it is not squarefree. Adding multiples of \(p_1^2\cdots p_k^2\) to \(n_0\), we can choose \(n\) positive. Hence such \(k\) consecutive numbers exist.