PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: 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:

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)

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 693 times total.

Classification:
AMS MSC: 11A25 (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)