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}\eq 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}\eq 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}\eq I_{n}$ .∎

单词	RelationshipBetweenTotativesAndDivisors
释义	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}\eq 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}\eq 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}\eq I_{n}$ .∎
随便看	hypergeometric function HypergeometricRandomVariable hypergeometric random variable Hypergraph hypergraph Hypergroup hypergroup HyperkahlerManifold hyperkähler manifold HyperperfectNumber hyperperfect number Hyperplane hyperplane HyperplaneArrangement hyperplane arrangement HyperplaneSeparation hyperplane separation Hyperreal hyperreal Hypersurface hypersurface Hypertext Hypertext HypertextMarkupLanguage Hypertext Markup Language