Representation

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

• $6 = 2\times3$
• $24 = 2^3\times3$
• $3087 = 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 $N$ will have at most one prime factor $\geq\sqrt{N}$.

If an integers $n$ has $m$ prime factors $(p_1 < p_2 < ... < p_m)$. Then either,

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

Proof: Using contradiction for $N$, if the above statement is not true, then there must be two prime factors, $p_1$ and $p_2$,​​ such that:

$p_1 \geq \sqrt{N},p_2 \geq \sqrt{N}$

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

In that case $p_1 \times p_2 > N$, and hence they can’t be factors of $N$.

---

Property: If $N$ has a prime factor $p > \sqrt{N}$. Then the power of $p$ in prime factorization of $N$ is $1$

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

---

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