Main content

## Computer science

### Course: Computer science > Unit 2

Lesson 4: Modern cryptography- The fundamental theorem of arithmetic
- Public key cryptography: What is it?
- The discrete logarithm problem
- Diffie-hellman key exchange
- RSA encryption: Step 1
- RSA encryption: Step 2
- RSA encryption: Step 3
- Time Complexity (Exploration)
- Euler's totient function
- Euler Totient Exploration
- RSA encryption: Step 4
- What should we learn next?

© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice

# 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 at1:27?(52 votes)
- It is an Ulam spiral, named after Stanislaw Ulam. You can learn more about it in the video "Sick Number Games."(24 votes)

- 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(23 votes)- 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 at2:05that 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(98 votes)

- do they end or go on forever and never stop?(8 votes)
- 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.(45 votes)

- I'm confused about prime factorization. Around the2:10mark, 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.(19 votes)- When you break it down to 7*2*2*2, you /are/ breaking it into its constituent primes. Remember - 2 is a prime number (the only even prime, actually), as it can only be divided by 1 and itself.(13 votes)

- Why is 2 a prime number it has 1 and 1. Which are two numbers, which makes the number 2 equal.(5 votes)
- 1x1 doesn't equal 2. it equals 1. Primes deal with multiplication, not addition.(11 votes)

- what was the Greek arithmetician's name i couldn't get it ?(2 votes)
- He is Euclid of Alexandria. He is the father of Geometry, I think and he wrote the book, Elements which was a influential work of geometry till the 1900s.(9 votes)

- 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?(4 votes)
- 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.(4 votes)

- easy way of finding factors of any number(2 votes)
- 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.(6 votes)

- I tried mapping out all the prime factorizations from 2 - 20, and I saw a problem. What is the prime factorization of 16? 20? 8? This is confusing!(1 vote)
- Can you take out the music?(0 votes)
- Actually, I like it. It's not so loud so it may distract you. and also makes you feel that you're getting to know the solution of mysteries that baffled the great minds of history.(8 votes)

## Video transcript

Imagine we are living
in prehistoric times. Now, consider the following. How did we keep track
of time without a clock? All clocks are based on some
repetitive pattern which divides the flow of time
into equal segments. To find these
repetitive patterns, we look towards the heavens. The sun rising and falling
each day is the most obvious. However, to keep track of
longer periods of time, we looked for longer cycles. For this we looked
to the moon, which seemed to gradually grow
and shrink over many days. When we count the number
of days between full moons, we arrive at the number 29. This is the origin of a month. However, if we try to
divide 29 into equal pieces, we run into a problem. It is impossible. The only way to divide
29 into equal pieces is to break it back
down into single units. 29 is a prime number. Think of it as unbreakable. If a number can be broken
down into equal pieces greater than one, we call it
a composite number. Now, if we are curious, we may
wonder how many prime numbers are there, and how
big do they get? Let's start by dividing all
numbers into two categories. We list the primes on the
left, and the composites on the right. At first they seem to
dance back and forth. There is no obvious
pattern here. So let's use a modern technique
to see the big picture. The trick is to
use a Ulam spiral. First we list all
possible numbers in order in a growing spiral. Then we color all the
prime numbers blue. Finally, we zoom out to
see millions of numbers. This is the pattern of primes,
which goes on and on forever. Incredibly, the entire
structure of this pattern is still unsolved today. We are on to something. So let's fast forward to around
300 BC in ancient Greece. A philosopher known as
Euclid of Alexandria understood that
all numbers could be split into these two
distinct categories. He began by realizing that
any number can be divided down over and over until you
reach a group of smallest equal numbers. And by definition,
these smallest numbers are always prime numbers. So he knew that all
numbers are somehow built out of smaller primes. To be clear, imagine the
universe of all numbers, and ignore the primes. Now, pick any composite
number and break it down, and you are always left
with prime numbers. So Euclid knew that
every number could be expressed using a
group of smaller primes. Think of these as
building blocks. No matter what
number you choose, it can always be built with
an addition of smaller primes. This is the root
of his discovery, known as the fundamental theorem
of arithmetic, as follows. Take any number, say 30, and
find all the prime numbers it divides into equally. This we know as factorization. This will give us
the prime factors. In this case, 2, 3, and 5
are the prime factors of 30. Euclid realized
that you could then multiply these prime
factors a specific number of times to build
the original number. In this case, you simply
multiply each factor once to build 30. 2 times 3 times 5 is the
prime factorization of 30. Think of it as a special
key, or combination. There is no other
way to build 30 using some other groups of prime
numbers multiplied together. So every possible number
has one, and only one prime factorization. A good analogy is to
imagine each number as a different lock. The unique key for
each lock would be its prime factorization. No two locks share a key. No two numbers share
a prime factorization.