# 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\leq m\leq n\}$

• $D_{n}=\{d\in I_{n}:d>1$ and $d|n\}$

• $T_{n}=\{t\in I_{n}:t$ is a totative of $n\}$

Then $D_{n}\cup T_{n}=I_{n}$ if and only if $n=1$, $n=4$, or $n$ is prime.

###### Proof.

If $n=1$, then $D_{n}=\emptyset$ 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\geq 8$. Thus, $6\in I_{n}$. On the other hand, $6$ is neither a totative of $n$ (since $\gcd(6,n)=2$) nor a divisor of $n$ (since $n$ is a power of $2$). Hence, $D_{n}\cup T_{n}\neq 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\geq 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}\neq 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\geq 3$. Thus, $n=ps>2p$. Therefore, $2p\in I_{n}$. On the other hand, $2p$ is neither a totative of $n$ (since $\gcd(2p,n)=p$) nor a divisor of $n$ (since $n$ is odd). Hence, $D_{n}\cup T_{n}\neq I_{n}$. ∎

Title relationship between totatives and divisors RelationshipBetweenTotativesAndDivisors 2013-03-22 17:09:15 2013-03-22 17:09:15 Wkbj79 (1863) Wkbj79 (1863) 15 Wkbj79 (1863) Theorem msc 11A25