Fool-Proof Test for Primes - Numberphile
HTML-код
- Опубликовано: 30 сен 2024
- The AKS Test has been a major break-through in the search for Prime Numbers.
More links & stuff in full description below ↓↓↓
See the previous video about Fermat's Prime Test at: • Liar Numbers - Numberp...
The video features Dr James Grime - singingbanana.com
The AKS Test paper: bit.ly/primetest
Support us on Patreon: / numberphile
NUMBERPHILE
Website: www.numberphile...
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberph...
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumb...
Videos by Brady Haran
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanb...
Sign up for (occasional) emails: eepurl.com/YdjL9
Numberphile T-Shirts: teespring.com/...
Other merchandise: store.dftba.co... 
Наука
![Cody Johnson - I'm Gonna Love You (with Carrie Underwood) [Official Music Video]](http://i.ytimg.com/vi/yy9PuYMU29g/mqdefault.jpg)
'If you have a p.'
*writes x*
You've lost me.
x marks the spot
and then you still watch more to see if it becomes any easier... alas no.
@@JasonKaler I don't even see how this is faster. From a programming perspective this, this would be insanely slow with big numbers.
Do mathematicians just have brown paper and sharpies on their person at all times?
don't you?
When a reply gets more likes than the comment.
+Bread Breadmen Come back to this thread. Your comment is no longer true, lol.
Right now it's 121 to the comment, 118 to the reply.
Shane's Book Corner
Substitute Professor for mathematitian and chalk board for brown paper and chalk for sharpie.
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! :)
+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.
I have only just watched this video and I came to exactly the same conclusion.
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.
Since the second term is px^(p-1) and the second to last is px, you can disregard them too. Etc.
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.
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?
I was thinking the same thing
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.
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.
+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.
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.
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.
Binomial Theorem. Instant Pascal.
@@mitchmarq428 not really?
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)
@@marios1861 yes really. do some maths bro.
@@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_
So... all this time trying to find complex tests to prove primality and the answer was always in Pascal's triangle? Oh god...
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!
Yeah it's always amusing when something so simple can solve something like this
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
@@KulakOfGulag You're wrong, it is 100%. Go do some reading.
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.
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.
@@swedishpsychopath8795 lol
@@swedishpsychopath8795 Username checks out.. 😅:)
@@swedishpsychopath8795 cope
@@swedishpsychopath8795 That's not how it works.. it doesn't matter who they were trained by dude.
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)
Pretty much
So can you just use Pascal's Triangle to find all the primes?
Basically yes, since this triangle gives you the coefficient of a binomial expansion. You do have to ignore the 1's at the ends
@@muzammilshafique7629 .. actually yes you can. if n choose k mod n == 0 for 0
Yep!
Yes
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.
Primes for Grimes! :D
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.
Can I aks you if this is prime?
Wait a minute, it doesn't work for 7,423,811!
1373 × 5407 is the prime factorization, and therefore, the number you listed is not prime. Apologies if you've received this response already :)
حسين فرّاج 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; RUclips’s app can’t seem to handle the Arabic text in your screen name properly.
@@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.
This method is found by two students and one professor of IIT Kanpur.
My teacher showed me this in class and suddenly it’s on my recommended
Cool!
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)
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.
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
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
Division by zero is illegal.
@Aidan DePeri OP stated "0 is divisible by 1", not the other way around
0/1=0; 1/0=UNDEF
Is it me or has the people in Brady's videos started to dress better and look shaven and such over time.
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.
Dr. Grimes- "I have a fool proof test for primes."
Me- "Fool proof you say? Hold my beer."
Never underestimate the power of a determined fool…
Are composite numbers that pass certain prime number tests in any way speial or all in all interesting?
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
@@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.)
@@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.
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 :-)
Equivalent to the first test: if p divides nCr(p,n) for each n=1,2,...,p-1, then p is prime.
Do you mean, "As for all n, pCn is divisible by p iff p is prime?"
yes, the prime just stays in the numerator
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?
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.
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?
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.
What makes it so slow? Couldn't they just use pascal's triangle to determine the coefficients?
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.
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.
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.
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.
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.
2:40 x-r-1 when you mean x^r-1
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.
Can you explain why this works
Try this, i can't see the other replies:
en.wikipedia.org/wiki/AKS_primality_test#Concepts
Clearly no composites pass this test, but are there any primes that fail it?
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.
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 RUclips 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!)
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
Yeah, AKS are Indians Agarwal Kayal Saxena...
can you do an episode on primecoin, its really cool but I'm not sure how it works, all I know its like GIMPS but it pays you...
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.
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.
That's what's already being done.
was thinking the same thing. that could save us some time!
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)
So basically you check all the binomial coefficients. cool!
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?
+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.
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.
Damn. Who even discovers these things?!
The fact that p | pCr for 0 < r < p was quite well known already
Mathematicians
But how to compute integer numbers of more than 64 bits?. In a pc of course.
There is an integer method to compute Pi with thousands of digits. Even millions if have enough memory.
2:35
"p lots of..."
sounds very, very British
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?
+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.
@@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!
It's crazy to think that even now people are innovating in the field of prime numbers and primality testing!
Would the graph of (x-1)^y-(x^y-1)=yz provide any useful data? Or would it just be too complicated?
***** you'd either have to assign a value for x or graph it algebraically.
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)?
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 ferma prime test lol.
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...)
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?
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.
Is this method faster than test with the √p divisors ?
Isn't trying to divide p by his √p divisors 100% true too ?
Or did I just don't understand this video ^^
(sorry if I have a bad grammar)
this is still too long, what about something like 81: 8+1 = 9
9%2 != 0 , 81 is prime :P
So if its 100% accurate as he describes it in the video then 1 is prime after-all.
Not really, because for p=1 the term disappears entirely.
If only the prisoners knew this in that movie _Cube_, more of them would have survived.
I love that movie!
The AKS primality test (also known as Agrawal-Kayal-Saxena primality test and cyclotomic AKS test): work of Indian mathematicians from IIT Kanpur.
Sounds close to Gauss's Lemma in relation to ring theory and polynomials
26333 is a prime
but is -541,667,724,774 = 3*(...)+(26333^r-1)*(...)
Honestly, I don't get the improvement of this test. If you are testing number k to see if it is prime, then you have k-2 binomial coefficients to check. Luckily we know that they are symmetric, so you have to check (k/2)-1 coefficients. This requires you to calculate k/2 - 1 binomial coefficients, and perform a division on each of them. Whereas, a simple test of finding the divisors of k is much easier, because you do not have to calculate any uber large coefficients, and you only have to check the first sqrt(k) numbers. And yes, sqrt(k) is smaller than k/2 - 1. So, what is the point of this test?
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.
It all makes sense! :) I just wonder why it works if and _only if_ the number is prime!
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.
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! :)
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.
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.
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.
This is a test in order to check if a number is prime. So the opposite must be true.
Aprendi o método: 👏👏👏👏👏👏👏
I love all of your videos on Primes
Yeah, you lost me right on the first step, im guessing that means i should get back to school.
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?
Sam596::Not nth line, It should be (n+1)th line, because a line having only 1 is 0th line!!!.
Cool - I'll have to check out the AKS test a bit more later.
Can you make a video on the proof!? This can be conjectured from pascal's triangle
I think this says 1 is a prime
en.wikipedia.org/wiki/AKS_primality_test#Concepts
en.wikipedia.org/wiki/AKS_primality_test#The_algorithm
Its only valid for n > 1.
1 was considered a prime number, and technically is. The only reason it isn't is because prime numbers are fundamental numbers. And while 1x3x5=15 the 1 isn't required so it's easier to just exclude it from the list of prime numbers than it is to consider it one.
+scpDgJ well the old definition of a prime is that it can only be divided by one and itself. The actual quantity of divisors isn't important
Originally, i.e. for the Ancients Greeks, 1 wasn't prime because it wasn't a number. It was the unit from which numbers are created.
"Not divisible by 1 and 1, just by 1." This doesn't change anything, 1 is divisible by 1 and by itself.
What actually matters is that 1 is the null factor of multiplication, therefore you don't need to include it in any of these tests, since it's use as a prime is useless.
So they are not looking for prime numbers formula anymore?
Finally! Now i can enhace my prime number calculator hello world program.
test (2^57885161)-1.
Why are primes so important?
yea but atoms are useful....
Primes contribute to the very encryption technologies, is what he was saying. That's more useful to the average man than atoms are.
encryption
Mu'izz Siddique you're a moron
Because the world needs primes and they fascinate us all.
This is such a beautiful result. I'm moved.
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
I guess the trick was proving it.
Vi Su how will it not hold for 341 if Pascal's triangle and the coeficents of those polynomials are always the same thing??
Pascal FTW!!! 1, 11, 121, 1331, 14641, 15101051, 1615201561, 172135352171,... The mth coefficient of (x-1)^n is relatively known. I am curious how this is so unknown. It's like it's been sneaking around laughing at us.
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
I always thought it was "full-proof." I guess I'm the fool. This is like when I realized "Ekans" was "snake" backwards.
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).
(0-1)^2-(0^2-1)=-1 and -1 is not divisible by 2, 0^2-2*0^2+2*0-1=0, (-1-1)^2-(-1^2-1)=-3 and -3 is not divisible by 2, -1^2-2*-1^2+2*-1-1=0. Moral 0 and numbers less proves some math theories wrong.
The test is about coefficients of polynomials, not about values of polynomials.
@@MuffinsAPlenty This is a joke as you can tell
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???
+HAIK CHAANG The test is defined for n > 1.
k sorry
I understand about 10% of what Dr. Grimes, says, but I watch him because he's such a pleasant person.
Oh 3 is a prime, Matt Parker won't be happy hahaha
My professor authored this paper xD
Great, seems like you are from IIT Kanpur.
Makes military grade encryption available to the masses :)
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.
How do you do that with your brain?
who disliked this??? why!! seriously this deserves 0 dislikes
It's not actually the AKS primality test. That's probably why.
Wow, blown away that somebody came up with proof of this.
n=0 -> 1
n=1 -> 1 1
n=2 -> 1 2 1
n=3 -> 1 3 3 1
n=4 -> 1 4 6 4 1
n=5 -> 1 5 10 10 5 1
n=6 -> 1 6 15 20 15 6 1
...
Many of you will recognize this tree. I don't remember what it's called, but I find it hard to believe that nobody (including me) noticed that only primes were divisible from all numbers in their respective columns after taking out the end 1s until 2002. This should have been figured out a long time ago.
What purpose does the negative in (x-1)^p serve? Sure, the first and last terms cancel out since you also have -(x^p-1), but wouldn't it be simpler to write (x+1)^p-(x^p+1)? Is there a need for the alternating negatives with (x-1)^p? This video doesn't seem to imply there is.
Can someone explain me why the period length of 1/p can be written as (p-1)/n where p is prime and n natural (seems to work for every prime under a 100 and the only non primes it works with are 33, 55, 91 and 99, if you only take the numbers into account that fully consist of a period for instance 0.45123123123... wouldn't count)
+Numberphile .
Results speak louder than words so what sizes of primes and checking times does the AKS test give?
A basic analysis suggests that the method is untenable because (1) The number of coefficients to be checked is equal to (p-1)/2 and (2) their magnitude is massively greater than the prime itself! This is far, far worse than repeated division and infinitely worse than a modularity test which can perform a 100 -120 digit prime check in the time it takes to make and consume a mug of coffee even for a Muppet like me.
Without an understandable explanation or convincing demonstration of its performance the AKS algorithm has all the hallmarks of being a bit of a joke!
Could you guys make a video on the Collatz problem? Thanks for your awesome videos.
What's the fastest way to learn if a number is prime?
Just aks it.
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.
When you came here because of a difficult test but have no idea what he’s talking about
Every prime number satisfy:. ******[(n-2)!-1]÷n=whole number****
Where:
n is natural number
It amazes me, as a non-mathematician, that the solution to such a long existent problem, should appear so relatively simple. Or am I viewing the solution simplistically?
Awesome!
Geez. This is amazing.
I wonder who are those 3 people who clicked dislike on this video. I mean, I can get you not liking it (for whatever reason you may have), but why would you "dislike" it ??