relationship between totatives and divisors
Theorem 1.
Let $n$ be a positive integer and define the sets ${I}_{n}$, ${D}_{n}$, and ${T}_{n}$ as follows:

•
${I}_{n}=\{m\in \mathbb{Z}:1\le m\le n\}$

•
${D}_{n}=\{d\in {I}_{n}:d>1$ and $dn\}$

•
${T}_{n}=\{t\in {I}_{n}:t$ is a totative^{} of $n\}$
Then ${D}_{n}\mathrm{\cup}{T}_{n}\mathrm{=}{I}_{n}$ if and only if $n\mathrm{=}\mathrm{1}$, $n\mathrm{=}\mathrm{4}$, or $n$ is prime.
Proof.
If $n=1$, then ${D}_{n}=\mathrm{\varnothing}$ and ${T}_{n}=\{1\}$. Thus, ${D}_{n}\cup {T}_{n}={I}_{n}$.
If $n=4$, then ${D}_{n}=\{2,4\}$ and ${T}_{n}=\{1,3\}$. Thus, ${D}_{n}\cup {T}_{n}={I}_{n}$.
If $n$ is prime, then ${D}_{n}=\{n\}$ and ${T}_{n}={I}_{n}\setminus \{n\}$. Thus, ${D}_{n}\cup {T}_{n}={I}_{n}$.
Sufficiency:
This will be proven by considering its contrapositive.
Suppose first that $n$ is a power of $2$. Then $n\ge 8$. Thus, $6\in {I}_{n}$. On the other hand, $6$ is neither a totative of $n$ (since $\mathrm{gcd}(6,n)=2$) nor a divisor^{} of $n$ (since $n$ is a power of $2$). Hence, ${D}_{n}\cup {T}_{n}\ne {I}_{n}$.
Now suppose that $n$ is even and is not a power of $2$. Let $k$ be a positive integer such that ${2}^{k}$ exactly divides $n$. Since $n$ is not a power of $2$, it must be the case that $n={2}^{k}r$ for some odd integer $r\ge 3$. Thus, $n={2}^{k}r>{2}^{k+1}$. Therefore, ${2}^{k+1}\in {I}_{n}$. On the other hand, ${2}^{k+1}$ is neither a totative of $n$ (since $n$ is even) nor a divisor of $n$ (since ${2}^{k}$ exactly divides $n$). Hence, ${D}_{n}\cup {T}_{n}\ne {I}_{n}$.
Finally, suppose that $n$ is odd. Let $p$ be the smallest prime divisor^{} of $n$. Since $n$ is not prime, it must be the case that $n=ps$ for some odd integer $s\ge 3$. Thus, $n=ps>2p$. Therefore, $2p\in {I}_{n}$. On the other hand, $2p$ is neither a totative of $n$ (since $\mathrm{gcd}(2p,n)=p$) nor a divisor of $n$ (since $n$ is odd). Hence, ${D}_{n}\cup {T}_{n}\ne {I}_{n}$. ∎
Title  relationship between totatives and divisors 

Canonical name  RelationshipBetweenTotativesAndDivisors 
Date of creation  20130322 17:09:15 
Last modified on  20130322 17:09:15 
Owner  Wkbj79 (1863) 
Last modified by  Wkbj79 (1863) 
Numerical id  15 
Author  Wkbj79 (1863) 
Entry type  Theorem 
Classification  msc 11A25 