# 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
$\mathrm{gcd}(n,{p}^{2})=1$. If $n\le 50$, then $$, so $$.
But if $n>50$ and $p\le 7$, then $$. 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)\mathrm{\#}={p}_{1}{p}_{2}\mathrm{\cdots}{p}_{k-1}$, which by assumption^{}
divides $n$. For then we would have $\mathrm{gcd}(n,{p}^{2})=1$ and $$,
showing that ${p}^{2}$ is a composite totative of $n$.

We now prove by induction^{} that for any $k>4$, the inequality^{} $$ holds. For the base case $k=5$ we need to verify that

$$ |

Now suppose $$ for some $k>4$. By Bertrand’s
postulate^{}, $$, so applying the induction assumption, we
get that

$$ |

But $$, so $$ 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 |