There are a number of ways to check if a number is a prime number. Some of these are Probabilistic tests. Like the Fermat primality test.

Using Coprime integers

I wrote this when I working on an example for testing random-based code.

examples/python/fermat_primality_test/prime.py

import random
import math


def get_coprime(n):
    while True:
        coprime = random.randrange(n)
        if math.gcd(coprime, n) == 1:
            return coprime


def fermat_primality(n, count = 1):
    for _ in range(count):
        a = get_coprime(n)
        if (a ** (n-1)) % n != 1:
            return False
    return True

examples/python/fermat_primality_test/test_prime.py

import prime
import random


def test_coprime():
    random.seed(1)
    assert prime.get_coprime(10) == 9
    assert prime.get_coprime(10) == 1

    assert prime.get_coprime(100000) == 64937

def test_fermat_primality():
    random.seed(1)
    assert prime.fermat_primality(1000) == False