### # 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)
limit, err2 := strconv.Atoi(os.Args)
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