- Define .
- For each , define .
- Then is prime if and only if .
That is, start with , and at each step, square the current number, subtract two, and take the remainder when divided by . Do this times. is prime if you end with zero, and composite if you don’t.
Let’s do two small examples, one when is prime and one when it isn’t.
For , we get
so is prime. For , we get
so is not prime (though note this doesn’t really help us factor it!).