#9 Chinese Remainder Theorem and Construction

Substitute: \(9t+4\equiv 7\pmod {11}\), so \(9t\equiv 3\pmod {11}\). Since \(9^{-1}\equiv 5\pmod {11}\), \(t\equiv 15\equiv 4\pmod {11}\). Thus \(x=9(11s+4)+4=99s+40\). The answer is \(x\equiv 40\pmod {99}\).

From the first two conditions: \(x=4a+1\), \(4a+1\equiv 2\pmod 5\), so \(4a\equiv 1\), \(a\equiv 4\pmod 5\). Hence \(x\equiv 17\pmod {20}\). Now \(20b+17\equiv 3\pmod 7\), or \(6b\equiv 0\pmod 7\), so \(b\equiv 0\pmod 7\). The least positive solution is \(x=17\).

If \(x\equiv 2\pmod 6\), then \(x\equiv 2\pmod 3\). If \(x\equiv 3\pmod 9\), then \(x\equiv 0\pmod 3\). The same integer cannot have two different residues modulo \(3\). Therefore there are no solutions.

The common divisor of \(12\) and \(18\) is \(6\), and \(17-5=12\) is divisible by \(6\), so the system is compatible. Let \(x=12t+5\). Then \(12t+5\equiv 17\pmod {18}\), so \(12t\equiv 12\pmod {18}\). Divide by \(6\): \(2t\equiv 2\pmod 3\), hence \(t\equiv 1\pmod 3\). Therefore \(x=12(3s+1)+5=36s+17\). The answer is \(x\equiv 17\pmod {36}\).

The conditions mean \(N\equiv -1\pmod 3\), \(N\equiv -1\pmod 5\), \(N\equiv -1\pmod 7\). Hence \(N\equiv -1\pmod {105}\). For example, \(N=104\).

We need \(N\equiv 3\pmod 4\), \(N\equiv 3\pmod 5\), \(N\equiv 6\pmod 9\). The first two conditions give \(N\equiv 3\pmod {20}\). Let \(N=20t+3\). Then \(20t+3\equiv 6\pmod 9\), so \(2t\equiv 3\pmod 9\). The inverse of \(2\) modulo \(9\) is \(5\), hence \(t\equiv 15\equiv 6\pmod 9\). The least \(N\) is \(20\cdot 6+3=123\).

From \(4n+1\equiv 0\pmod 9\), \(4n\equiv 8\), so \(n\equiv 2\pmod 9\). From \(5n-2\equiv 0\pmod {11}\), \(5n\equiv 2\), and \(5^{-1}\equiv 9\pmod {11}\), so \(n\equiv 18\equiv 7\pmod {11}\). Solve \(n=9t+2\), \(9t+2\equiv 7\pmod {11}\), so \(9t\equiv 5\). Since \(9^{-1}\equiv 5\), \(t\equiv 25\equiv 3\pmod {11}\). The answer is \(n\equiv 29\pmod {99}\).

Impose \(N+1\equiv 0\pmod 2\), \(N+2\equiv 0\pmod 3\), \(N+3\equiv 0\pmod 5\), \(N+4\equiv 0\pmod 7\). Thus \(N\equiv 1\pmod 2\), \(N\equiv 1\pmod 3\), \(N\equiv 2\pmod 5\), \(N\equiv 3\pmod 7\). By CRT, a solution exists modulo \(210\). One solution is \(N=157\). Then \(158,159,160,161\) are divisible by \(2,3,5,7\), respectively, and are larger than those divisors; hence they are composite.

We have \(385=5\cdot 7\cdot 11\). For each of the moduli \(5,7,11\), the congruence \(x^2\equiv 1\) has two solutions: \(x\equiv 1\) and \(x\equiv -1\). The moduli are pairwise coprime, so the choices combine independently. There are \(2^3=8\) solutions modulo \(385\).

There are four systems. \((1,1)\) gives \(x\equiv 1\). \((-1,-1)\) gives \(x\equiv -1\equiv 34\). For \(x\equiv 1\pmod 5\), \(x\equiv -1\pmod 7\), checking \(1,6,11,16,21,26,31\) gives \(6\). For \(x\equiv -1\pmod 5\), \(x\equiv 1\pmod 7\), we get \(29\). The answer is \(1,6,29,34\pmod {35}\).

