Results 1 to 2 of 2

Math Help - 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 2^0\cdot1; so is 2=2^1\cdot1.

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

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

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

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

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

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

    \therefore\ 2^{r_1}=2^{r_2} and so r_1=r_2 and m_1=m_2.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum