Fool-Proof Test for Primes - Numberphile

[@redrob6026]

'If you have a p.' *writes x* You've lost me.

[@adriannanad4675]

x marks the spot

[@JasonKaler]

and then you still watch more to see if it becomes any easier... alas no.

[@resphantom]

@@JasonKaler I don't even see how this is faster. From a programming perspective this, this would be insanely slow with big numbers.

[@ThisWorldMakesMeSad]

Bro same

[@numberphile]

This video will be properly listed in the next day or two, but I have it viewable for people who watched the "Fermat's Little Theorem Video" and can't wait! :)

[@coopergates9680]

+Numberphile It's faster to just find the Pth entry in Pascal's triangle and remove the 1s on each end, no? That's what the coefficients are.

[@paulscoombes]

I have only just watched this video and I came to exactly the same conclusion.

[@coopergates9680]

paulscoombes There are on the order of P/2 coefficients to check though (half due to symmetry), so I won't be replacing the trial division algorithm in my own prime generator with some other test very soon.

[@LemoUtan]

Since the second term is px^(p-1) and the second to last is px, you can disregard them too. Etc.

[@coolfreaks68]

Numberphile why not simply construct the pascal's triangle and determine primes ?? we can construct only the left half of pascal's triangle to determine primes.

[@GeneralPotatoSalad]

I can appreciate the need to make the calculation faster, but I was kind of hoping they'd just made a *really* huge Pascal's Triangle to figure things out with.

[@mirmarq429]

Binomial Theorem. Instant Pascal.

[@marios1861]

@@mirmarq429 not really?

[@stanleydodds9]

This would take exponential space and exponential time for an n-bit candidate prime, far slower than the O(n^6) AKS test, let alone the GRH dependent (probably correct) O(n^4) Miller test, and the many much faster probabilistic O(n^2) tests, or special-form tests such as Lucas-Lehmer which is also O(n^2) (where O means soft-O notation)

[@Chainless_Slave7]

@@marios1861 yes really. do some maths bro.

[@marios1861]

@@Chainless_Slave7 the recursion needed to construct a pascal triange is encapsulated through the factorial operator of the binomial theorem, thus it is not "instant". Learn some math _bro_

[@Violetcas97]

Do mathematicians just have brown paper and sharpies on their person at all times?

[@katie98711]

don't you?

[@baggetspagget5632]

When a reply gets more likes than the comment.

[@DeathBringer769]

+Bread Breadmen Come back to this thread. Your comment is no longer true, lol.

[@rhandhom1]

Right now it's 121 to the comment, 118 to the reply.

[@acetate909]

Shane's Book Corner Substitute Professor for mathematitian and chalk board for brown paper and chalk for sharpie.

[@suyashsrivastava9582]

This primality test is known as AKS primality test because it was developed by three indian mathematicians Manindra Agarwal, Neeraj Kayal, Nitin Saxena. They are currently working as professor at Indian Institute of Technology Kanpur Computer Science Department.

[@swedishpsychopath8795]

But they all got their training from a Swedish professor over skype - if what I've heard rumors about is correct. If so this should be attributed as a Swedish discovery.

[@scc470]

@@swedishpsychopath8795 lol

[@kaye_07]

@@swedishpsychopath8795 Username checks out.. 😅:)

[@noahdirksen3623]

@@swedishpsychopath8795 cope

[@JavedAlam24]

@@swedishpsychopath8795 That's not how it works.. it doesn't matter who they were trained by dude.

[@nathanisbored]

in other words, if the (p+1)th row of pascals triangle only contains multiples of p (excluding the 1s on either end), then p is prime?

[@TheRMeerkerk]

I was thinking the same thing

[@ffggddss]

