# A prime number determined by its congruence relation?

Let $p_i$ denote the $i$-th prime number. Is there any "good function" $k(n)$ such that when we know $x_i$ for which $p_n \equiv x_i \pmod{p_i}$ for all $i\leq k(n)$, it is possible to find a unique value for $p_n$.

Note that we only assume that we know the prime numbers $p_1,p_2\ldots, p_l$ where $l\leq k(n)$ and the values $x_1,x_2,\ldots,x_l$.

• That changes the question entirely. Commented Jul 13, 2017 at 16:54
• @messel If you answer this comment then your question will be much clearer: Given that $l=4$ and $x_1,x_2,x_3,x_4$ are $1,1,2,4$ coming from unknown prime $p \lt 100$, does this mean $p \bmod 2,3,5,7$are $1,1,2,4$ IN THAT ORDER (so $p=67$) OR might it be that the correct order is $1,1,4,2$ or $1,2,1,4$ or $1,2,4,1$ giving $79$ or $11$ or $29$ respectively? Commented Jul 13, 2017 at 20:05
• Yes, in that given order. Commented Jul 13, 2017 at 22:43
• I rolled back the question to the previous version. Commented Jul 14, 2017 at 0:26

The term for this is primorial numbering. What you see is that each digit in the "primorial numbering system" corresponds to a residue in each cyclic ring with prime modulus. So in fact if you are looking for a prime $p_n$ then we know that $i < n$ implies the order $p_i < p_n$, because the $i$-th prime numbers $p_i$ are an increasing sequence.

First, $x_n \equiv p_n \equiv 0 \pmod{p_n}$ and $x_i \not \equiv 0 \pmod{p_i}$.

Then observe that $p_n \equiv 1 \pmod{2}$ for all the odd primes and that $p_n \in (\mathbb{Z}/p_i \# \mathbb{Z})^*$ in general which is equivalent to $x_i \not \equiv 0 \pmod{p_i}$. Unfortunately for you, when the greatest common factor between your $(x_i, p_i) = 1$ there are infinitely many primes $\{ p \equiv x_i \pmod{p_i} \}$ via Dirichlet's Theorem.

As a result, whenever you form your primorial numbering with the Chinese Remainder Theorem, $\bigcap_{i<n} \{x_i \pmod{p_i} \}$ you won't be able to uniquely determine a value for $p_n \in \mathbb{P}$ below $k(n) = n$, because that intersection forms a residue class and $\{ p_n \equiv x_i \pmod{p_i} \}$ implies that $x_i \in (\mathbb{Z} / p_i \mathbb{Z})^*$ because $p_n$ and $p_i$ are relatively coprime. The intersection formed by $\bigcap_{i<n} \{x_i \pmod{p_i} \}$ when $i \in [0,n)$ is a prime residue class and, again, as a result of Dirichlet's Theorem, it contains infinitely many prime numbers. $x_i \equiv 0 \pmod{p_i}$ if and only if $x_i = p_i = p_n$. Otherwise there exist at least two residue classes for which $p_n \equiv 0 \pmod{p_i}$ and as a result either $p_n$ is not a prime number, or $p_i \ne p_n$, while $p_i \mid p_n$. This is a contradiction.

Therefore $k(n) = n$.

• If I am wrong, let me know I claimed that $k(n)\leq n-1$. Now we know all primes $p_1,...,p_{n-1}$. Then $p_n\leq 2p_{n-1}$. Now, since I know $x_1$ and $x_{n-1}$, and $p_1=2$ we know that $p_n\equiv t \ mod \ 2p_{n-1}$. Since $p_n\leq 2p_{n-1}$, $p_n=t$. Commented Jul 12, 2017 at 16:19
• I think the reason is the following; You are claiming there are infinitely many prime number satisfying the congruence relation, which is true. But, $p_n$ is bounded by $k(n)$. More specifically, $$p_n \leq p_{[k(n)]}2^{n-k(n)}$$ Ofcourse, there are better bounds also. Thus, the question turns to be whether there is a unique solution satisfying the inequality. Commented Jul 12, 2017 at 16:40
• $p_n = p_{k(n)}$ precisely when $n - k(n) = 0$. Commented Jul 12, 2017 at 16:49
• I did not understand what you mean, did you read the first comment ? Commented Jul 12, 2017 at 16:52
• No. I won't delete my answer, because its not wrong. Commented Jul 12, 2017 at 23:37

Update 2017.07.13: The question has been made more precise and interesting by having some uncertainty introduced in knowing some information in an 'unordered' fashion. Part of the interest stems from the fact that a multiset of residues mod small primes has some limitations in making a valid interpretation. For example, if 6 is a residue, is that mod 5 or mod 7? If it is 6 mod 2 or mod 3 then most of the other residues have to have the same value, either 2 or 3.

In spite of this uncertainty, much of the post below applies. If you know n (equivalently p_n) is small enough, you can still have a multiset of about (say) 3 log (n) many terms to specify the prime. This is because the primes less than M are few in number compared to the number of appropriate multisets of length 3*log M. A question similar to one that has appeared on MathOverflow I record here: if p is a small prime with residue multiset consisting of 1's and 2's only, how long does it take to find it? Notice that this has a connection with consecutive smooth numbers.

End Update 2017.07.13.

If you are given the value m=k(n), and the first m primes and moduli p_i and x_i, and you are given the information that the prime p_n you are looking for is less than the product of the known primes, then (since the product of the first m primes is about exp(p_m) ), you can have k(n) be as small as something like 2log(n), perhaps smaller. Because of the wording of the question, it is not clear if you have or can derive the information that p_1 p_2... p_m is greater than p_n . If you have no clue of n other than p_n is prime, then (as was pointed out in another post) because of the infinitude of primes in certain arithmetic progressions the only congruence that specifies the prime p_n is p_n =0 mod p_n; no other finite system of congruences mod primes that excludes p_n does so.

For example, suppose I know n is 11. From other theory, I know p_11 is less than 11 * 4, (using log 11 + log log 11) and so k(11) is 4, and so p_11 is less than 2*3*5*7. Using moduli, I get p_11 is 31. If I did not know n was 11, I might not know if the prime was 31 or 241 just from knowing k(n)=4 and the four congruences.

Gerhard "Hopefully This Answers The Question" Paseman, 2017.07.12.

• There is no $m$. $k(n)$ was the upper limit for $i$ in the residue classes for which $\{x_i \pmod{p_i}\}$ was known if $p_i$ was the $i$-th prime number. See my counter example. Commented Jul 12, 2017 at 23:29
• By saying that $p_i$ is $i$'th prime, is it not clear that $p_1=2,p_2=3,p_3=5 ...$. Commented Jul 12, 2017 at 23:30
• How is it not? That's what it usually means. Commented Jul 12, 2017 at 23:32
• Are you given n? Are you given k(n)? Can you infer the information I mention? If you are the original poster, you can say. Otherwise the best you can do is interpret. Gerhard "Has Given His Own Interpretation" Paseman, 2017.07.12. Commented Jul 12, 2017 at 23:38
• Where does $i$-th prime number not mean the sequence of primes? Commented Jul 12, 2017 at 23:39