PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: Very high
[parent] relationship between totatives and divisors (Theorem)
Theorem   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 \le m \le 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 \ge 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^kr$ for some odd integer $r \ge 3$ Thus, $n=2^kr>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 \ge 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$ $ \qedsymbol$




"relationship between totatives and divisors" is owned by Wkbj79.
(view preamble | get metadata)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: prime divisor, odd, odd integer, exactly divides, even, divisor, contrapositive, sufficiency, necessity, prime, totative, integer, positive
There are 2 references to this entry.

This is version 12 of relationship between totatives and divisors, born on 2007-05-24, modified 2007-06-02.
Object id is 9463, canonical name is RelationshipBetweenTotativesAndDivisors.
Accessed 1324 times total.

Classification:
AMS MSC11A25 (Number theory :: Elementary number theory :: Arithmetic functions; related numbers; inversion formulas)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy
When n is a power of 2 by PrimeFan on 2007-06-01 19:01:49
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.
[ reply | up ]

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)