If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

# The fundamental theorem of arithmetic

Independent realization from an ancestor's perspective. Created by Brit Cruise.

## Want to join the conversation?

• What is the spiral called at ? • I guess what I am not getting here is what exactly is the Fundamental Theorem of Arithmetic?
That every number has a prime factorization? 30 = 2*3*5
Or
That every composite number can be broken down into the sum of equal prime numbers? 30= 5+5+5+5+5+5

Thanks,
Victoria •   The Fundamental Theorem of Arithmetic states:
Every integer >1 has a prime factorization
(a product of prime numbers that equals the integer, where primes may be repeated, and the order doesn't matter)
AND
That prime factorization is unique (This is very important)
(for each integer there is exactly one collection of prime numbers that will work, no more, no less)

e.g. 30=2*3*5. No matter how hard we search, we will never find a different collection of primes whose product is 30

So what is this stuff about the sums ?

Basically, it is discussing how Euclid discovered "For any integer X>1, X has a prime factorization".

The video suggests at that Euclid knew that "For any integer X>1, X can be written as a sum of equal primes"

As, it turns out, saying
"For any integer X>1, X can be written as a sum of equal primes",
is the same as saying
"For any integer X>1, X has a prime factorization".

How can these very different looking statements be the same ?

Suppose the first statement is true ( X can be written as a sum of equal primes).
We can find the prime factorization of X as follows:
1. write X as a sum of equal primes, with P added N times i.e. X= P + P + P...+ P
2. Note that this is the same as X=P * N
3. P is prime, so if N is prime we are done.
If N is not prime, then we can find the prime factorization for N using steps 1-3 for N and
substitute the result for N in X= P * N.

e.g.
X=12
1. 3+3+3+3=12
2. 3*4=12
3. 4 is not prime, find prime factorization of 4 below
1. 2+2=4
2. 2*2= 4
3. 2 is prime. done
Substitute 2*2 for 4 into 3*4=12, gives us 3*2*2=12 which is the prime factorization of 12.

Suppose instead, that the second statement is true (X has a prime factorization).
We can find a sum of equal prime numbers equal to X as follows:
1. Select one of the prime factors of X, which we will call K
2. multiply the remaining prime factors of X to produce a product called N
3. Add K, N times to make a sum that equals X

e.g.
X=35
35=5^1*7^1
1. select 7 to be K
2. N=5^1=5
3. 7+7+7+7+7=35

e.g.
X=16
16=2^4
1. Select 2 to be K
2. N=2^3=8
3. 2+2+2+2+2+2+2+2=16

So what this means is, if one statement is true, then the other statement is true as well.
(And if one statment is false, then they are both false)

Hope this makes sense
• •  Primes go on forever, and this was proven quite simply by Euclid -

Imagine that P1 is the first known prime (in our case 2), and P2 is the second and P3 is the third and so on. Multiply all known primes together

P1 * P2 * P3 * P4..... until you reach the last prime you know.

then add 1 to that product. Lets' call this x . x is not divisible by any of the primes you multiplied together, and this means that either there is a prime smaller than x that you don't know, or that x is prime. and you can repeat this process infinitely and will find new primes every time.

Credit for that goes to Euclid.
• I'm confused about prime factorization. Around the mark, it's said that any composite number can be broken down into smallest equal numbers. DO you really mean all composite numbers, because if I try a number like 56, I can only break it into 7x8, or 7x4x2, or 7x2x2x2 -- not by multiplying equal prime numbers.
What am I missing?
Thanks. • Why is 2 a prime number it has 1 and 1. Which are two numbers, which makes the number 2 equal. • what was the Greek arithmetician's name i couldn't get it ? • Are there any other methods of TRYING to find a pattern in prime numbers other than the Ulam spiral and is it possible to find one? • Believe me, we've tried. A lot. There might be a pattern, but whatever it is, humans haven't found it yet. And in my opinion, if there was a pattern, prime numbers won't be half as interesting as they are.

Also, in case you don't know, there are two common tricks to finding primes, but they're not perfect - they have exceptions and limitations, but we do have them.
6k +/- 1 : this can find numbers that aren't divisible by 2 or 3, and they are often primes if the numbers you're dealing with are less than 100.
You can also multiply all known primes together and add one to find a new prime number, but this misses a lot of prime numbers less than the new one you found, and, its hard to perform with large numbers.
• • For numbers smaller than a 1000 I would use divisibility criteria first (by 2,3,5,7,11) and if it doesn't work by Fermat's factorization method : Example. consider 377.
The general idea is writing 377 as a difference of two squares and then using the "third identity" (a-b)(a+b) = a^2 - b^2.
The smallest square greater than 377 is 20^2. So :
377 = 20^2 - 23 (23 is not a square, so I add 1 to 20 and compensate by adding 2·20 + 1 to 23) so...
377 = 21^2 - 64 = 21^2 - 8^2 = 13 · 29.
Of course sometimes you need to do more than one iteration before getting hold of the square...the "worst" situation is if the number you started with is prime. Knowing (or being able to find quickly and easily) all squares < 1000 is of great help to start the procedure. A long example is : 949 = 31^2 - 12 = 32^2 - 75 = 33^2 - 140 = 34^2 - 207 = 35^2 -276
= 36^2 - 347 = 37^2 - 420 = 38^2 - 495 = 39^2 - 572 = 40^2 - 651 =
= 41^2 - 732 = 42^2 - 815 = 43^2 - 900 = 43^2 - 30^2 = 13 · 73. • 