Bdtyktl

While practicing to code for my college course I stumbled upon this and would like to know if this is something new or significant as I haven't found anything resembling it on the internet.

$ p_1, p_2, ..., p_n = text{consecutive prime numbers starting from 2} \$

$ q_1 = p_2p_3...p_n \
q_2 = p_1p_3...p_n \
... \
q_n = p_1p_2...p_{n-1} \$

$ r_1 in {1, ..., p_1-1} \
... \
r_n in {1, ..., p_n-1} \$

$ s= p_1p_2...p_n \$

$ x equiv q_1r_1+...+q_nr_n :text{mod}: s \$

$ x_2 = text{the second smallest congruence} \
text{All congruences less than } x_2^2 text{ are also every prime number between } p_n text{ and } x_2^2 \$

$ text{example:} \$

$ p_1, p_2, ..., p_n = 2, 3, 5 \$

$ q_1 = 3cdot5 = 15 \
q_2 = 2cdot5 = 10 \
q_3 = 2cdot3 = 6 \$

$ r_1 in {1} \
r_2 in {1, 2} \
r_3 in {1, 2, 3, 4} \$

$ s = 2cdot3cdot5=30 \$

$ x_2 equiv 7 equiv 15cdot1 +10cdot1 +6cdot2 :text{mod}: 30 \
7^2 = 49 \$

$ text{The full sequence of primes is clearly not random.} \$

$ 0 \
color{blue}{1 equiv 31 equiv 15cdot1 +10cdot1 +6cdot1 :text{mod}: 30} \
1 \
2 \
3 \
4 \
color{red}{5} \$

$ 6 \
color{blue}{7 equiv 37 equiv 15cdot1 +10cdot1 +6cdot2 :text{mod}: 30} \
8 \
9 \
10 \
color{red}{11 equiv 41 equiv 15cdot1 +10cdot2 +6cdot1 :text{mod}: 30} \$

$ 12 \
color{blue}{13 equiv 43 equiv 15cdot1 +10cdot1 +6cdot3 :text{mod}: 30} \
14 \
15 \
16 \
color{red}{17 equiv 47 equiv 15cdot1 +10cdot2 +6cdot2 :text{mod}: 30} \$

$ 18 \
color{blue}{19 equiv 15cdot1 +10cdot1 +6cdot4 :text{mod}: 30} \
20 \
21 \
22 \
color{red}{23 equiv 15cdot1 +10cdot2 +6cdot3 :text{mod}: 30} \$

$ 24 \
color{blue}{25} \
26 \
27 \
28 \
color{red}{29 equiv 15cdot1 +10cdot2 +6cdot4 :text{mod}: 30} \$

Interesting that you marked 25, which is not a prime, similar to 6x+1 and 6x-1, which means it's not a primality test, but still quite interesting.

I had to say, I was suspicious when I read the question but I coded up the problem and up to at least $n=10$ it definitely works.

Edit: I found a proof! It works. Check out the details below.

The proof consists of two main steps: we first prove that the sum $r_1 q_1 + cdots + r_n q_n$ can never be divided by $p_i$ for any $i$ between $1$ and $n$. After that, we will show that $x_2 = p_{n+1}$.

To prove the first part, let's first forget about the modulo $p_1p_2cdots p_n$ term for a moment. Now, note that both $q_i$ and $r_i$ are not divisible by $p_i$ and all other $q_i$ are divisible by $p_i$. Hence, our sum
$$r_1q_1 + cdots + r_n q_n = r_i q_i (neq 0) mod p_i$$ can never be divisible by $p_i$. Adding a multiple of $p_1cdots p_n$ (which is divisible by $p_i$) doesn't change this fact. Hence, $$Big(r_1 q_1 + cdots + r_n q_nmod (p_1cdots p_n)Big) neq 0 mod p_i$$
for any $i$ between $1$ and $n$. Summarizing, the first $n$ primes $p_1$, $p_2$, $dots$ ,$p_n$ will never be divisors of our sum. Now, the question remains: might it be divisible by $p_{n+1}$ for example? We cannot exclude this! But this does wrap up the first part of the proof.

