How to Find VERY BIG Prime Numbers?

Humans have been looking for prime numbers for a very long time. We still haven’t found the formula for generating prime numbers. However, we have developed methods to discover increasingly larger primes.

Chapters:
00:00 The largest prime
00:37 Infinite number of primes
02:38 Sieve of Eratosthenes
03:14 Sieve of Atkin
04:46 Fermat's Little Theorem
06:10 Miller-Rabin test
09:18 AKS primality test
10:05 Mersenne Primes
11:43 Perfect Numbers
13:50 Lucas-Lehmer primality test
15:15 Intro to Group Theory
19:15 Lucas-Lehmer test proof
24:44 GIMPS

[NexusOfChaos]

there is actually a function that for every value n it computes exactly the nth prime number (which we'll call p). the problem is it is so slow to compute that it is literally faster to manually check every number 1 to p if they are prime before this function can tell you what p is, bc tbh that's what the function is doing too

[danielsharp]

Really great refresher video for someone who already knows most of these and only has some gaps. A bit of constructive criticism though. Leave pauses between thoughts. If you are not already intimate with the concepts it's hard to follow. Sometimes separate topics get a little mashed together because there's nothing signifying that the thought ended. I know it adds to the video length but something to consider.

[IbnBahtuta]

It took just 10 seconds to find the current biggest prime number to date. Just use a search engine.

[Loffai]

As a student who has just started Pre-Calc, this is some very interesting info, I will use it for the forseeable future, thanks!

[marcellmate]

New prime has just been unlocked a few days ago!

[coopergates]

7:01 If you are hoping to use the M-R test to (factor) a number, you may need to perform x+1 modular comparisons, but to check if it is prime, you only need x of them. Fermat's Little theorem proves that the (x+1)th test will *never* yield a remainder of -1.

[stanleydodds]

22:47 this is incorrect. 0 is not necessarily the only element of X that has no inverse. Luckily, this doesn't matter for the proof. We only need the fact that |X*| < q^2. It doesn't actually matter if it's exactly 1 less element, or many less elements. (actually, the proof still works even without the strict inequality).

For an example of why you can't say this, look at q = 11, then the non-zero elements 5 + sqrt(3), 5 - sqrt(3), and all their multiples have no inverses; to prove this (without checking every element), we know (5 - sqrt(3))(5 + sqrt(3)) = 5^2 - 3 = 0 (mod 11). If an inverse existed, multiplying both sides of this equation by the inverse would give a non zero element equals zero, contradiction.

In general, what you say is only true in an integral domain (a ring with no zero divisors). For this specific ring, Z/qZ [sqrt(3)], that's only true if 3 is a quadratic non-residue modulo q.

Also, this is only one direction of the proof (showing that if this term in the sequence is 0 mod Mp, then the mersenne number is prime). In order to prove the reverse direction, the fact that if the mersenne number Mp is prime then this term is zero, we do actually need to worry about whether or not elements like 2 and 3 are quadratic residues modulo modulo Mp. In fact, the legendre symbols of 2 and 3 modulo mersenne primes is the reason that we use the sequence starting at 4. It is also possible to perform the test starting with other numbers given that the mersenne number falls into particular congruence classes, but 4 is convenient because it works for all mersenne numbers (this is only important for this direction of the proof though).

For an explicit proof, first note that (1 + sqrt(3))^2 / 2 = (1 + 2sqrt(3) + 3) / 2 = 2 + sqrt(3) = x
Then we have x^(2^(p-1)) = (1 + sqrt(3))^(2^p) / 2^(2^(p-1)) = (1 + sqrt(3))^(Mp + 1) / 2^((Mp + 1)/2)
Using a result stated in this video, and now using the fact that we assume Mp is prime, note that (1 + sqrt(3))^Mp = 1 + sqrt(3)^Mp = 1 + sqrt(3) * 3^((Mp - 1)/2) (mod Mp)
Now compute the legendre symbol 3^((Mp - 1)/2) = (3|Mp) = (Mp|3) * (-1)^((3-1)(Mp - 1)/4) = (Mp|3) * (-1)^(2^(p-1) - 1) = -(Mp|3) by Euler's criterion and quadratic reciprocity
Then note that Mp = 2^p - 1 = 2 * 2^(2k) - 1 = 2 * 1 - 1 = 1 (mod 3) since p prime is odd (check p = 2 case separately), so (Mp|3) = (1|3) = 1, hence 3^((Mp - 1)/2) = -(Mp|3) = -1
So we have that (1 + sqrt(3))^Mp = 1 + sqrt(3) * 3^((Mp - 1)/2) = 1 - sqrt(3) (mod Mp), and hence (1 + sqrt(3))^(Mp + 1) = (1 + sqrt(3))(1 - sqrt(3)) = 1 - 3 = -2 (mod Mp).
Next, compute the legendre symbol 2^((Mp - 1)/2) = (2|Mp). Here we can just use standard results for legendre symbols of 2, or that 2^(p-1) = 1 (mod p) by Fermat's little theorem to get that p divides (Mp - 1)/2, and since 2^p = 1 (mod Mp) trivially, we have that the order of 2 divides p modulo Mp. Therefore 2^((Mp - 1)/2) = 1 (mod Mp) as the exponent is a multiple of the order. Either way, we then get 2^((Mp + 1)/2) = 2 * 2^((Mp - 1)/2) = 2 (mod Mp)

Combining all of the above, we get that x^(2^(p-1)) = (1 + sqrt(3))^(Mp + 1) / 2^((Mp + 1)/2) = -2 / 2 = -1 (mod Mp). Multiply both sides by y^(2^(p-2)), we get x^(2^(p-2)) = -y^(2^(p-2)) (mod Mp), so finally x^(2^(p-2)) + y^(2^(p-2)) = 0 (mod Mp) as required.

[KneeOfficial]

I don’t like nor have I ever liked math, but you managed to keep me hooked the whole way through, great video

[oro]

This is great!!! I used to wonder how these are found, the main question of the video. Thank you for it

[movaxh]

Great video. A bit fast at places, but really well done. I like that it is pretty dense and fast, as it can deliver way more info.

[muskyoxes]

I wish math videos would do more linking, like here i'll bet most people able to understand this video know the axioms of group theory, and if they don't it'd be easy to point them to one of the million places that go over them

[HuaweiHome-gm]

It's crazy that A number with 25 million digits can't be divided by any number except 1

[francishubertovasquez]

You're an exceptionally gifted mathematician. Period

[RubyPiec]

8:37 I like the subtle dramatic boom when you say "13 is a liar"

[NoProductionsGD]

1:51 One way to make trial division faster is by ruling out all even numbers and all multiples of 5.
even + even always results in even (e.g. 4 + 6 = 10)
The number you are testing will most likely not end in a 5, meaning that all multiples of 5 will not divide into it since the test is not a "stack" of 5s (e.g. 15 + 20 + 25 = 55 is made of 5s, but is not).

[WatchAccount-vwpo]

When your brain is so fried the only thing you catch is 'Idnetity elelment'

[jamesmarlowebito]

In college-level mathematics, a variety of operations are used across different fields of study. Here are some of the key operations commonly encountered:

1. Arithmetic Operations: Addition, subtraction, multiplication, and division are foundational for most calculations.


2. Algebraic Operations: Involves manipulating algebraic expressions and equations, including solving for variables, factoring polynomials, and using functions.


3. Calculus Operations: Includes differentiation (finding derivatives) and integration (finding integrals), as well as operations on limits, series, and multivariable functions.


4. Matrix Operations: Includes addition, subtraction, multiplication, inversion, and finding determinants for matrices, which are essential in linear algebra.


5. Statistical Operations: Such as computing means, medians, variances, standard deviations, and performing hypothesis tests and regression analysis.


6. Trigonometric Operations: Involving functions like sine, cosine, and tangent, and their inverses, used in solving problems related to angles and periodic functions.


7. Complex Number Operations: Includes addition, subtraction, multiplication, and division of complex numbers, as well as finding magnitudes and arguments.


8. Differential Equations: Involves solving equations involving derivatives and applying methods like separation of variables or using numerical techniques.


9. Vector Operations: Such as vector addition, dot product, cross product, and vector normalization, which are used in physics and engineering contexts.



These operations form the basis for more advanced studies and applications in fields such as physics, engineering, economics, and computer science.

[douglasstrother]

"Prime has come today" ~ The Chambers Brothers (sort of)

[movaxh]

AKS test (which was onlt discovered about 15 years ago), is actually super fast. Initially it was not very practical. But still polynomial in number of digits, which us amazing. I think it was initiallt pretty big power, like 12, byt was reduced later to 6. Few years of computation for few thousand digit prime is actually pretty good. Considering brute force, even using sieves would take unimaginable amount of time (quntilions of years would not even scratch the surface of computation). AKS is one of the coolest algorithms of 21st century.

To paper where AKS was explained is called "Primality is in P".

[nuggetontrend]

I really like how 252 digits of 9, one 8 and 253 digits of 9 is a prime number