|
|
|
Viewing Version
9
of
'relationship between totatives and divisors'
|
[ view 'relationship between totatives and divisors'
|
back to history
]
| Title of object: |
relationship between totatives and divisors |
| Canonical Name: |
RelationshipBetweenTotativesAndDivisors |
| Type: |
Theorem |
| Created on: |
2007-05-24 23:47:42 |
| Modified on: |
2007-05-25 02:46:48 |
| Classification: |
msc:11A25 |
Preamble:
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{pstricks}
\usepackage{psfrag}
\usepackage{graphicx}
\usepackage{amsthm}
\usepackage{xypic}
\newtheorem{thm*}{Theorem}
|
Content:
\begin{thm*}
Let $n$ be a positive integer and define the sets $I_n$, $D_n$, and $T_n$ as follows:
\begin{itemize}
\item $I_n=\{ m \in \mathbb{Z}: 1 \le m \le n \}$
\item $D_n=\{ d \in I_n: d>1$ and $d|n \}$
\item $T_n=\{ t \in I_n: t$ is a totative of $n \}$
\end{itemize}
Then $D_n \cup T_n=I_n$ if and only if $n$ is a power of $2$ or $n$ is prime.
\end{thm*}
\begin{proof}
\vspace{2mm}
Necessity:
If $n$ is a power of $2$, then $D_n=\{ d \in I_n: d \text{ is even} \}$ and $T_n=\{ t \in I_n: t \text{ is odd} \}$. (In the case that $n=1$, $D_n=\emptyset$ and $T_n=\{ 1\}$.) 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 even. 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$.
Now 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(n,2p)=p$) nor a divisor of $n$ (since $n$ is odd). Hence, $D_n \cup T_n \neq I_n$.
\end{proof} |
|
|
|
|
|
