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.

Necessity:

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
Canonical name	RelationshipBetweenTotativesAndDivisors
Date of creation	2013-03-22 17:09:15
Last modified on	2013-03-22 17:09:15
Owner	Wkbj79 (1863)
Last modified by	Wkbj79 (1863)
Numerical id	15
Author	Wkbj79 (1863)
Entry type	Theorem
Classification	msc 11A25