So you're counting from the peak, C(0,0) = 1? So that the (p+1)st row is C(p,k), for k = 0...p. Then, I think yes, because you can generate that row by: C(p,0) = 1 ; then for k = 1...p-1: C(p, k) = [(p-k+1)/k] C(p, k-1) So that, as you proceed along that row, you're successively removing (by that division by k) each integer factor from 1 through p-1, while only appending (by the multiplication by p-k+1) factors smaller than p. Sometimes you will remove prime factors that you've earlier (or simultaneously!) multiplied into the number, but if p is prime, it will never be removed, because it's always larger than the {1...p-1} that are being divided out. Harder, but I believe, possible, to show, is that if p is composite, then at some point, some part of its prime factorization will get reduced enough that p won't divide C.

[@coolfreaks68]

nathanisbored yes but determining half the terms in a horizontal row of Pascal's triangle is O(n) time complexity operation - which is dependent on , n more rows which come before it. so overall this method will perform slower once you are hunting for large primes as it takes O(n*n) time. Sieve of Eratosthenes takes O(n log n) time , so its faster.

[@sti15v]

+Subhadeep, As I mentioned on another post, while this method using binomials is terribly slow, it isn't AKS. Both it and the SoE are exponential in the size of the input, while AKS is polynomial. The complexity is O(log^6 n). AKS is much, much faster than the SoE for large numbers. The SoE isn't properly a primality test for a single input, as it is just trial division when run on a single number. For generating small primes, the segmented SoE is the right tool. It's still used for ranges of large number though there just to remove small factors, then a primality test on the remaining candidates.

[@nathanisbored]

I understand that, I was just making a connection because I noticed the dualism at a glance. I think the pascal's triangle is a more intuitive way to explain what the formula means, even if it's not a more efficient way to calculate it.

[@thecassman]

That is very cool. Amazing that polynomials are one of the first bits of algebraic maths that you do in school and it ends up being the solution to finding primes - not something outrageously complicated!

[@milosnikic4803]

Yeah it's always amusing when something so simple can solve something like this

[@KulakOfGulag]

Its not 100% test for primes ,the sum of the binomial coefficients make this (2^n -2)/2=2^(n-1)≡1 mod n. this is just a base-2 fermat's prime test lol

[@JavedAlam24]

@@KulakOfGulag You're wrong, it is 100%. Go do some reading.

[@Artisyy]

It happens so, a few days ago I discovered the relation between binomials and Pascal's triangle. When writing out the triangle I noticed that if a row number was a prime, I could divide the numbers in the triangle (corresponding to that row number), except for the first and last number (that's why they subtract (x^p-1) from (x-1)^p) by that row number, thus a prime. It's so logical! The easiest way to calculate a binomial is using that triangle to identify the coefficients.

[@ElFabriRocks]

So... all this time trying to find complex tests to prove primality and the answer was always in Pascal's triangle? Oh god...

[@ScottLahteine]

I'd love to know more about the Theory behind this method, and how it relates to the Fermat test. In other words, how come it works, and what it says about primeness. I've always liked the name of the Sieve of Eratosthenes, because that's essentially what prime numbers are: unfilled holes in the whole number line. Think of a number line stretching to infinity. It starts out unmarked. So you mark off 1 to get started. Then you begin with the multiples. Mark off all the multiples of 2 up to infinity. The next unmarked integer will be prime, in this case, 3. Mark off very multiple of 3 up to infinity. Again, the next hole in the line, 5, is prime. Mark off every multiple of 5. Rinse and repeat ad infinitum. Now, of course you can't actually do this mechanical thing (but possibly a quantum computer could do). So instead, by Eratosthenes' method, you attempt to divide each number by all the primes that precede it, and if it is indivisible by all the primes, it is prime. Now along comes Fermat and this new test, which both still require divisibility to be tested, but they significantly enhance the process, but do they point to a possible algorithm that could generate primes? For example, input the highest known prime, out comes the next prime... Sadly, no. I would be interested to discover whether it has been established that no such algorithm is possible, and if not, why not.

[@remypalisse4102]

