You are here
Homerelationship between totatives and divisors
Primary tabs
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 $dn\}$

$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}$.
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}$. ∎
Mathematics Subject Classification
11A25 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections
Comments
When n is a power of 2
I'm not so sure this is correct for powers of 2. For example, 8. Totatives are 1, 3, 5, 7; divisors are 1, 2, 4, 8. The union of these two sets if 1, 2, 3, 4, 5, 7, 8; missing is 6.
Re: When n is a power of 2
Good catch. Obviously, 6 is not a divisor of any power of 2. I'll edit accordingly. Thanks.