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}$ .∎
随便看	AntiderivativeOfRationalFunction antiderivative of rational function AntidiagonalMatrix anti-diagonal matrix AntiharmonicNumber antiharmonic number Antiholomorphic antiholomorphic Antiidempotent anti-idempotent Antiisomorphism anti-isomorphism AntiperiodicFunction antiperiodic function Antipodal antipodal AntipodalIsothermicPoints antipodal isothermic points AntipodalMapOnSnIsHomotopicToTheIdentityIfAndOnlyIfNIsOdd antipodal map on S^n is homotopic to the identity if and only if n is odd Antiprism antiprism Antisymmetric antisymmetric AntisymmetricMapping