# 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$

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 = \T$ for all the positive integers given:

 $\ds S_1$ $=$ $\ds \O$ trivially $\ds S_2$ $=$ $\ds \O$ trivially $\ds S_3$ $=$ $\ds \set 2$ which is prime $\ds S_4$ $=$ $\ds \set 3$ which is prime $\ds S_6$ $=$ $\ds \set 5$ which is prime $\ds S_8$ $=$ $\ds \set {3, 5, 7}$ all prime $\ds S_{12}$ $=$ $\ds \set {5, 7, 11}$ all prime $\ds S_{18}$ $=$ $\ds \set {5, 7, 11, 13, 17}$ all prime $\ds S_{24}$ $=$ $\ds \set {5, 7, 11, 13, 17, 19, 23}$ all prime $\ds S_{30}$ $=$ $\ds \set {7, 11, 13, 17, 19, 23, 29}$ all prime
$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 = \F$.

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

 $\ds S_9$ $=$ $\ds \set {2, 4, 5, 7, 8}$ of which $2, 4, 8$ are composite $\ds S_{10}$ $=$ $\ds \set {3, 7, 9}$ of which $9$ is composite, $\ds S_{14}$ $=$ $\ds \set {3, 5, 9, 11, 13}$ of which $9$ is composite $\ds S_{15}$ $=$ $\ds \set {2, 4, 7, 8, 11, 13, 14}$ of which $4, 8, 14$ are composite $\ds S_{16}$ $=$ $\ds \set {3, 5, 7, 9, 11, 13, 15}$ of which $9, 15$ are composite $\ds S_{20}$ $=$ $\ds \set {3, 7, 9, 11, 13, 17, 19}$ of which $9$ is composite $\ds S_{21}$ $=$ $\ds \set {2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}$ of which $4, 8, 10, 16, 20$ are composite $\ds S_{22}$ $=$ $\ds \set {3, 5, 7, 9, 13, 15, 17, 19, 21}$ of which $9, 15, 21$ are composite $\ds S_{25}$ $=$ $\ds \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 $\ds S_{26}$ $=$ $\ds \set {3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25}$ of which $9, 15, 21, 25$ are composite $\ds S_{27}$ $=$ $\ds \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 $\ds S_{28}$ $=$ $\ds \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$