Results 1 to 2 of 2

Thread: Trouble with a proposition

  1. #1
    Junior Member
    Joined
    Jan 2011
    From
    Sydney
    Posts
    36

    Trouble with a proposition

    Proposition 5.18 (An introduction to mathematical cryptography)
    Let n be a positive integer and let $\displaystyle k=\lfloor \log n \rfloor +1 .$ which means that $\displaystyle 2^k > n.$ Then we can always write $\displaystyle n = u_0 + u_1*2+u_2*4+u_3*8+...+u_k*2^k$
    With $\displaystyle u_0,u_1,...,u_k \in \textbracerleft -1,0,1 \textbracerright $ and at most $\displaystyle \frac{1}{2}k$ of the $\displaystyle u_i$ nonzero.




    So say if we have n=61 then $\displaystyle \lfloor log n \rfloor + 1 = 5 $ then $\displaystyle 2^5 = 32$ which is definitly not greater than 61. So the first line of the proposition is not correct. Where on earth am i going wrong!! I must be missing something?

    Any insight would be greatly appreciated,
    cheers
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    10

    Re: Trouble with a proposition

    Quote Originally Posted by liedora View Post
    Proposition 5.18 (An introduction to mathematical cryptography)
    Let n be a positive integer and let $\displaystyle k=\lfloor \log n \rfloor +1 .$ which means that $\displaystyle 2^k > n.$ Then we can always write $\displaystyle n = u_0 + u_1*2+u_2*4+u_3*8+...+u_k*2^k$
    With $\displaystyle u_0,u_1,...,u_k \in \{ -1,0,1 \} $ and at most $\displaystyle \tfrac{1}{2}k$ of the $\displaystyle u_i$ nonzero.

    So say if we have n=61 then $\displaystyle \lfloor \log n \rfloor + 1 = 5 $

    In fact, the log (to base 2) of 61 is 5.93..., so its integer part is 5, and $\displaystyle \color{red}k=\lfloor \log n \rfloor +1=5+1=6$, not 5.

    then $\displaystyle 2^5 = 32$ which is definitely not greater than 61. So the first line of the proposition is not correct. Where on earth am i going wrong!! I must be missing something?
    It doesn't explicitly say so, but the context makes it clear that the logs here must be to base 2.
    ..
    Last edited by Opalg; Jul 10th 2011 at 06:53 AM. Reason: added comment
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Another fibonacci proposition
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Feb 28th 2011, 02:55 PM
  2. proof this proposition
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: Dec 19th 2009, 06:25 AM
  3. Proposition Help!?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 29th 2009, 03:16 PM
  4. Proposition induction
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: Sep 23rd 2008, 06:59 PM
  5. Prove a Proposition
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 16th 2008, 02:30 PM

Search Tags


/mathhelpforum @mathhelpforum