This test is equivalent at looking if the coefficients of the line number p (excluding the first and the last ones) of Pascal's triangle are divisible by p. I like your channel, you are great teachers and can be understood by anyone :-)

[@GKOALA7]

Brady, I want to thank you very much from the heart for creating and constantly updating this channel. Throughout my entire life, except for geometry, I have been simply awful at math. I've been watching this channel now for over a year now, and you have helped my brain finally start grasping some number theorems. James has also been such a great help as well. His enthusiasm and child-like adoration of numbers has made (re)learning math more accessible. God has gifted me with the ability to excel in science, English, and art, but math always escaped me. Ironically, I love watching people who excel at it work it out. (That might explain why Numb3rs is one of my all-time favorite tv dramas.) And now, Numberphile is in my top 5 favorite KZbin channels. (Blushing) Admittedly, I find Dr. James Grime to be absolutely attractive and handsome in addition to being a very sharp dressed man! James, if you ever come visit Los Angeles, please let us know. I'd love to come see you and Simon's Enigma Machine. (I loved U-571!)

[@Daviljoe193]

Primes for Grimes! :D

[@hallfiry]

I'm still impressed that our math teacher managed to adequately prepared us for our finals back in 2010 and still found time to teach us an entire lesson about this particular result.

[@jbramson1]

So can you just use Pascal's Triangle to find all the primes?

[@skylardeslypere9909]

Basically yes, since this triangle gives you the coefficient of a binomial expansion. You do have to ignore the 1's at the ends

[@dhoyt902]

@@muzammilshafique7629 .. actually yes you can. if n choose k mod n == 0 for 0

[@andersontorres6557]

Yep!

[@youtubekings3853]

Yes

[@JM-us3fr]

Kind of. Pascal’s triangle is why the algorithm works, but you don’t really use the triangle. Instead, you exploit the fact that modular exponentiation is much faster than traditional exponentiation, not only with numbers but also with polynomials.

[@jeffreywickens3379]

I understand about 10% of what Dr. Grimes, says, but I watch him because he's such a pleasant person.

[@johnchessant3012]

It was very cool to think through why this is true! The x^k coefficient of (x-1)^n is nCk = n! / (k! (n - k)!). So if n is prime, there's no way to get factors in the denominator to cancel the n in the numerator, so nCk is divisible by n.

[@surfer855]

This is a test in order to check if a number is prime. So the opposite must be true.

[@PikalaxALT]

Equivalent to the first test: if p divides nCr(p,n) for each n=1,2,...,p-1, then p is prime.

[@sth128]

Good thing we have computers now. I'd jump off a bridge if I was the guy responsible to figure out if the 1024 bit numbers are prime or not by expanding via the AKS test.

[@ayaan8897]

My teacher showed me this in class and suddenly it’s on my recommended

[@mohammadumair3108]

Cool!

[@arsenelupin123]

This is such a beautiful result. I'm moved.

[@MinuteMaths]

I love all of your videos on Primes

[@TheAllBlackMan]

I think Fermat's Little Theorem should be used to as an initial check, then run through the latest one to be sure. This allows Fermat's test to act like a filter allowing he slower test to pick out the Carmichael numbers leaving only the primes.

[@trissylegs]

In practice you use the Miller-Rabin test. If you run it 20 times your chance of being wrong is: 1/4^20 ~ 9.095 x 10^-13. If you want to be sure, then run AKS.

[@Melomathics]

That's what's already being done.

[@DimitrisLost]

was thinking the same thing. that could save us some time!

[@Salabar_]

You are patrially right. AKS is too slow for real life application. But your idea is in use. Usually, Fermat's test is followed by Solovay-Strassen algorithm. That one is not accuarate as well, but it never fails on the same number with Fermat's (or Miller-Rabin, to be exact)

[@pvnrt2803]

This method is found by two students and one professor of IIT Kanpur.

