# Trouble with a proposition

Printable View

• Jul 9th 2011, 08:18 PM
liedora
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
• Jul 10th 2011, 12:18 AM
Opalg
Re: Trouble with a proposition
Quote:

Originally Posted by liedora
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.
..