# Integers such that all Coprime and Less are Prime

## Theorem

The following positive integers have the property that all positive integers less than and coprime to it, excluding $1$, are prime:

- $1, 2, 3, 4, 6, 8, 12, 18, 24, 30$

This sequence is A048597 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).

There are no other positive integers with this property.

## Proof

Let $S_n$ denote the set of all positive integers less than and coprime to $n$, excluding $1$.

Let $\map P n$ denote the propositional function:

- All positive integers less than and coprime to $n$, excluding $1$, are prime.

We establish that $\map P n = \mathrm T$ for all the positive integers given:

\(\displaystyle S_1\) | \(=\) | \(\displaystyle \varnothing\) | trivially | ||||||||||

\(\displaystyle S_2\) | \(=\) | \(\displaystyle \varnothing\) | trivially | ||||||||||

\(\displaystyle S_3\) | \(=\) | \(\displaystyle \set 2\) | which is prime | ||||||||||

\(\displaystyle S_4\) | \(=\) | \(\displaystyle \set 3\) | which is prime | ||||||||||

\(\displaystyle S_6\) | \(=\) | \(\displaystyle \set 5\) | which is prime | ||||||||||

\(\displaystyle S_8\) | \(=\) | \(\displaystyle \set {3, 5, 7}\) | all prime | ||||||||||

\(\displaystyle S_{12}\) | \(=\) | \(\displaystyle \set {5, 7, 11}\) | all prime | ||||||||||

\(\displaystyle S_{18}\) | \(=\) | \(\displaystyle \set {5, 7, 11, 13, 17}\) | all prime | ||||||||||

\(\displaystyle S_{24}\) | \(=\) | \(\displaystyle \set {5, 7, 11, 13, 17, 19, 23}\) | all prime | ||||||||||

\(\displaystyle S_{30}\) | \(=\) | \(\displaystyle \set {7, 11, 13, 17, 19, 23, 29}\) | all prime |

From Schatunowsky's Theorem:

- $30$ is the greatest positive integer $n$ such that $\map P n$ is true

We note that for all primes $p$ greater than $3$, $p - 1$ is composite, and so $\map P p = \mathrm F$.

The remaining composite numbers less than $30$ are investigated:

\(\displaystyle S_9\) | \(=\) | \(\displaystyle \set {2, 4, 5, 7, 8}\) | of which $2, 4, 8$ are composite | ||||||||||

\(\displaystyle S_{10}\) | \(=\) | \(\displaystyle \set {3, 7, 9}\) | of which $9$ is composite, | ||||||||||

\(\displaystyle S_{14}\) | \(=\) | \(\displaystyle \set {3, 5, 9, 11, 13}\) | of which $9$ is composite | ||||||||||

\(\displaystyle S_{15}\) | \(=\) | \(\displaystyle \set {2, 4, 7, 8, 11, 13, 14}\) | of which $4, 8, 14$ are composite | ||||||||||

\(\displaystyle S_{16}\) | \(=\) | \(\displaystyle \set {3, 5, 7, 9, 11, 13, 15}\) | of which $9, 15$ are composite | ||||||||||

\(\displaystyle S_{20}\) | \(=\) | \(\displaystyle \set {3, 7, 9, 11, 13, 17, 19}\) | of which $9$ is composite | ||||||||||

\(\displaystyle S_{21}\) | \(=\) | \(\displaystyle \set {2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}\) | of which $4, 8, 10, 16, 20$ are composite | ||||||||||

\(\displaystyle S_{22}\) | \(=\) | \(\displaystyle \set {3, 5, 7, 9, 13, 15, 17, 19, 21}\) | of which $9, 15, 21$ are composite | ||||||||||

\(\displaystyle S_{25}\) | \(=\) | \(\displaystyle \set {2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24}\) | of which $4, 6, 8, 9, 12, 14, 16, 18, 21, 22, 24$ are composite | ||||||||||

\(\displaystyle S_{26}\) | \(=\) | \(\displaystyle \set {3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25}\) | of which $9, 15, 21, 25$ are composite | ||||||||||

\(\displaystyle S_{27}\) | \(=\) | \(\displaystyle \set {2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26}\) | of which $4, 8, 10, 14, 16, 20, 22, 25, 26$ are composite | ||||||||||

\(\displaystyle S_{28}\) | \(=\) | \(\displaystyle \set {3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27}\) | of which $9, 15, 25, 27$ are composite |

That exhausts the list.

Hence the result.

$\blacksquare$

## Sources

- 1971: George E. Andrews:
*Number Theory*... (previous) ... (next): $\text {4-2}$ Residue Systems: Exercise $4$ - 1986: David Wells:
*Curious and Interesting Numbers*... (previous) ... (next): $30$ - 1997: David Wells:
*Curious and Interesting Numbers*(2nd ed.) ... (previous) ... (next): $30$