Just a small update: I came to the PSU Hackathon to learn the rudiments of coding. While random scrolling down wikipedia articles, I came across the AKS Primality test, created by three computer scientists at the Indian Institute of Technology, Kanpur. The Wikipedia page does a great job of explaining the algorithm. It is the first polynomial time algorithm ever to determine the primality of a number. And it is so simple!
The algorithm depends not the following fundamental fact: if is a prime number, and is a number co-prime to (say ), then for any integer , we have . This is a necessary and sufficient condition for primality! This is the simplest and most awesome thing I’ve seen in the recent past.
Note: Do you see why is if and only if is prime? Hint: For proving that this is not true for non-prime , consider , where is the smallest prime factor of .