Prove that every positive integer $n$ has a unique expression of the form: $2^{r}m$ where $r\ge 0$ and $m$ is an odd positive integer

if $n$ is odd then $n=2^{0}n$, but I dont know what to do when $n$ is even

and to prove that this expression is unique is it a good choice to use the fundamental theorem of arithmetic?

I would really appreciate your help


This is definitely where you use the Fundamental Theorem of Arithmetic.

Note that $2^rm$ actually is the unique prime decomposition of the number guaranteed by the theorem in disguise. The only difference is that $2$ and its powers have been separated from the rest of the primes (which have been combined into a single product, $m$).

In other words, consider a number $x$ and its unique prime decomposition. We can simply apply the associative property like so to get it into your form:

$$x = 2^{k_1}p_2^{k_2}p_3^{k_3} \cdot \cdot \cdot p_n^{k_n} = (2^{k_1}) \cdot (p_2^{k_2}p_3^{k_3} \cdot \cdot \cdot p_n^{k_n})$$

And of course if $x$ is odd, the power on $2$ would simply be $0$.

  • $\begingroup$ thanks a lot kaj_H I knew that I needed to use the fundamental theorem but someone told me that I was wrong, thanks again!! $\endgroup$ – user140027 Apr 23 '14 at 5:08
  • $\begingroup$ No problem; I'm glad I could help! Don't forget to accept an answer by clicking the check mark if you're good to go. That way, the question doesn't show up as unanswered for future users. $\endgroup$ – Kaj Hansen Apr 23 '14 at 5:12
  • $\begingroup$ Typo: if $x$ is odd, the power on 2 would simply be $\color{#c0d}{0}$. $\endgroup$ – Anant Apr 24 '14 at 13:01

If $n$ is odd, then $n = 2^{0}\cdot n$ which satisfies the condition. If $n$ is even, then let $r$ be the largest power of the factor $2^k$, then $n = 2^{r}\cdot m$. Claim: $m$ must be odd. If not then write $m = 2s$. So: $n = 2^{r+1}\cdot s$. So $r$ is no longer the max power of factor $2^k$, contradiction. Thus the conclusion follows.

  • $\begingroup$ thanks for the help LAcarguy :D $\endgroup$ – user140027 Apr 23 '14 at 5:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.