Re: [Caml-list] Errors in Bignum arithmetic?

[David House <dmhouse@gmail.com>]

On 10 August 2010 08:34, Jim Pryor <lists+caml@jimpryor.net> wrote:
> Fermat's Little Theorem says that when p is prime, then for all 1<=a<p,
> a**(p-1) mod p = 1. However, some composite p also have this property
> for some choices of a. However, if one checks a handful of a, only a few
> composite p will have the property wrt all of them. This is the basis of
> one fairly reliable indeterministic test for primality.
>
> The Carmichael numbers are a series of composites that have the property
> for all choices of a. http://mathworld.wolfram.com/CarmichaelNumber.html tells us the first few Carmichael numbers are [561; 1105; 1729; 2465; 2821; 6601; 8911; 10585; 15841; 29341]. Conceivably there's a typographical mistake in that list, but I've seen the segment of it < 10k also reported elsewhere.

You've missed a small detail in the definition here. n is Carmichael
iff a^(n-1) = 1 (mod n) for all a with gcd(a,n) = 1; in other words,
you are only allowed to consider a's which are coprime to your
supposed Carmichael number.

And indeed,

# let rec gcd a b = if b = 0 then a else gcd b (a mod b);;
val gcd : int -> int -> int = <fun>
# List.map (fun (a,b) -> gcd a b) [561,3; 1105,5; 2465,5; 10585,5];;
- : int list = [3; 5; 5; 5]