[@thesnowedone]

Cool - I'll have to check out the AKS test a bit more later.

[@chickenspaceprogram]

who disliked this??? why!! seriously this deserves 0 dislikes

[@recursiv]

It's not actually the AKS primality test. That's probably why.

[@PunmasterSTP]

It's crazy to think that even now people are innovating in the field of prime numbers and primality testing!

[@rationalsceptic7634]

Prove the sum of 4 prime numbers are divisible by 60 if 5 < p < q < r < s < p + 10

[@simka123]

Can somebody correct me, if I am wrong, but doesn't this follow from Pascal triangle being made out of combinatorial numbers (n,k) and if n is prime that by calculating it k never divides n from n!(unless k=0 or k=n)

[@predraggrujic2239]

Pretty much

[@Eric.Morrison]

Can I aks you if this is prime?

[@MatthewAHaas]

Wait a minute, it doesn't work for 7,423,811!

[@ChadZeluff]

1373 × 5407 is the prime factorization, and therefore, the number you listed is not prime. Apologies if you've received this response already :)

[@KnakuanaRka]

حسين فرّاج Those aren’t primes, either; 341 and 561 are divisible by 11 (easily determined in both cases because the middle digit is the sum of the .other two), and 1105 is obviously a multiple of 5 Also, sorry about the messed-up formatting; KZbin’s app can’t seem to handle the Arabic text in your screen name properly.

[@mikelindenstrauss.1955]

@@HocineFerradj all the numbers you mentioned in your comment are composite my dear. Instead of finding mistakes in the algorithm of a renowned Indian mathematician you need to first make sure that you are yourself correct in your logic.

[@gauravarya8952]

The AKS primality test (also known as Agrawal-Kayal-Saxena primality test and cyclotomic AKS test): work of Indian mathematicians from IIT Kanpur.

[@mscha]

Note that this is *not* the AKS test, but a not very efficient test that has been know for centuries. (Basically, if choose(p, 1) through choose(p, p-1) are all divisible by p, p is a prime number.) The AKS test builds upon that, see: en.wikipedia.org/wiki/AKS_primality_test

[@acetate909]

Dr. Grimes- "I have a fool proof test for primes." Me- "Fool proof you say? Hold my beer."

[@TruthNerds]

Never underestimate the power of a determined fool…

[@mikecmtong]

Oh I get it. So in the binomial coefficient, if it's prime then it won't be cancelled out by any of the denominator of the coefficient. You subtract the last binomial because obviously the first and last coefficient will be 1.

[@ZardoDhieldor]

It all makes sense! :) I just wonder why it works if and _only if_ the number is prime!

[@mikecmtong]

Yea, I was thinking that, too! I figured something for n even: If n is composite and even, then n choose 2 is not divisible by n.

[@ZardoDhieldor]

mikecmtong For n even you also get (when subtracting (x^p-1)) a +2 at the very end which also is divisible by n if and only if n is a prime! :)

[@ImAllInNow]

Zardo Schneckmag mikecmtong It ONLY works for primes because if you take the first and last coefficients away from (x-y)^p you get sum(n=1..p-1){pCn*x^(p-n)*(-y)^n} so the binomial coefficient parts (p choose n or pCn) go from 1 to p-1. So if for all of those ones, p is NEVER canceled out by something in the denominator, then it means that p is not divisible by any number less than p other than 1 so it's prime.

[@ZardoDhieldor]

ImAllInNow I just don't get why. Why can't it be that you additionally multiply by a component of n, so it doesn't cancel out? After all there are more factors in the numerators.

[@krakraichbinda]

I've never thought that the mathematics would be so fascinating. Best greetings from Poland.

[@xexpaguette]

My Fool-Proof Test to find Primes. 1. Divide your Number by Every Number Below It (Except 1) If you get a whole number as a result in one or more of the divisions, the number is composite (Not Prime)

[@gauravarya8952]

