# Thread: Ivan Nivens problem

1. ## Ivan Nivens problem

I need help on the following...
Show that every positive integer n has a unique expression of the form n=(2^r)m, r>=0, m is a positve odd integer.

I know that we need to find the existence of n, then find the uniqueness.. need help...

2. Existence is easily proven by strong induction.

1 is of that form as $\displaystyle 2^0\cdot1;$ so is $\displaystyle 2=2^1\cdot1.$

Let $\displaystyle n\geqslant2$ and assume that this is true for all integers $\displaystyle <n$.

If $\displaystyle n$ is odd, then $\displaystyle n=2^0\cdot n.$

If $\displaystyle n$ is even, then $\displaystyle n=2k$ for some $\displaystyle k<n$.

By the inductive hypothesis, $\displaystyle k=2^rm.$ $\displaystyle \therefore\ n=2^{r+1}m$ – which proves the result by strong induction.

For uniqueness, suppose $\displaystyle 2^{r_1}m_1=2^{r_2}m_2.$

Then $\displaystyle 2^{r_1}\mid 2^{r_2}$ since $\displaystyle \gcd(2^{r_1},m_2)=1.$ Similarly $\displaystyle 2^{r_2}\mid 2^{r_1}.$

$\displaystyle \therefore\ 2^{r_1}=2^{r_2}$ and so $\displaystyle r_1=r_2$ and $\displaystyle m_1=m_2.$