# Homework Help: How to prove?

1. Feb 24, 2005

### msmith12

For a positive natural number n, we use
$$|n|= \log_{2}n$$
as the measure of the size of n (which is the number of bits in n's binary representation). however, in most cases the size of n can be written as log n without giving an explicit base (the omitting case is the natural base e). Show that for any base b>1,
$$\log_{b}n$$
provides a correct size measure for n, i.e., the statement "a polynomial in the size of n" remains invariant for any base b>1.

This was a problem in my homework for cryptography...

I understand the first part of the problem, which basically means that for any base, b:

$$\log_{b}n=|k| => b^{[k]+1} > n$$
where [k] equals the floor of k.

but beyond that, I really have no idea...

thanks for any help

matt