Also known as Agrawal-Kayal-Saxena primality test and cyclotomic AKS test. A deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002.

[@amits4744]

Prime numbered rows in Pascal's triangle only consist of 1 and the numbers divisible by the prime. Like 5 would have 1,5,10,10,5,1. 7 will have 1,7,21,35,35,21,7,1 and so on And we know that nth row of Pascal's triangle sums up to 2^n. So for every n where (2^n - 2)/n equals a positive integer, n is prime

[@alexmcgaw]

Great couple of videos here :) this second result is incredible, as I'm reading it as "Iff p is a prime, then all the numbers (excluding 1) on the pth row of Pascal's triangle are divisible by p" and I have no idea why that ought to be the case! Would like to read the paper.

[@neelmodi5791]

So basically, you can look at pascal's triangle right? If a number is prime, then all the numbers in its row in pascal's triangle are divisible by it. For example,if we look at the number 5, in the row in Pascal's triangle is 1, 5, 10, 10, 5, 1. Excluding the 1's, every single number in that row is divisible by 5.

[@valiant8987]

Here's another way you can test if P is prime Cosine pi times a fraction where the numerator is (P - 1)! +1 and the denominator is just P . All of that gets squared at the end. If prime=1 If composite=0

[@bitansarkar6463]

What they did was quite simple, so it can be further broken down. If 2^(p-1) - (1 + p) is divisible by p, then p is a prime, where p is natural numbers, EXCLUDING {1,2,3}

[@koenth2359]

Always enjoying James's zeal! Here a new law: Shirt+marker-lid+enthusiasm=be careful.

[@Waggles1123]

I know 1 isn't a prime, but doesn't this test technically work for 1? You end up with 0, but 0 is divisible by 1.

[@helloitsme7553]

well 1 shares some properties of primes, and doesnt have some other properties of primes, so its not fully prime, so that's why we say it's prime. this is an example of a shared property

[@happmacdonald]

Basically, the right way to talk about this is not *really* "a 100% primality test", but instead a "100% *compositeness* test". Ultimately, 1 is not composite, and the union of the list of prime and composite numbers are exhaustive for all larger natural numbers. :3

[@aidandanielski]

Division by zero is illegal.

[@DanSmithJeffery]

@Aidan DePeri OP stated "0 is divisible by 1", not the other way around

[@aidandanielski]

0/1=0; 1/0=UNDEF

[@BigChief014]

Gotta love a little bit of certainty when looking for new primes. :)

[@karifeaster5]

the answer should be around a list of 115600 moves because the square root of 1161=34.07 and the square root of 12=3.46 fairly close right movement of the decimal on incredibly similar numbers so if the decimal was moved once more hypothetically then it should approx. 115600 for four steps either way to be certain death.

[@Johnny20022002]

Can you explain why this works

[@00bean00]

Try this, i can't see the other replies: en.wikipedia.org/wiki/AKS_primality_test#Concepts

[@ryandsouza9093]

Simple Proof: Use Binomial Theorem Excluding the first and last term, every coefficient is of the form pCr are integers. Since p is prime no denominator of pCr will eliminate it (since they are products of smaller numbers). So all terms are 100% divisible.

[@mphayes98]

so basically what this is saying is that a number "p" is prime if every combination from "pC1" to "pC(p-1)" is divisible by "p". that's what I gathered at least, and it seems easier to think of it like that than they way they explained haha

[@puma3912]

This test should have been obvious since prime-number rows on Pascal's Triangle are ones whose elements are all divisible by their row number, and (x - 1)^p - (x^p - 1) is the same thing as just looking at the coefficients that are not 1 in the p'th row of the pascal's triangle

[@hellox8990]

I guess the trick was proving it.

[@kiharapata]

Vi Su how will it not hold for 341 if Pascal's triangle and the coeficents of those polynomials are always the same thing??

[@wsadhu]

