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 $n$ is a prime number, and $a$ is a number co-prime to $n$ (say $n-1$), then for any integer $x$, we have $x^n+a\equiv (x+a)^n \pmod {n}$. 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 ${n\choose k}\equiv 0 \pmod {n}$ is if and only if $n$ is prime? Hint: For proving that this is not true for non-prime $n$, consider ${n\choose j}$, where $j$ is the smallest prime factor of $n$.

1. danaj says:
1. ayushkhaitan3437 says: