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

[@pablozaid6078]

8:56 I think it should be 1 - (1/4)⁵

[@jakubtokarski5531]

That was my thought thank you

[@oro5421]

Thought the same :)

[@raynahmed6155]

@@jakubtokarski5531jjjj

[@Camman18family]

This proves that you did watch the video 500 times

[@coopergates9680]

@@Camman18family The errors in this video can be spotted pretty easily tbh

[@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

[@hypercoder-gaming]

Actually it checks 1 to 2^n which is greater than p

[@NexusOfChaos]

@@hypercoder-gaming thx for the correction, been a while since ive seen the function myself

[@simohayha6031]

There is also Mill's constant which gives primes for every input n where n ranges over the natural numbers. Problem is it grows extremely fast and we don't know all the decimal digits, but it's proven that it yields primes for all n, even something as crazy as million or G64.

[@anon1963]

there is no mathematical formula that produces prime numbers yet. it would be the end of network security since so many things rely on primes

[@proton..]

:3

[@oro5421]

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

[@movax20h]

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.

[@danielsharp2402]

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.

[@tyjacobs6822]

1:40

[@kshysztof9649]

Your vides are really good. Motivating to some extent, thank you!

[@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!

[@ranchoabilities7928]

Bro this guy should have a million subs, UNDERRATED

[@midnight8654]

and he’s back with two videos!

[@tyjacobs6822]

3:18

[@IbnBahtuta]

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

[@KneeOfficial]

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

[@stanleydodds9]

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.

[@jsutbule]

I will read all of that.

[@jsutbule]

I read all of that. I have no idea what I just read.

[@4r_ff]

@@jsutbuleSame. What is Fermat's little theorem???

[@probablypeenuts]

my brain hurts

[@theunifun4903]

I read allat, and i dont know who you are but you are very good math, see what you described is correct, disproving the claim that its alway 0

[@Lokalgott]

Well explained!

[@ems951]

I actually learned a lot from you.

[@coopergates9680]

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.

[@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

[@MooverCat]

Beautiful!

[@movax20h]

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".

[@muskyoxes]

I was recently shocked to hear that before Euler, nobody in the world knew a prime number bigger than a million. It is much more difficult to find primes by brute force than it looks

[@palmakzx]

amazing vid ❤️

[@Slerdus]

I agree

[@zaviyargul]

I understood nothing,I liked it 👍

[@Very_Rando_person]

Same

[@RubyPiec]

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

[@user-ud6ui7zt3r]

Does the Miller-Rabin test have any statistical Out Liars ?

[@douglasstrother6584]

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

[@benjaminwasfound2]

0:28 willan's formula, although it is very inefficient

[@nuggetontrend]

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

[@jonathanschenck8154]

Analog & Quantum Computations for checks, with base value checks can be more than just the slow data overflow that of float.

[@jonathanschenck8154]

Do not use any non integers, as binary doesn't like decimals.

[@jonathanschenck8154]

But don't use engineers for SSD memory figures except for analog memory devices that discrepancies don't exist for. Discrepancies exist for various base's decimal points & fractions.

[@jonathanschenck8154]

Non real base integers don't like to be divided. So calculating fractions like 1/3 isn't recommended by most number bases. Or 1/... As accuracy of numbers fails with pi as it isn't divisible after the decimal. Also the value 3 looks really weird in computer code. Like in floating point.

[@o_s-24]

Such a simple yet complex problem

[@tyjacobs6822]

2:45

[@GabAguy]

You can check if a number is divisible by 2 3 5 7 and if its not then it is a prime number

[@nycoshouse]

is there better method to identify only twin primes ? ( to compute Brun's constant up to 10^20 )

[@tyjacobs6822]

4:23

[@tyjacobs6822]

4:23

[@SaagarNayak]

Every prime number can be written as 6n + 1 or 6n - 1 which are twin primes

[@alejandropulidorodriguez9723]

splendid

[@coopergates9680]

8:40 Fortunately, this is not the average probability, it is the (worst case). Semiprimes of the form (2k + 1)(k+1) and some three-factor Carmichael numbers have almost a 1/4 proportion of strong liars, but for most composites, the ratio is far smaller. No bases between 1 and 436, exclusive, are strong liars for 437.

[@k3nu85]

In 0:20, 2^82589933-1 should be over centillion. Also. Did you know that 67+1/4489= Supergolden ratio ^11?

[@Porto5452]

651 is not a Carmichael number since 2^651 = 281 (mod 651). The Carmichael number you were looking for was 561 = 3*11*17. In the Miller-Rabin test you actually square the number k-1 times, where k is the exponent of the largest power of 2 divisible by p-1, so you squared 13 1 extra time when you used it to determine if 221 was prime. Finally the probability that the Miller Rabin test works using a composite for a random base is always less than 1/4, usually much lower than that. It can only be close to 1/4 if the composite number is of the form (n+1)*(2n+1), where n is an integer and n+1 and 2n+1 are primes, so n must also be a multiple of 6 for large values of n. The rest of the video was good and well animated so keep up the good work and try to make less mistakes next time. Edit : The sequence used in the Lucas-Lehmer primality test starts with s0 = 4 and not s1 = 4. This means that you need to check if the p-2th term is divisible by p to determine if 2^p-1 is prime. Also a number can't be divisible by 32 but not by 16, since 16 is a divisor of 32. Maybe you meant that if a number was divisible by 16 but not by 32 then the largest power of 2 divisor of that number was 16.

[@thenew3dworldfan]

Yeah, I was going to say that too.

[@fortcraftgaming2136]

Do Try to do try to find X axisis value

[@appel-seed_]

Yes there is a formula for generating primes It's made by c p Willians at 1964

[@dungnguyen-um3gv]

Google is right with you!

[@RA41DW0U]

when Math Prime says "die" you actually die for real

[@PraviLukijanJC]

This number goes in, the square hole

[@alexanderscott2456]

This is my algorithm: If it ends in a 2 or 5: Not Prime If it doesn't end in a 2 or a 5: It is Prime You're welcome

[@wschess]

Yep, definitely how it works. Can confirm

[@ecromancer]

All even numbers except for 2 and all numbers ending with 5 except 5 are not prime numbers.

[@muskyoxes]

I have made huge advancements in this method. If the digits add up to a multiple of 3: not prime. If it's not divisible by 2, 3, or 5, it looks prime when seen on paper and therefore is prime. Fermat used this method.

[@Rockety521]

I mean, yeah, but my algorithm is simpler: If I can divide it by any number that isn't itself or 1, it's not prime, else it is... simple, right?

[@coopergates9680]

5:51 Sorry to be 'that guy' but the first Carmichael number is 3*11*17 = 561, you simply swapped a couple digits.

[@Swagpion]

Almost every single prime number touches a multiple of 6. 2 and 3 are the only excrptions, because they are the factors of 6. This is because a prime cant be an even amount away from a Mo6, or it would be even, and 3 away because it would be threeven. And 5 away is 1 away from another multiple of 6. And now I wonder what the smallest multiple of 6 that doesnt touch any primes, if one exists at all.

[@Swagpion]

This fact also proves that an infinite amount of the primes are twin primes. Because there are infinite primes and they can never stop being in pairs.

[@AA-100]

120 is a multiple of 6 and is not 1 away from a prime number 119 = 7×17 121= 11×11

[@programmieraufgaben8391]

cool!

[@ryanchiang1202]

Then what is Willian’s theorem then?

[@tyjacobs6822]

2:14

[@rodrigoqteixeira]

16:58 the typo in "idnetity" unstead of "identity" lol

[@ElevatorFan1428]

You have a typo! "unstead" instead of "instead"

[@RoundShades]

You can be great at math, or English. Not both.

[@rodrigoqteixeira]

@@ElevatorFan1428 :(

[@stilze]

Whilst it is an extremely slow and (when it comes to computers) inefficient way of generating primes, there a formula for the prime numbers: Willans' formula.

[@user-ud6ui7zt3r]

Wait… I thought all the 🦕 🦖 divisaurs went extinct ☄️, because of a big asteroid, a long time ago.

[@JustA1ex2465]

Finally now I can achieve heaven

[@JustTriangle]

37

[@sababugs1125]

there is a formula to generate the nth prime number

[@Camman18family]

how

[@practicemodebutton7559]

16:35 you spelled identity 'idnetity'

[@raynahmed6155]

1 - (1\4)

[@RoundShades]

!! Huge Prime !!

[@ten-faced-carrot]

Here is a simple approach to check if any number n is a prime, that completes in 1 step only. Between 0 and 1000000, roughly 7% of numbers are primes, and that number will get smaller the further we go, so we can reasonably assume, that any number n is not a prime. Here is a simple C implementation of that algorithm: bool isPrime(int n){ return false; } I've benchmarked it, and for 10000000 Numbers, it has an error rate of 6.65%

[@RoundShades]

I love mathematics, but I live computational reasoning even more, it's like the same world being interpreted in 2 entirely separate ways

[@insertcreativenamehere492]

Yeah, and the error rate gets smaller as you go higher! For 10^100 numbers, the error rate is 0.434%, and for 10^1000000, the error rate is just 0.00004%!

[@SeaBeastHunter]

Jojo reference

[@MrAdamdgross45]

You had me until the Seive of Atkins. 🙁

[@JamesIsbell-up4yu]

What good is all this prime number research?

[@njgskgkensidukukibnalt7372]

cryptography Also the tools developed to understand more about prime numbers are good enough reason to study them

[@RoundShades]

It generates energy and solves world hunger. ...Is what you'd like me to say. What good is space travel, everyone says on the comments section from the keyboard of their cell phone. Imagine asking what good does paper achieve and mailing it to the paper factory on a piece of paper?

[@kcchan3263]

0:49

[@jhawar-ji]

9:07 1-1/4 ~ 99.9%? How?

[@FelipeSouza-oc9tj]

He just forgot to put the power on the 1/4, it's 1/(4^5)

[@yeetasfahitas]

17:03 idnetity 😭😭

[@mihaleben6051]

You get an ouija board. Thats how. Maybe

[@reelGeohere]

9:35

[@AnaMunoz-el5ch]

♾️

[@sodiboo]

0:28 bro forgot about 1 + sum{i=1 .. 2^n}(floor((n/(sum{j=1 .. i}(floor((cos(pi*((j-1)!+1)/j))^2))))^(1/n)))

[@waldogmd]

hey whats up

[@tyjacobs6822]

3:38

[@damianojeda938]

why is one not prime

[@QbdulloK]

Because any prime number has 2 divisors. 1 and itself. The number 1 has only one divisor, which is 1. That's why it isn't prime

[@mateswinter3i]

One is himself

[@user-ud6ui7zt3r]

yoo rook MAH-VELOUS

[@zhixinhuang4084]

My favorite color is red and red and red and red and red and red and red and red and red and red and red and red & I think you didn’t read all of that.

[@ToanPham-wr7xe]

😮

[@explosive1984]

P p p p p ppppprime? Like minos prime ultrakill??? Judgement????

[@ucngominh3354]

hi

[@carteraplus3020]

Read this as how to find VERY BIG phone numbers

[@user-rp7mc5ju1u]

the biggest prime number is a mersenne prime

[@movax20h]

Biggest know prime number.

[@MonsterCity277RS]

Here before 100K views

[@SillyPerrin]

2:16 divisor is pronounced “div-aye-suh-r”

[@nnoxie.a]

"di·vigh·zer" is a less ambiguous way to write that

[@thje_mop]

100000001

[@raynahmed6155]

-1

[@Roperdo7]

240th like and 26th comment

[@Roperdo7]

1600th view

[@nokhinsiu7210]

((j-1)!+1)/j,if = odd then yes no then no

[@stormy1514]

what is this called

[@bruhifysbackup]

​@@stormy1514 willsons theorem

[@AdrianCHOY]

Why the obsession? What’s the application?

[@michaelpenklis3104]

With the advancement of modern computers and mathematicians out there, will they ever find a prime number bigger than 2^82,589,93 3-1

[@AA-100]

As of May 2024, they haven't yet

[@Heillygamings]

Say alusmabinsoainia in real life

[@saba5412]

46 mins, 70 likes... Fell off

[@Sunbeast_the_9th]

3 hours 1121 views he really fell off

[@aydhin]

no views in 30 seconds he really fell off

[@justsaadunoyeah1234]

SHUT UP

[@tyjacobs6822]

1:36

[@currywurst7229]

4 minutes 9 likes fell off

[@Zachyshows]

13 minutes 23 likes fell off

[@alejandropulidorodriguez9723]

in 4 minutes to everyone's liking you will fall off a bridge

[@justsaadunoyeah1234]

SHUT UP OR I WILL GO TO YOUR HOUSE

[@catWithFunkyFace]

not funny

[@soogers]

14 minute 2 likes fell off ​@@catWithFunkyFace

[@hypercoder-gaming]

We do know about a function for generating primes... en.wikipedia.org/wiki/Formula_for_primes

[@GiaHuy-oe8ck]

This 4.46087557183754...×10^686

[@zhixinhuang4084]

Dinobaby is my new wallpaper and my favorite color ever and it’s a good color to use for a portrait and I like to draw it with a little color to show it to people and it looks great and it looks really good 👍 and it’s so pretty and I love how it’s a little more of my favorite colors and it is very pretty and it makes it so much better to have something to draw on you like I love it so I think I would like it, all of that is not true I’m guessing you didn’t read all of that 🧽🧸

[@thomazsoares1316]

11 101 1001 10001 ... 10ⁿ + 1 = prime number

[@A_literal_cube]

1001=7*11*13

[@excelmaster2496]

It's not divisible by 2, 3 or 5, but there's still a lot of other numbers

[@MartinChristensen-bk8ur]

10^n + 1 can be prime only if n is a non-negative power of 2, as it is with 11 and 101. 10^4 + 1, 10^8 + 1, and 10^16 + 1 are all composite, and I know of no other prime numbers that are one more than a power of 10.

[@mmbloveaugust3669]

Nice britishing pooks🥰♥️🫶🫶