Exercise 1.3.6 ($n = 2^rm$, where $m$ is odd)

Question

Show that every positive integer $n$ has a unique expression of the form $n = 2^rm,\ r\geq 0$, $m$ a positive odd integer.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

\begin{proof}
Let $n$ be a positive integer. Consider the subset $A$ of $\N$ defined by
$$A = \{s \in \N : 2^s \mid n\}.$$
\begin{itemize}
\item $A 
e \varnothing$ since $0 \in A$.
\item $A$ is bounded above. Indeed, if $m \geq n$, then $2^m \geq 2^n > n$, thus $2^m 
mid n$, so $m
ot \in A$.

This shows that every element of $A$ is less than $n$, so $n$ is an upper bound for $A$.
\end{itemize}

Since $A 
e \varnothing$ is bounded above, $A$ has a largest element 
$$r = \max(A).$$
By definition of a largest element, $r \in A$, so $2^r \mid n$. Thus there is some $m \in \N$ such that $n = 2^r m$.

Assume for contradiction that $m$ is even. Then $2 \mid m$, thus $2^{r+1} \mid n$, and $r+1 \in A$. Then $r+1 \leq \max(A) = r$. This is absurd, therefore $m$ is odd.
$$n = 2^r m ,\qquad 2 
mid m.$$

\bigskip
Now we prove the unicity of this expression of $n$. If $n = 2^r m = 2^t q$, where $m,q$ are odd, then $2^r \mid 2^t q$, and $2^r \wedge q = 1$, thus $2^r \mid 2^t$, so $r \leq t$. Similarly $t\leq r$, therefore $r = t$. From $2^r m = 2^t q$, we deduce $m = a$. The expression is unique.

\end{proof}
Note: Alternatively, we can use the full decomposition in prime numbers of $n = \sum_{p} p^{\alpha(p)}$. Then $r = \alpha(2)$, and $m$ is the product of $p^{\alpha(p)}$ for odd $p$. From a computational point of view, the above solution is preferable. It suggests the following algorithm to obtain $r, m$:
\begin{verbatim}
def niven136(n):
    r = 0
    m = n
    while m % 2 == 0:
        r = r + 1
        m = m // 2
    return (r,m)
    
print(niven136(3328))
(8, 13)
\end{verbatim}

Exercise 1.3.6 ($n = 2^rm$, where $m$ is odd)

Answers

Comments

Exercise 1.3.6 ($n = 2^rm$, where $m$ is odd)

Answers

Comments

Add answer