What is the largest (if any) multiplicative modulo group with all prime elements?

Question

Here's what I've been able to find out so far to address this question:

1) $C^*_2$ = {1}, $C^*_3$ = {1, 2}, $C^*_4$ = {1, 3}, $C^*_6$ = {1, 5}, $C^*_8$ = {1, 3, 5, 7}, and $C^*_{12}$ = {1, 5, 7, 11}, $C^*_{18}$ ={1, 5, 7, 11, 13, 17}, and $C^*_{30}$ = {1, 7, 11, 13, 17, 19, 23, 29} are all prime.

2) All $C^*_p$ where p is a prime larger than 3 have {4} as an element and thus cannot be all prime.

What is the largest modulo multiplicative group with all primes or is that even possible and there is no "largest"?

Answer 1

$n=30$ is the largest $n$ with this property.

Note that $11^2 < 2 \cdot 3 \cdot 5 \cdot 7$. By induction it is now straightforward to prove that if $p_n$ is the $n$-th prime, then $p_{n+1}^2 < 2 \cdot 3 \cdot 5 \cdot \cdots \cdot p_{n-1} \cdot p_n$ for $ n \geq 4$. Indeed, the induction step follows from the fact that $p_{n+1}$ is larger than $(p_{n+2}/p_{n+1})^2$, which is at most $4$ by Bertrand's postulate.

Let $p_k$ be the smallest prime not dividing $n$. Then $p_k^2$ is composite and coprime to $n$, so if $(\mathbb{Z}/n\mathbb{Z})^\ast$ contains only primes then $p_k^2 > n \geq p_{1} p_2 \cdots p_{k-1}$, which implies $k \leq 4$ and $n < 7^2$. So if $(\mathbb{Z}/n\mathbb{Z})^\ast$ contains only primes, then $n$ is at most $48$.

It is now easy to check that $30$ is the largest number with this property, since any number between $30$ and $48$ is coprime to $4$, $9$ or $25$.

Answer 2

We're looking for numbers $m$ such that every composite number less than $m$ is coprime to $m$.

If $p$ is the smallest prime that does not divide $m$, then $p^2$ is composite and coprime to $m$, so if $p^2<m$, then $m$ doesn't work.

Now turn that around and choose $p$ first. Since $p$ is the smallest prime that doesn't divide $m$, we can see that $m$ has to be at least the product of all primes smaller than $p$. But then, for $p=11$ we see that this smallest $m$ is already too large -- and due to Bertrand's postulate, this will keep holding for $p>11$ (namely, the product of the two last primes before $p$ is at least $p^2/8$, and multiplying this by the three first primes produces something that exceeds $p^2$). So the possibilities are:

• $p=7$ and $m$ is a multiple of $30$ less than $49$ -- that is $m=30$.
• $p=5$ and $m$ is a multiple of $6$ less than $25$ -- that is, $m\in \{6, 12, 18, 24\}$.
• $p=3$ and $m$ is an even number less than $9$ that is not a multiple of $3$ -- that is, $m\in\{2, 4, 8\}$.
• $p=2$ and $m$ is odd and less than $4$ -- that is, $m=3$.

This is the complete set of qualifying $m$s, so the maximum is $m=30$.

Answer 3

Claim. For $n>30$, there always exists a composite $m$ with $1<m<n$ and $\gcd(n,m)=1$.

Proof. If $n$ is odd, we can take $m=4$. If $n$ is not a multiple of $3$, we can take $m=9$. If $n$ is not a multiple of $5$, we can take $m=25$. So assume $n$ is a multiple of $30$. In particular, $n\ge 60$. Thus if $n$ is not a multiple of $7$, we can take $m=49$. So now we may assume $n$ is a multiple of the first four primes. In particular, $n\ge 210$. Thus if $n$ is not a multiple of $11$, we can take $m=11^2$. And if $n$ is not a multiple of $13$, we can take $m=13^2$. So now we may assume $n$ is a multiple of the first six primes. In particular, $n\ge 30030$. This allows us to repeat the argument with $17^2$, $19^2$, and so on up to $173^2=29929$.

A pattern evolves! Let $p$ be the smallest prime with $p\nmid n$. As seen, $p>173$.

By Bertrand, there is a prime $q$ between $\frac{p-1}2$ and $p$; note that $q\ge89$. By Bertrand again, there is a prime $r$ between $\frac{q-1}{2}$ and $q$; note that $r\ge 47$. Thus $n\ge 2\cdot 3\cdot 5\cdot r\cdot q>4r\cdot 2q>p^2$ and so we can take $m=p^2$ - contradiction. $\square$