Prime Factors

In this lesson, we'll discuss about prime factorization of prime numbers.

We'll cover the following

Representation

Any integer can be represented as the product of a power of primes. For example:

  • 6=2×36 = 2\times3
  • 24=23×324 = 2^3\times3
  • 3087=32×733087 = 3^2\times7^3

Breaking an integer into its prime factors with their corresponding powers is called prime factorization.

Prime factorization of an integer is a very common problem and will reoccur in a wide range of topics, hence it is important to know an efficient way to do it.


Prime Factors

Property: An integer NN will have at most one prime factor N\geq\sqrt{N}.

If an integers nn has mm prime factors (p1<p2<...<pm)(p_1 < p_2 < ... < p_m). Then either,

  • All prime factors are less than or equal to N\sqrt{N} or,
  • All prime factors except pmp_m are less than or equal to N\sqrt{N}.

Proof: Using contradiction for NN, if the above statement is not true, then there must be two prime factors, p1p_1 and p2p_2,​​ such that:

p1N,p2Np_1 \geq \sqrt{N},p_2 \geq \sqrt{N}

But since p1p2p_1 \neq p_2, both can’t be equal to N\sqrt{N}.

In that case p1×p2>Np_1 \times p_2 > N, and hence they can’t be factors of NN.


Property: If NN has a prime factor p>Np > \sqrt{N}. Then the power of pp in prime factorization of NN is 11

Proof: Again, by contradiction, if the power is greater than 11, then p×p>Np \times p > N, which is not possible.


In the next lesson, we’ll see how to find the prime factorization of a number.

Get hands-on with 1200+ tech skills courses.