Let \(d=\gcd(m,n)\). If \(x\) is a solution, then \(m\mid x-a\), \(n\mid x-b\), so \(d\mid (x-a)\) and \(d\mid (x-b)\), hence \(d\mid a-b\). Conversely, suppose \(d\mid a-b\). Write \(m=dm_1\), \(n=dn_1\), \(\gcd(m_1,n_1)=1\). Seek \(x=a+mt\). We need \(a+d m_1t\equiv b\pmod {dn_1}\), or \(m_1t\equiv \frac{b-a}{d}\pmod {n_1}\). Since \(m_1\) is coprime to \(n_1\), it has an inverse, and such \(t\) can be chosen. Thus the system is solvable.

We need to solve \(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}\). The moduli are pairwise coprime, so by CRT a solution exists modulo \(M=3\cdot 5\cdot 7\cdot 11\cdot 13\). If \(N_0\) is one solution, then all \(N=N_0+tM\) are also solutions. There are infinitely many.

Require \(n\equiv 0\pmod 5\), \(n+2\equiv 0\pmod 7\), \(n+6\equiv 0\pmod {11}\). This is \(n\equiv 0\pmod 5\), \(n\equiv 5\pmod 7\), \(n\equiv 5\pmod {11}\). The moduli are coprime, so there is a solution \(n_0\) modulo \(385\). All \(n=n_0+385t\) have the same divisibility properties. For sufficiently large \(t\), the numbers \(n,n+2,n+6\) are larger than their assigned divisors, hence composite. There are infinitely many.

The moduli \(8,3,5,7\) are pairwise coprime. Modulo \(8\), all odd residues \(1,3,5,7\) square to \(1\), so there are \(4\) solutions. For each of \(3,5,7\), there are \(2\) solutions: \(\pm 1\). By CRT, the total number is \(4\cdot 2\cdot 2\cdot 2=32\).

For \(k=2\), this is the usual CRT. Suppose the statement is true for \(k-1\) moduli. The first \(k-1\) conditions are equivalent to one congruence \(x\equiv r\pmod M\), where \(M=m_1\cdots m_{k-1}\). Since \(m_k\) is coprime to each \(m_i\), \(\gcd(M,m_k)=1\). By CRT, \(x\equiv r\pmod M\), \(x\equiv r_k\pmod {m_k}\) is solvable. The induction is complete.

Let \(A=(k+1)!\). The numbers \(A+2,A+3,\ldots,A+(k+1)\) form \(k\) consecutive integers. For each \(j=2,\ldots,k+1\), \(A+j\) is divisible by \(j\), because \(A\) is divisible by \(j\). Also \(A+j>j\), so \(A+j\) is composite. This gives the required block.

Choose distinct primes \(p_1,\ldots,p_k>k\). Consider the system \(N+i\equiv 0\pmod {p_i}\) for \(i=1,\ldots,k\), or \(N\equiv -i\pmod {p_i}\). The moduli are pairwise coprime, so by CRT there is a solution \(N_0\) modulo \(P=p_1\cdots p_k\). Every \(N=N_0+tP\) also works. For sufficiently large \(t\), \(N+i>p_i\), so each \(N+i\) is composite and has its assigned prime divisor \(p_i>k\).

Since \(m_i>1\), choose a residue \(b_i\) different from \(a_i\) modulo \(m_i\). By CRT there exists \(x_0\) such that \(x_0\equiv b_i\pmod {m_i}\) for all \(i\). Then all \(x=x_0+tM\), where \(M=m_1\cdots m_k\), have the same residues modulo all \(m_i\). Hence they avoid all forbidden classes, and there are infinitely many such integers.

Choose pairwise distinct primes \(p_1,\ldots,p_k\) so large that \(p_i>|a_i-a_j|\) for all \(i,j\). The system \(N\equiv -a_i\pmod {p_i}\) is solvable by CRT. Let \(N_0\) be a solution and \(P=p_1\cdots p_k\). Then \(N=N_0+tP\) preserves all divisibilities \(p_i\mid N+a_i\). For sufficiently large \(t\), all \(N+a_i\) are positive and larger than \(p_i\), hence composite. There are infinitely many such \(t\).

For an odd prime \(p\), the congruence \(u^2\equiv 1\pmod p\) has only the solutions \(u\equiv \pm 1\pmod p\), because \((u-1)(u+1)\equiv 0\pmod p\). Therefore the condition “not congruent to \(\pm 1\) modulo any \(p_i\)” is incompatible with \(x^2\equiv 1\pmod {p_i}\) for every odd prime. Such an \(x\) does not exist for any choice of \(p_i\). Answer: the claim is false.