# What integers are coprime to the first $x$ prime numbers?

I have noticed that there is a very specific pattern to numbers that are coprime to $2$, it is simply all of the odd numbers. More specifically, it is in the following pattern, where $n$ is an integer:

$$2n+1$$

For numbers that are coprime to the first $2$ prime numbers, $2$ and $3$ (or $6$), it is given as:

$$6n\pm1$$

And upon analyzing this, I found an equivalent expression:

$$6n\pm p_i$$

Where $p_i$ is the $i^{th}$ prime number greater than $2$ or $3$. You can check this using modular arithmetic.

When considering a pattern to numbers that are coprime to the first $3$ prime numbers, I get the following:

$$30n\pm p_i$$

In fact, I have found that there is a particular $p_i$ which satisfies the entire problem for each problem, as we see $5$ satisfies $p_i$ for the first $2$ prime numbers problem. In fact, $6n\pm5$ will never produce numbers that aren't coprime to the first $2$ prime numbers and never misses any numbers that are.

For the first 3 prime numbers, I note the following:

$$15n\pm2^a$$

For any integer $n$ or $a$, $15n\pm2^a$ will always be coprime to $2,3,5$ and there is no number it misses.

And then going back, I realize this also implies $3n\pm2^a$ is also coprime to $2$ and $3$.

In fact, I found that the following two expressions represent all numbers that are coprime to the first $x$ prime numbers:

$$\Pi_{v=1}^xp_vn\pm p_i$$

$$\frac{\Pi_{v=1}^xp_v}2n\pm2^a$$

And the second one reduces since $p_1=2$:

$$\Pi_{v=2}^xp_vn\pm2^a$$

Though I cannot construct a proof as to why such occurs. Could someone explain why these two expressions manage to produce all numbers that are coprime to the first $x$ prime numbers and no numbers that aren't coprime?

• If $p_1 = 2$, then the second expression has the nicer form $\prod _{v=2} ^x p_v n \pm 2^a$. – Alex M. Jan 27 '16 at 21:22
• @AlexM. True. I will include that. – Simply Beautiful Art Jan 27 '16 at 21:23

$\prod_{v=1}^x p_vn\pm p_i$ is certainly coprime to $p_1,\ldots, p_x$ as long as $p_i$ is not among these primes. On the other hand, Dirichlet showed that in each arithmetic progression $an+b$ with $a$, $b$ coprime, there are infinitely many primes. Therefore, we are sure to find enough distinct primes $p_i$ to civer all coprime residue classes. In fact, it suffices to consider only $\prod_{v=1}^x p_vn- p_i$ (or, if we allow negative $n$, only $\prod_{v=1}^x p_vn+ p_i$). Note that your observation "one prime suffices" does not generalize: There are $\prod_{v=1}^x (p_v-1)$ co prime residues classes and this is $>2$ as soon as we go beyond the first two primes.
Your second expression, $\frac12\prod_{v=1}^x p_vn\pm 2^a$ is a bit more problematic: If $n$ is a multiple of $4$, then the expression will be even! But in all other cases, this is both odd and coprime to the remaining of the first $x$ primes because for each of these one summand is a multiple and the other is not. Hence with the caveat about $4\mid n$, this expression covers only coprime residue classes. But does the expression cover all coprime residue classes? Perhaps surprisingly, it doesn't! As $2^5\equiv 1\pmod{31}$, we see that the powers of $2$ run only over five distinct residue classes modulo $31$. If we add the negatives, $-2^a$, this count doubles to ten. But there are $30$ residue classes we want to cover.