How to Find VERY BIG Prime Numbers?

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

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

[@IbnBahtuta]

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

[@barrianic4]

r/technicallythetruth

[@Akuma.aa0]

Although the rate of discovering one is extremely hard

[@marcellmate425]

New prime has just been unlocked a few days ago!

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

[@evnnxi]

I will read all of that.

[@evnnxi]

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

[@coolio-46]

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

[@liquidcashews]

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

[@zaviyargul]

I understood nothing,I liked it 👍

[@Very_Rando_person]

Same

[@MorbiddaPlays]

bruh, i'm in 9th grade and i don't even understand a little bit....wait...am i just dumb?

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

[@midnight7175]

and he’s back with two videos!

[@tyjacobs6822]

3:18

[@oro5421]

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

[@RubyPiec]

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

[@TheCaregiverSITMOB]

YOU AGAIN?!

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

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

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

[@KneeOfficial]

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

[@HuaweiHome-g1m]

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

[@FranklinLee-t3k]

@@HuaweiHome-g1m Then imagine a 41 million digit number can only be divided by 1 and itself.

[@francishubertovasquez2139]

You're an exceptionally gifted mathematician. Period

[@douglasstrother6584]

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

[@WatchAccount-vw7po]

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

[@jamesmarlowebito8982]

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.

[@Lokalgott]

Well explained!

[@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 1000001 is not).

[@nuggetontrend]

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

[@ems951]

I actually learned a lot from you.

[@o_s-24]

Such a simple yet complex problem

[@tyjacobs6822]

2:45

[@matei_woold_wewu]

1:36 i reccomend use a fraction as “÷”

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

[@benjaminwasfound2]

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

[@kshysztof9649]

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

[@AmazingAmbro1]

Miller-rabin test is basically just among us

[@FranklinLee-t3k]

Speaking of composite numbers, we know that Graham’s Number is composite. It’s divisible by 3, and its prime factorization is made up of only 3s.

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

[@walterbrownstone8017]

To a heathen like me, a prime number represents an anchor in time. So this is kind of an interesting job.

[@MooverCat]

Beautiful!

[@smithfrederick2]

(10^641 +1)/11 = 90909090......91 is prime with 640 digits, 641 is also prime, and the expression on top is 1000...01 with 641 digits (10^3011 +1)/11 = 90909090.....91 is prime with 3010 digits, 3011 also prime

[@RA41DW0U]

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

[@ranchoabilities7928]

Bro this guy should have a million subs, UNDERRATED

[@justinburchard3344]

IDNETITY 16:34 16:34 16:34 16:34 16:34 16:34 16:34 16:34 16:34 16:34 16:34 16:34 16:34 16:34 16:34 16:34 YEAH BABY

[@rdbchase]

"How to Find VERY BIG Prime Numbers? [sic]" -- that is declarative, not interrogative.

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

[@HamzaDev754]

Understood 40%, but I really like it

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

[@warioshomas100]

i used to go by the logic of 'if it isnt a multiple of 2 3 5 or 7 its probably prime'

[@coopergates9680]

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

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

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

[@stargazer7644]

@@muskyoxes44521?

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

[@Jhshsshshshhs]

I feel so dumbfounded seeing other people (probably twice my age) be so smart when im just starting highschool 😭

[@k3nu85]

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

[@JohnBerry-q1h]

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

[@dh605x]

561 is a Carmichael number, not 651. Sorry to be so pedantic on that one.

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

[@palmakzx]

amazing vid ❤️

[@Slerdus]

I agree

[@W-Pentomino]

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

[@miyu1424]

It's so inefficient, it can barely be considered a formula for generating primes and is more of a fun thought experiment

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

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

[@PraviLukijanJC]

This number goes in, the square hole

[@ryanchiang1202]

Then what is Willian’s theorem then?

[@tyjacobs6822]

2:14

[@yafyafyaf]

6n±1 can be good but it won't word for 120 i think

[@ArtemSayapov]

1:38 shouldn't it be k + 1/p? Pardon if I am wrong, I don't thank that's how you show remainders

[@debmalyalodh1]

This video is outdated as of 22nd October 2024

[@JustA1ex2465]

Finally now I can achieve heaven

[@fortcraftgaming2136]

Do Try to do try to find X axisis value

[@phuonglinh4775]

14:02 HOW DID YOU KNOW MY NAME

[@Anonymous-e5u]

6:55 nice

[@FranklinLee-t3k]

how many digits does that number at the end have?

[@JohnBerry-q1h]

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

[@sababugs1125]

there is a formula to generate the nth prime number

[@Camman18family]

how

[@PeriodicTableLover2]

16:32 error: "idnetity element"

[@SeaBeastHunter]

Jojo reference

[@RobotKiwiTheFailureKid]

Any Even Number Exept 2 And Numbers That End In 5 And 0 Is Composite

[@ultimasvalk]

I got lost at L-L test proof lol

[@benjamineppler3770]

The prime number was found just for pefect numbers or something else( all factors of n added up = n is the definition of a perfect number and that prime number in the thumblail was found to try and find an odd perfect number bc all perfect numbers exept the holy perfect number thats non-even ( if even existant ) ( all even numbers are divisible by 2 and no non-even ( = odd ) numbers are not divisible by 2 ( no matter what ) ) ) Mersene primes a prime if the prime number is ( 2^n ) -1 and its the same whith frivvel primes but whith - and + swaped and 3 is a mersene prime and a frivvel prime because 3=2^1+1=2^2-1=prime

[@francishubertovasquez2139]

No one had presented the calculation method you have taught in that video and in your other lecture video, only you Sham Lahm whether you're a real person or AI, I don't care, I the CaesarKing shall add 3% of energy to money conversion once only for your presentation because that's rare and was meticulously researched in time. Let it be

[@mr.redlazer9173]

Meanwhile CD Wilans who made a prime number formula in 1960’s (it’s not used cus it’s slower then modern algorithms)🗿

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

[@mihaleben6051]

You get an ouija board. Thats how. Maybe

[@raynahmed6155]

1 - (1\4)

[@JustTriangle]

37

[@mathy-mathy-maths]

watch this in 16x speed and see if you understand :D

[@asherdp]

16:31 e --- idnetity element

[@alejandropulidorodriguez9723]

splendid

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

[@TwitterIsReal]

1 - (1/4)^5=0.999

[@MrAdamdgross45]

You had me until the Seive of Atkins. 🙁

[@marouane2839]

I want my own 3000+ digit prime,not some stupid 'Mersenne prime' ---- that is already known

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

[@programmieraufgaben8391]

cool!

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

[@practicemodebutton7559]

16:35 you spelled identity 'idnetity'

[@RoundShades]

!! Huge Prime !!

[@carteraplus3020]

Read this as how to find VERY BIG phone numbers

[@JustBlack4]

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.

[@yeetasfahitas]

17:03 idnetity 😭😭

[@explo-sn]

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

[@mathy-mathy-maths]

idnetity element? nah! 16:34

[@lumachin2557]

Pucci founded all

[@TheBigHeadLegion]

the biggest prime number is a mersenne prime

[@movax20h]

Biggest know prime number.

[@JohnBerry-q1h]

yoo rook MAH-VELOUS

[@kcchan3263]

0:49