Are composite numbers that pass certain prime number tests in any way speial or all in all interesting?

[@alandouglas2789]

wsadhu composite numbers are just any number that has factors (so not prime). An example of a highly composite number would be 12 compared to 10

[@bearcubdaycare]

@@alandouglas2789 I think that wsadhu is referring to tests for primes that, unlike this test, can have false positives, and is asking whether numbers that pass those tests but are not in fact primes are in any way interesting. (A fairly broad question, admittedly, as a specific rest isn't mentioned.)

[@wsadhu]

@@alandouglas2789 I know what composite numbers are. The question is, if there is anythong special in a composite number that passes a certain prime number test and what can it tell about the test.

[@movax20h]

I think aks-test is one of the biggest discoveries of 2000-2010. Not only it is definitive, it is polynomial. (There is not point of a test that is exponential, because you could simple do factorization).

[@benjohnson6251]

Doesn't this generate as many terms (give or take) as there are numbers between 1 and p? If so doesn't it make sense to just do divisibility tests on all numbers from 2 to square root p?

[@primerepresentingconstant]

Thank you for this very much for this video. The video shows that pi is approximately 22 / 7. This value is approximately 3.14. Using the properties of this value we can compute prime numbers in sequence, which is based on the existing computing capability. The formula was an algorithm, that was developed by a well known mathematician. Using his formula and the method that I discovered, I can compute prime numbers in sequence using 22 / 7 .

[@xXNICKROXXx]

You guys should do a video explaining the intuition behind the Fundamental theorem of calculus. Its pretty complex as to why the difference of the antiderivatives is equal to area under the curve.

[@laudprim5680]

By taxing in the test x=2, one has: for any prime p there exists a hole number h such (2^p - 2)/p=h which looks like a direct formulae of primes.

[@richardhannemann9258]

I got the same, trank you, because my way was very complicated and now I could maybe remember it.

[@nayutaito9421]

Do you mean, "As for all n, pCn is divisible by p iff p is prime?"

[@IshanBanerjee]

yes, the prime just stays in the numerator

[@shruggzdastr8-facedclown]

If you take the length of this video, ignore the colon between the minutes and seconds digits and read it as one single three-digit number, "343", you get the cube of "7".

[@niltondasilva1645]

Aprendi o método: 👏👏👏👏👏👏👏

[@alexvosten4797]

WAIT A SECOND! The expansion of (x-1) ^y follows row y of Pascal's triangle. Which means that ever member of all prime rows of Pascal's triangle are divisible by the prime of the row. AND you can calculate the members in each row of Pascal's triangle with permutations and combinations. And this can be used for any number! So the rows numbers can be MASSIVE, but it is still quick. Pascal you beautiful man! Although, it makes you think why only primes behave in this way. Why the simple addition of numbers can produce primes and ONLY multiples of primes. The elegance of the prediction of primes leads me to believe that the subsequent formula would be beautifully simplistic.. Pascal's triangle is beautifully simplistic, and with so many patterns already.... Maybe the simple compound addition of 1's in the shape of a triangle holds the key to the prediction of primes. Or maybe, I'm a little insane.

[@bruinflight]

Thanks Brady! Great videos!

[@CallMeTaste]

Geez. This is amazing.

[@venkatbabu186]

How to make pattern. Take all the numbers from one to huge numbers and arrange them in patterns of prime and see the pattern to recognize the prime. Similarly follow the same for other primes. Say for example. 123456789101112. Say 3 prime. 120120120120120. Arrange vertical in groups of prime or up to ten in each column. Zero gives you the pattern to look for. For higher prime overlay the next prime pattern.

[@benjaminwalters6703]

If you used Pascal's triangle here instead of generating a polynomial every time it may be faster. If all values in row (n+1) of the triangle besides the 1s at the ends are divisible by n, n is prime

[@FR4NKESTI3N]

Finding the k-th pascal's row is still of O(k) time complexity so the modulo test would still give faster results at O(sqrt(n)) complexity. Where is AKS test applied?

[@achyutpatel95]

Thats what I was thinking the whole time. This seems cool at first but it is really slow algorithm unless they do have some other means to make it faster.

[@davidhuynh9996]

So you take Pascal's triangle, and for row n, you remove the first and last entry and check if the remaining elements divide the n? That's wicked! How did they go about determining that?!? How do you think so abstractly and see that? Truly incredible and wonderfully elegant.

[@kephalopod3054]

In Pascal's triangle, the GCD of all internal (neither first, neither last) terms of row n, n >= 2: * equals n iff n is prime; * equals prime p iff n = p^k, k >= 1; * equals 1 iff n is not the power of a prime.

[@Luca_5425]

That's actually really cool

[@yogendraprasad4087]

The most underrated video on KZbin

[@arunb8841]

Excellent video, as always. On a different note, with no disrespects to others, am happy and proud that AKS test was discovered/devised by three brilliant Indian minds from IIT-Kanpur. So happy for them!!

[@OrchestratedChicanery]

You're bluffing, aren't you?

[@arunb8841]

@@OrchestratedChicanery Check the Wikipedia page of AKS test..

[@Virtue740097]

Great illustration

[@zanti4132]

To everyone raving about this test, I have to ask them about its practicality. You do realize that to test a number (let's call it n), you need to check all the coefficients in the nth row of Pascal's triangle. Okay, I suppose we can take advantage of the symmetry in the triangle and not bother to test half the coefficients, but that means if the number being testing is, say, around 10^50, then about 10^50/2 computations have to be executed. That does not sound like a fast calculation to me. It's more like one of those "end of the universe" calculations that our eminent professor insists is not the case with this test.

[@mirmarq429]

So basically, if the row of the number in Pascal's Triangle is completely divisible by the number, it's prime. Genious.

[@XxAdnan1995xX]

Yet another great video! By the way, I saw matt on the discovery channel today, he was explaining all sorts of science behind some really viral videos's :p Really cool!

[@vishalcseiitghy]

I got a chance to be interviewed by the person who found this algorithm for a Phd position under him. The best day of my life.

[@ThePharphis]

Wow, very cool. It helps to look at Pascal's Triangle to see it

[@alastairbateman6365]

To add to the historical accuracy of my comments of 6 years ago the simple algebra of the AKS test was derived and proved by no other than that well known mathematician Leonhard Euler. It is theorem 1 in his 'Theorems on the Divisors of Numbers' which is published as E134 in the Enestrom Index of the Euler Archives. Give credit where credit is due!

[@jonasrla]

Now do the Computerphile interview asking about the importance of this discover to the computer science community! Also, would be nice to see this theorem turned into a algorithm.

[@SolPhoebusApollo]

I definitely prefer the AKS test, greater accuracy with less double checking sounds like a winner to me. I don't see how AKS is slower since you have to double check so many numbers for the Fermat's test to catch all the sneaky, composites, liars and witnesses.

[@calebmitchell-ward1585]

heres a good way to find primes. plug 0 into f*(x)=x^2+1 and you'll get tons of prime divisors. the numbers in this sequence can get pretty big so they should use supercomputers for this

[@Untoldanimations]

Wait, if you wanted to test if 100 was prime, would you need to do that thing 100 times or something? If so, why don't you just do 100 divided be the first half of all the numbers before it? That would be quicker IMO.

[@paulinho543]

This guy is completely funny. His face, accent and smile are unique. He looks like the guy from Mad Magazine.

[@merchpublicschool9331]

Thank you, I have discovered a whole new way to test for primes that is much faster and more accurate than any existing formula, I have also discovered a couple of formulas that predict prime numbers a lot more often than any existing one. Plus one formula that predicts twin primes and brings us closer to solving the twin prime conjecture. I can even go as far as saying that I have solved it and I am 100 percent certain that there is an infinite number of twin primes, I don't have the equipment to test it any further but did manage to test it to 114 digits. I have contacted several entities to get help on how to publish my work but none have answered my emails, not even you sir in the video. I guess the world might just have to wait another 2000 years like they did before. I am very upset because I turn 40 in a few days, and you know what you get when you publish great work after the age of 40? A pad on the shoulder...

[@benjaminbrady2385]

Sounds close to Gauss's Lemma in relation to ring theory and polynomials

[@ThalesII]

What makes it so slow? Couldn't they just use pascal's triangle to determine the coefficients?

[@IsYitzach]

Calculating the whole of pascal's triangle is O(n^2) for the nth level that you complete and you would end up throwing out most of that work. I think that a single line is order O(n). I think you're looking for other information I don't have with the first question.

[@meetudeshi3520]

try generating the pascal's triangle till larger number of rows, like 10^6 or 10^7 rows, then you'll realize how slow and memory-abusing the process becomes. If it were me, I would never have gone with using pascal's triangle but instead would have used the (n choose r) formula.

[@MishMash95]

On a computer, (which I assume they are using for larger calculations), Powers in them selves take a while to calculate. Pascal's triangle is also not the fastest thing you can compute, due to its recursive nature. To me, it still seems like it would be faster to do the good-ol' test if a number is divisible by every number up to that number.

[@joopie99aa]

But how much time do you think it would take to calculate pascal's triangle up to the 2^(57,885,161) − 1th row (the largest known prime number). Pretty long, I dare venture :) And it's certainly slower than just calculating the coefficients outright using factorials.

[@ThalesII]

Meet Udeshi It would indeed be much faster to use that formula, but still that is simply a more effective way to find the numbers in any given row in pascal's triangle. I can't fathom how the polynomial method can be much slower than the other one, not to mention that it's much more reliable.

[@EnderCrypt]

WHAT a 100% accurate prime test method?! magic

[@alex75493]

Integer factorization works too

[@XenogeneGray]

Clearly no composites pass this test, but are there any primes that fail it?

[@Kubboz]

nah, there is not one. It's very easy to prove when you realise you can compute the binomial coefficients recursively. I'm actually sort of embarrassed how I did not notice it before I've heard about it.

[@MasterMindmars]

Very good explained

[@ianw8479]

Well explained*

[@barack.obama.official]

Why the fuck was this video not shown before? This is outrageously significant.

[@goldenera7090]

this is very interesting test. one can now use Pascal's triangle to test prime numbers. Pascal's triangle gives coefficients of the polynomial as shown in the video. so all you have to do is to find numbers in Pascals triangle , which will be coefficients and if they are all divisible by p, then p is prime. is that right?

[@pivotman64]

Would the graph of (x-1)^y-(x^y-1)=yz provide any useful data? Or would it just be too complicated?

[@htmlguy88]

***** you'd either have to assign a value for x or graph it algebraically.

[@namnatulco]

Thanks! I just tweeted asking about this the other day :-)

[@Phoenixspin]

I will sleep easier tonight knowing that there is a fool-proof test for primes. I no longer feel like a fool.

[@codediporpal]

Wow, blown away that somebody came up with proof of this.

[@DavidHT]

Mind suitably blown. Love it!

[@JustinTimeCuber]

2:35 "p lots of..." sounds very, very British

[@kanabalize]

More Dr James Grime please

[@abdul-muqeet]

Before watching this vid, I suspiciously found that for a prime p, all numbers on the pth row of Pascal's triangle except the two 1's were divisible by p.That completely relates to this.

[@SamSpendla]

So basically if all the numbers (that are not 1) in the nth line of Pascals Triangle are divisible by n, n is prime. correct?

[@mayankacharya2712]

Sam596::Not nth line, It should be (n+1)th line, because a line having only 1 is 0th line!!!.