Lemma There exist choices $(r_1,dots,r_n)$ and $(r_1',dots,r_n')$ such
that $$ r_1 q_1 + cdots + r_n q_n = 1mod (p_1p_2cdots p_n) $$ and
$$ r_1 q_1 + cdots + r_n q_n = p_{n+1}mod (p_1p_2cdots p_n). $$

Proof This lemma is actually an application of the Chinese Remainder Theorem. This theorem states that given a sequence $$(a_1,dots,a_n)in prod_{i=1}^{n}mathbb{F}_{p_i}$$
is uniquely related to an $ainmathbb{F}_{prod_{i=1}^{n} p_i}$ where I use the notation $mathbb{F}_z$ to represent the group related to calculating modulo $z$.

We actually know that $(1,1,dots,1)$ is related to $1$ but we don't know exactly what is the sequence which is related to $p_{n+1}$. It turns out it is not necessary to know this sequence to proof its existence! Let's take now arbitrary values $z_1,dots,z_n$ which satisfy the same conditions as the $r_i$, $r_i'$. Let's simplify our expression now modulo $p_i$
$$ z_1 q_1 + cdots + z_n q_n = z_i q_i mod p_i $$
Since $p_i$ is prime, we know that $c q_i$ for $cin{1,dots,p_i-1}$ actually generates the complete group, i.e., $$ {c q_i mod p_i: cin{1,dots,p_i-1}} = {1,2,dots,p_i-1}.$$ This essentially means that we can make the right-hand side equal to almost any number in $prod_{i=1}^{n}mathbb{F}_{p_i}$. To be precise,
$$ prod_{i=1}^{n}{z_1 q_1 + cdots + z_n q_n mod p_i: forall j: 1leq z_jleq p_j-1} \ = prod_{i=1}^{n}{z_i q_i mod p_i: 1leq z_ileq p_i-1} = prod_{i=1}^{n} (mathbb{F}_{p_i}setminus{0}). $$ A slight adaptation of the standard Chinese Remainder Theorem now gives us that
$$ {z_1 q_1 + cdots + z_n q_n mod (p_1cdots p_n): forall j: 1leq z_jleq p_j-1} = mathbb{F}_{prod_{i=1}^{n} p_i}setminus A $$
where $A$ is the set of all multiples of $0, p_1, p_2, dots, p_n$.

Now, let's translate this to English. We see that $1$ is not an element of $A$ and, hence, there exists a sequence $(z_1,dots,z_n)$ such that
$$ z_1 q_1 + cdots + z_n q_n = 1 mod (p_1cdots p_n)$$
and we simply take $r_i = z_i$. Moreover, the next element which is not part of $A$ is $p_{n+1}$ and hence there exist a sequence $(w_1,dots,w_n)$ such that
$$ w_1 q_1 + cdots + w_n q_n = p_{n+1} mod (p_1cdots p_n) $$
and we take $r_i'=w_i$. This completes the proof of the lemma.

Now, we have dealt with the most difficult part and it is not too difficult to finish the proof. For the sake of completeness, let $s = r_1 q_1 + cdots + r_n q_nmod (p_1p_2cdots p_n)$ such that $s< p_{n+1}^2$ and let's assume it is composite. We have proven above that $s$ is not divisible by $p_1, p_2, dots, p_n$. This means that the first candidate prime factor is actually $geq p_{n+1}$. However, since $s$ is composite, it has a second prime factor and this also needs to be $geq p_{n+1}$. Thus $sgeq p_{n+1}^2$ which is a contradiction. This completes the overall proof!

Extra note: we have developed a way of constructing the first $n$ primes. However, since it is not clear how the sequence $(r_1',dots,r_n')$ is chosen in practice, the method is not particularly computationally efficient to put it mildly.