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<n$ . But if $n>50$ and $p\leq 7$ , then $p^{2}<50<n$ . 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}<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’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<k<p_{k}$ , so $p_{k+1}^{2}<k\#$ as desired. ∎

Title	every positive integer greater than 30 has at least one composite totative
Canonical name	EveryPositiveIntegerGreaterThan30HasAtLeastOneCompositeTotative
Date of creation	2013-03-22 16:58:19
Last modified on	2013-03-22 16:58:19
Owner	mps (409)
Last modified by	mps (409)
Numerical id	7
Author	mps (409)
Entry type	Result
Classification	msc 11A25
Related topic	SmallIntegersThatAreOrMightBeTheLargestOfTheirKind