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

Proposition.

Every positive integer greater than 30 has at least one composite totative.

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. But if $n>50$ and $p\leq 7$, then $p^{2}<50. In either case we get that $p^{2}$ is a composite totative of $n$.

So now suppose $p>7$. Then $p=p_{k}$ for some $k>4$. To complete the proof, it is enough to show that $p^{2}$ is strictly smaller than the primorial $(k-1)\#=p_{1}p_{2}\cdots p_{k-1}$, which by assumption divides $n$. For then we would have $\gcd(n,p^{2})=1$ and $p^{2}, 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’s postulate, $p_{k+1}<2p_{k}$, so applying the induction assumption, we get that

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

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

Title every positive integer greater than 30 has at least one composite totative EveryPositiveIntegerGreaterThan30HasAtLeastOneCompositeTotative 2013-03-22 16:58:19 2013-03-22 16:58:19 mps (409) mps (409) 7 mps (409) Result msc 11A25 SmallIntegersThatAreOrMightBeTheLargestOfTheirKind