So testing that condition for several random values of a can be used as evidence that p is probably prime.
This site explains the Fermat primality test and its flaws in more detail:
from random import randint p = int(raw_input("Input potential prime: ")) for i in range(5): a = randint(2,p-2) if pow(a, p-1, p) == 1: print "Test passed for ", a else: print "Test failed for ", a
As shown below, 11 and 13 pass all the tests because they are prime, but 100 and 121 fail because they aren't.
It works, because Python really can handle any size of integer, as shown below.
Find the first number above it which is prime. The flag is That number is the flag
The flag is that number as one long integer, like
Find the first set of companion primes above
The flag is the lower of the two primes, as one long integer, like