Consecutive composite numbers using the Chinese Remainder Theorem.

78 Views Asked by At

Consecutive Composite Numbers

Define a list of the first $n$ prime numbers $p_1, p_2, \ldots, p_n$.

Create a set of $n$ congruences

\begin{align*} x + 1 &\equiv 0 \pmod{p_1} \\ x + 2 &\equiv 0 \pmod{p_2} \\ &\vdots \\ x + n &\equiv 0 \pmod{p_n} \end{align*}

By the Chinese Remainder Theorem (CRT), there exists a unique solution $x$.

The solution $x$ gives the start of a sequence of $n$ consecutive composite numbers:

$$x + 1, x + 2, \ldots, x + n$$

Example

Here's a C example to generate 21 consecutive composites using the above CRT method.

x+1 = 18242056294531940584645872728
x+2 = 18242056294531940584645872729
x+3 = 18242056294531940584645872730
x+4 = 18242056294531940584645872731
x+5 = 18242056294531940584645872732
x+6 = 18242056294531940584645872733
x+7 = 18242056294531940584645872734
x+8 = 18242056294531940584645872735
x+9 = 18242056294531940584645872736
x+10 = 18242056294531940584645872737
x+11 = 18242056294531940584645872738
x+12 = 18242056294531940584645872739
x+13 = 18242056294531940584645872740
x+14 = 18242056294531940584645872741
x+15 = 18242056294531940584645872742
x+16 = 18242056294531940584645872743
x+17 = 18242056294531940584645872744
x+18 = 18242056294531940584645872745
x+19 = 18242056294531940584645872746
x+20 = 18242056294531940584645872747
x+21 = 18242056294531940584645872748

Question

The common methods to generate consecutive composites are

$$\overbrace{(n+1)! + 2, \ (n+1)! + 3, \ \ldots, \ (n+1)! + (n+1)}^{\text{n composites}}$$

$$\overbrace{n!+2,n!+3,...,n!+n}^{\text{n-1 composites}}$$

$$\overbrace{n\#+2,n\#+3,…n\#+n}^{\text{n-1 composites (Primorials)}}$$

I'm curious what are the reasons this Chinese Remainder method to generate consecutive composite numbers isn't as well known?