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 which is greater than 30.
Let be the smallest prime number which does not divide . Hence
. If , then , so .
But if and , then . In either case we
get that is a composite totative of .
So now suppose . Then for some . To complete
the proof, it is enough to show that is strictly smaller than
the primorial , which by assumption
divides . For then we would have and ,
showing that is a composite totative of .
We now prove by induction that for any , the inequality
holds. For the base case we need to verify that
Now suppose for some . 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 |