Fool-Proof Test for Primes - Numberphile

The AKS Test has been a major break-through in the search for Prime Numbers.
More links & stuff in full description below ↓↓↓

NUMBERPHILE

Videos by Brady Haran

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

[redrob]

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

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

[suyashsrivastava]

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.

[Violetcas]

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

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

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

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

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

[remypalisse]

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

[GKOALA]

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 YouTube 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!)

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

[jbramson]

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

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

[sth]

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.

[PikalaxALT]

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

[gauravarya]

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

[johnchessant]

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.

[Waggles]

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.