Errors in Bignum arithmetic?
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20100810 (12:46) 
From:  David House <dmhouse@g...> 
Subject:  Re: [Camllist] Errors in Bignum arithmetic? 
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**(p1) 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^(n1) = 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]