# Thread: Trouble with a proposition

1. ## 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

2. ## Re: Trouble with a proposition

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