Results 1 to 2 of 2

Math Help - 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 k=\lfloor \log n \rfloor +1 . which means that 2^k > n. Then we can always write  n = u_0 + u_1*2+u_2*4+u_3*8+...+u_k*2^k
    With u_0,u_1,...,u_k \in \textbracerleft -1,0,1 \textbracerright and at most \frac{1}{2}k of the u_i nonzero.




    So say if we have n=61 then \lfloor log n \rfloor + 1 = 5 then 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
    7

    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 k=\lfloor \log n \rfloor +1 . which means that 2^k > n. Then we can always write  n = u_0 + u_1*2+u_2*4+u_3*8+...+u_k*2^k
    With u_0,u_1,...,u_k \in \{ -1,0,1 \} and at most \tfrac{1}{2}k of the u_i nonzero.

    So say if we have n=61 then \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 \color{red}k=\lfloor \log n \rfloor +1=5+1=6, not 5.

    then 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; July 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: February 28th 2011, 02:55 PM
  2. proof this proposition
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: December 19th 2009, 06:25 AM
  3. Proposition Help!?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 29th 2009, 03:16 PM
  4. Proposition induction
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: September 23rd 2008, 06:59 PM
  5. Prove a Proposition
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 16th 2008, 02:30 PM

Search Tags


/mathhelpforum @mathhelpforum