Prime Factorization
We care about the properties of two sets of numbers.
Natural Numbers, N = {1, 2, 3, 4, . . .}
Integers, Z = {. . . , -2, -1, 0, 1, 2, . . . }
We further concern ourselves with a subset of these sets, the set of Prime Numbers.
To understand prime numbers we must know what division over the set Z is.
Definition of Divides
If a, b, are elements of Z we say that a divides b, a|b, if ac = b for some c that is an element of Z.
During your childhood you may have been told that division is just a special case of multiplication, this definition of division states that explicitly. Division is derived from the fact that a number b can be expressed as the product of two numbers a and c. Division undoes this product, that is b/a = c.
Definition of Prime
An integer n > 1 is Prime if the only positive divisors of n are 1 and n.
Prime numbers are just a special kind of integer whose set identity is determined by the set of divisors they all have, in this case only n and 1.
The primary motivation for studying Prime numbers is that every natural number can be constructed out of primes in a unique way, which leads us to the most fundamental theorem of Number Theory.
Fundamental Theorem of Arithmetic
Every natural number can be written as a product of primes uniquely up to the order of the factors.
Finding the unique product of primes for some number is known as Prime Factorization.
Example. n = 1300
The sum of the digits of n is divisible by 2, so 1300/2 = 650
therefore n = 2*650
650 is divisible by 2, so 650/2 = 325
therefore n = 2 * 2 * 325
325 is divisible by 5, so 325/5 = 65
therefore n = 2 * 2 * 5 * 65
65 is divisible by 5, 65/5 = 13
so n = 2 * 2 * 5 * 5 * 13
13 is a prime number so we know we've completed the prime factorization
Hence, n = 2^2 * 5^2 * 13
Prime Factorization as a process has two key properties:
(1) Prime factors are unique, meaning that any give number n can only be written as a product of primes in one way.
(2) For some numbers n, finding this unique product of primes is incredibly difficult or rather computationally costly.
The following two theorems cover key properties of Prime Numbers.
Euclids Theorem
There are infinitely many prime numbers.
We care about this property because it alludes to the computational complexity of finding prime factors, we are searching for a set of bounded numbers out of a potentially infinite amount.
Primes of the Form ax + b
There are infinitely many primes of the form ax + b where a and b are fixed integers with a > 1 and x varying over the natural numbers.
We care about this property because it it reveals that prime numbers can be written as polynomials, in this case a linear polynomial (degree 1).
To get a feel for the computational complexity of prime factorization, lets define a function that outputs the number of primes less than some number x.
π(x) = #{p element of N : p <= x is a prime}
π(6) = #{2, 3, 5} = 3
π(10) = #{2, 3, 5, 7} = 4
We now graph this function with an upper bound of x = 100,000
![Posted Image]()
Notice that the number of primes is always increasing but become less dense for greater numbers of x.
The problem is that for large numbers of x the function π(x) is computationally costly given is requires us to count each prime individually. That cost comes from us having to check the set of divisors for each and every number less than x.
Luckily there is a formula for π(x)
Prime Number Theorem
The function π(x) is asymptotic to x/log(x).
Asymptotic means that π(x) is approximately equal to x/log(x) and the accuracy of that approximation increases for larger and larger values of x.
This theorem paired with a clever algorithm makes finding really big prime numbers computationally easy.
At this point we now know some amazing facts with far reaching applications.
Any natural number can be represented uniquely as a product of prime numbers. To take some number, especially really big ones, and factor it into primes is really difficult even for big super computers. However, to find really big prime numbers is quite easy thanks to the Prime Number Theorem.
The upshot is that we could take two really big prime numbers p and q we've found via Prime Number Theorem and take their product n = p*q. We know the prime factor of n is p*q but everyone else will have a extremely difficult time finding the prime factor of n even if they know what n is.
Sound familiar?
