The Euclidean algorithm  the algorithm to compute the greatest common divisor  or   of two numbers  dates back to antiquity (obviously) We can use it to make a fast test for primality  at least up to some confidence—and that’s where the inclusion-exclusion principle comes in