Results 1 to 2 of 2

Thread: Ivan Nivens problem

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    40

    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...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    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.$
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum