4
$\begingroup$

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?

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

$\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.

$\endgroup$
  • $\begingroup$ Aw snaps with my second equation. I tried. Thank you. $\endgroup$ – Simply Beautiful Art Jan 27 '16 at 21:27
  • $\begingroup$ @SimpleArt Nevertheless a very nice hunt for patterns $\endgroup$ – Hagen von Eitzen Jan 27 '16 at 21:31
1
$\begingroup$

That's just a coincidence, and it will vanish as soon as you'll go a bit further. Indeed, 30 is the greatest number with the property that all numbers below it and coprime to it are prime (or 1).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.