# Fermat primality test

Fermat's little theorem

a**p =~ a (mod p)
a**p mod p = a mod p

Algorithm

# cat FermatPrimalityTest.go
package main

import "fmt"
import "math/big"
import "os"
import "strconv"

func add(x, y int) int {
        return x + y
}

func main() {
        prime, err1 := strconv.Atoi(os.Args[1])
        limit, err2 := strconv.Atoi(os.Args[2])
        if err1 == nil && err2 == nil {
                for i := 1; i < limit; i++ {
                        exp := new(big.Int).Exp(big.NewInt(int64(i)), big.NewInt(int64(prime)), nil)
                        left := new(big.Int).Mod(exp, big.NewInt(int64(prime)))
                        right := new(big.Int).Mod(big.NewInt(int64(i)), big.NewInt(int64(prime)))
                        if left.Cmp(right) != 0 {
                                fmt.Printf("%d != %d\n", left, right)
                                fmt.Printf("Not prime!\n");
                                return
                        }
                }
        }
        fmt.Printf("Prime!\n");
}

# go build FermatPrimalityTest.go

# ./FermatPrimalityTest 7 1000
Prime!
# carmichael_number_1=561
# carmichael_number_2=41041
# ./FermatPrimalityTest $carmichael_number_1 1000
Prime! <-- False
# ./FermatPrimalityTest $carmichael_number_2 1000
Prime! <-- False

References

https://en.wikipedia.org/wiki/Carmichael_number