Prime Factorization and Induction

676 Views Asked by At

I have a discrete math problem and I need some guidance on where to start:

Let $ n \geq 2$ and let $n = p_1p_2...p_k$ be its prime factorization, where the primes are not necessarily distinct. Prove that $ k\leq \log_2(N)$.

Hint: prove the equivalent statement $n\geq 2^k$ by induction on $k$.

I'm not look for a full fledge answer but a starting point. So far I'm aware that $k$ is how many prime numbers are needed to build $n$ and that I'm asked to prove that $n$ will always be equal or greater than $2^k$.

Thanks.

EDIT 1:

This is what I have so far:

Proof n≥ 2^k

Base case n = 2 n = 2 is prime therefore k = 1 2 ≥ 2^1 2 ≥ 2^1 2 ≥ 2

Inductive case n > 2 Case I: If n is prime, then k = 1 and it will be the same as the base case.

Case II:

1

There are 1 best solutions below

1
On

You just need to estimate the primes. We have $p_i\geq 2$.