- 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?
Independent realization from an ancestor's perspective. Created by Brit Cruise.
Want to join the conversation?
- What is the spiral called at1:27?(48 votes)
- It is an Ulam spiral, named after Stanislaw Ulam. You can learn more about it in the video "Sick Number Games."(21 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
That every composite number can be broken down into the sum of equal prime numbers? 30= 5+5+5+5+5+5
- 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)
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.
3. 4 is not prime, find prime factorization of 4 below
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
1. select 7 to be K
1. Select 2 to be K
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.(44 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?
- 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)
- 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)
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.