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

[@AmitYellin]

​@@resphantom You're partially right. It's complexity is O(log⁶n) which is way better than the alternative of checking primes up to square root of n which is about O(n^0.5). But there is for example the Miller-Rabin test, that has a complexity of O(k*log³n). (k is the number of rounds youre testing). Technically, the Miller-Rabin test is not 100% accurate, but the probability of a composite number to pass this test as a prime is at worst case: 0.25^k, so when k is, say, 150, the probability of it being wrong is about one over googol.

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

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

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

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

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

[@ElFabriRocks]

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

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

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

[@jeffreywickens3379]

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

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

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

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

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

[@PunmasterSTP]

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

[@Daviljoe193]

Primes for Grimes! :D

[@ayaan8897]

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

[@mohammadumair3108]

Cool!

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

[@arsenelupin123]

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

[@PikalaxALT]

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

[@thesnowedone]

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

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

[@chickenspaceprogram]

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

[@recursiv]

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

[@Eric.Morrison]

Can I aks you if this is prime?

[@pvnrt2803]

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

[@MinuteMaths]

I love all of your videos on Primes

[@gauravarya8952]

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

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

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

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

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

[@krakraichbinda]

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

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

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

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

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

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

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

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

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

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

[@rationalsceptic7634]

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

[@koenth2359]

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

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

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

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

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

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

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

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

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

[@BigChief014]

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

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

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

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

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

[@benjaminbrady2385]

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

[@MichaelMoore99]

So, is the idea to run numbers through Fermat's test, then all that pass, run them through the new test, so you don't have to run as many numbers through the slow process?

[@sti15v]

+JMan Nitpicking, but there were already two NON-probabilistic algorithms that were much faster, and we still use them in practice. AKS is polynomial, but the constants and exponents are quite large. So we knew we could quickly and correctly test primality, but the question was if it was in P. It was long suspected the problem was in P, but nobody had an actual method until AKS.

[@sti15v]

APR-CL is general, unconditional, deterministic, and sub-exponential. The exponent does not exceed AKS for any physically computable number. That is what I mean. We also had ECPP, which is general, unconditional, randomized, and polynomial. In practice it does indeed run in the expected time, which is faster than AKS. I'm trying to make a distinction, because so many people confuse them, between asymptotically fast (e.g. polynomial) and fast in actual practice (which AKS fails miserably at). Lots of people also seem to think the only solutions for general inputs are probabilistic tests (e.g. randomized Miller-Rabin, but there are lots more), and AKS. There are perfectly usable deterministic tests, which we still use. We do not actually use AKS because it is very slow.

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

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

[@paulinho543]

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

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

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

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

[@mirmarq429]

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

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

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

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

[@liamtoebes]

Seeing as the coefficients of binomial expansion line up with Pascal's triangle always, the does this mean that if all the numbers on the nth level of Pascal's triangle (but the ones) are divisible by n then n is prime.

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

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

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

[@JustinTimeCuber]

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

[@subgatempp]

Could you guys make a video on the Collatz problem? Thanks for your awesome videos.

[@tallevi2000]

what do you think will happen to the RSA encryption if some day mathematicians will find a (relative) fast way to factorize huge numbers (specially huge numbers who's only factors are 2 huge primes)?

[@Phoenixspin]

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

[@penfold-55]

riemann's hypothesis is known for having direct implications for predicting that prime numbers however this just gives us prime numbers that complete the test... i know there are lots of useful things that the riemann hypothesis shows and can be used in but surely mathematicians as a community are interesting in being able to pin point and predict primes. how has this not eclipsed the status of riemann's hypothesis. Also, is there proof that this consistently will produce prime numbers? Is there proof that it must work 100% or has it just not been found?

[@jeskomatthes1192]

As far as the relationship of AKS and Pascal's triangle goes, and in fact the concept behind them is identical, there is a proof that all coeffients in a triangle row are divisible by the row number if and only if that number is prime. This implies that the pattern of the primes is fully deterministic, all considerations in the complex plane left aside. The point is, AKS and Pascal's triangle testing still are trial division and therefore not a "formula for primes". They are just as tantalizingly close as you can get to the idea at the moment. The proof of the Riemann Hypothesis, as far as a complete layman like me can possibly understand, could perhaps be to establish a deterministic connection between the zeroes of the zeta function and the polynomials in Pascal's triangle. - Just an educated guess, of course.

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

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

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

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

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

[@Cougar1823]

Why involve the powers at all? All one needs is the binomial coefficients. Also, since I don't have the time to read all of the comments to determine if this is old news, I apologize in advance, but has anyone else noticed that when the number isn't prime, the remainders of the coefficients which aren't evenly divisible by that number share a common factor with that number? In other words, if the number is not prime, the coefficients which caused it to fail the prime test hands its factors over on a silver platter.

[@macwilliambasilio4128]

What about Peter Plichta's method, where you check a number as being prime or not, considering multiples of (6 +/- 1)?

[@mr_nexys4735]

i found a prime tester, n is the number you are testing, it dose not work for numbers divisible by 3 it is 2n - (first digit of n + second digit of n) and if the first digit of the output is a Fibonacci then n is prime. e.g 127*2 = 254 - 1+2 = 251 and i is a Fibonacci number, so 127 is prime

[@ThePeaceableKingdom]

Not for the first time watching Numberphile, my mind is blown. But it leaves me wondering why it's 100% certain? Perhaps that's a much more advanced, more difficult thing to explain than the result, which is certainly interesting enough on its own. Or perhaps that's coming soon. Or perhaps I've missed something obvious. (Wouldn't be the first time for that, either...)

[@kox444]

What about this? Take 2 for x and you have (2-1)^p-(2^p-1)=1-(2^p-1)=2-2^p multiply it by -1 to make it simpler and we have 2^p-2 but it only works up to 53. I knew it wouldn't work, but I wonder why it works for every prime

[@barack.obama.official]

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

[@bruinflight]

Thanks Brady! Great videos!

[@CallMeTaste]

Geez. This is amazing.

[@npip99]

I don't understand how this is breakthrough. I've always noticed that Pascal's triangle is only divisible by the row it's in when it's prime (1 7 21 35 35 21 7 1). Was that never proven before or was it the shortcut that's new?

[@coopergates9680]

+Nicholas Pipitone Exactly, just remove the 1s from the Pth row of the triangle. The only problem is that if you're testing a number such as 80207, you have to check if 80206 coefficients are divisible by 80207. Sounds like trial division up to the square root of the number is still faster.

[@npip99]

@@coopergates9680 Seems like AKS works by proving you only have to check a few values of "a" for the whole polynomial to be correct. Still seems like a complicated proof!

[@matthewwelch1537]

Can you make a video on the proof!? This can be conjectured from pascal's triangle

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

[@haikchaang2302]

There is a video in Numberphile stating that 1 is not a prime. But,(x-1)^1-(x^1-1)=0... Zero is divisible by 1. Does this mean 1 is prime??? Or that it is not fool proof???

[@relaurent1]

+HAIK CHAANG The test is defined for n > 1.

[@haikchaang2302]

k sorry

[@ThePharphis]

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