every positive integer greater than 30 has at least one composite totative

Proposition.

Every positive integer greater than 30 has at least one compositetotative.

Proof.

Suppose we are given a positive integer $n$ which is greater than 30.Let $p$ be the smallest prime number which does not divide $n$ . Hence $\\gcd(n,p^{2})=1$ . If $n\\leq 50$ , then $p<7$ , so $p^{2}\\leq 25<n$ .But if $n>50$ and $p\\leq 7$ , then $p^{2}<50<n$ . In either case weget that $p^{2}$ is a composite totative of $n$ .

So now suppose $p>7$ . Then $p=p_{k}$ for some $k>4$ . To completethe proof, it is enough to show that $p^{2}$ is strictly smaller thanthe primorial $(k-1)\\#=p_{1}p_{2}\\cdots p_{k-1}$ , which by assumptiondivides $n$ . For then we would have $\\gcd(n,p^{2})=1$ and $p^{2}<n$ ,showing that $p^{2}$ is a composite totative of $n$ .

We now prove by induction that for any $k>4$ , the inequality $p_{k}^{2}<(k-1)\\#$ holds. For the base case $k=5$ we need to verify that

p_{5}^{2}=121<210=4\\#.

Now suppose $p_{k}^{2}<(k-1)\\#$ for some $k>4$ . By Bertrand’spostulate, $p_{k+1}<2p_{k}$ , so applying the induction assumption, weget that

p_{k+1}^{2}<4p_{k}^{2}<4(k-1)\\#.

But $4<k<p_{k}$ , so $p_{k+1}^{2}<k\\#$ as desired.∎