« All posts

04.15.2022 - Math / Prime Factorization Uniqueness

In mathematics, the fundamental theorem of arithmetic states that: “Any integer number larger than 1 can be written as a product of prime numbers in one and only one way”.

No matter how you come up with the prime factorization, the set of prime factors might have a different order, but they are always the same set.

In algorithm problem solving, the uniqueness of a prime factorization can be applied in some situations, for example, to check if two strings are made up from the same set of characters, with a different arrangement (anagram).

The idea to solve this kind of problem is, to map the characters in each string to a prime number:

Then multiply them together, if they made up the same integer number, then they’re anagram.

The proof of the uniqueness can be found on Page 16, Section 2 of the Elementary Number Theory: Second Edition book. But Wikipedia has a great summarization:

Suppose we have an integer $n$ that has two distinct prime factorizations $n = p_1 \times p_2 \times p_3 \times \cdots \times p_j$ and $n = q_1 \times q_2 \times q_3 \times \cdots \times q_k$, where each $p_i$ and $q_i$ is a prime.

We see that $p_1$ divides $n$, so $p_1$ divides $q_1 \times q_2 \times q_3 \times \cdots \times q_k$. By Euclid’s lemma, we have that $p_1$ divides some $q_i$, let’s say $q_1$.

Since $p_1$ and $q_1$ are both prime, they must be the same, so $p_1 = q_1$. Cancel both $p_1$ and $q_1$ from the two prime factorizations, we get:

p_2 \times p_3 \times \cdots \times p_j = q_2 \times q_3 \times \cdots \times q_k

Continue the process, eventually, we will find that each $p$ is a $q$. After each cancellation, we cannot run out of $p$ before all the $q$ are gone. This means, $p_1 \times p_2 \times p_3 \times \cdots \times p_j$ are just a rearrangement of $q_1 \times q_2 \times q_3 \times \cdots \times q_k$. The two factorizations are just differ in the order of the factors.

Read more