From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 82709BBAF for ; Tue, 10 Aug 2010 14:46:51 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AmsCAJrnYEzRVdc0kGdsb2JhbACTYYxuCBUBAQEBCQkMBxEDH6gKiRCCEYYrLohUAQEDBYU1BIhbXw X-IronPort-AV: E=Sophos;i="4.55,348,1278280800"; d="scan'208";a="67461653" Received: from mail-ew0-f52.google.com ([209.85.215.52]) by mail4-smtp-sop.national.inria.fr with ESMTP; 10 Aug 2010 14:46:50 +0200 Received: by ewy20 with SMTP id 20so4463469ewy.39 for ; Tue, 10 Aug 2010 05:46:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:received:in-reply-to :references:date:message-id:subject:from:to:content-type :content-transfer-encoding; bh=yh2LhjK9DOJ7MSZ1PAF+oAPrauKiddCU2iFEgJUoiWE=; b=INwJnwO6CK3EZhh+B9IczYg3abLD8FUV73BYCaIjFKLVB/LOhCLAaIRZLrRyPtuuk2 k3EVTQM1Qyu8Y/YHIGayzV53bmB7iqnXC2lsKN0f5DTEFbxrz0Ky8pjjCWoKkkgcUTKu NxIKQTxqPdJIxdL4E20Iabga+F2jyac0DRv08= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type:content-transfer-encoding; b=DY//cJDXoleUwibWnTQo3WTznbKjniaaICPs6tJMzdYte6aFZoLdcZODZNXvVuKNNp BNCLqW/PJf5XthYvgAQILF4T+SGvepRG0K+ZppnXOTihZA8lnxLt2l9nUPHYGfEylwYq cvAeHp8rCuaTNr3UhFNNNyV+X9GI+oKIT70SQ= MIME-Version: 1.0 Received: by 10.213.44.129 with SMTP id a1mr13530884ebf.57.1281444409661; Tue, 10 Aug 2010 05:46:49 -0700 (PDT) Received: by 10.14.121.16 with HTTP; Tue, 10 Aug 2010 05:46:49 -0700 (PDT) In-Reply-To: <20100810123410.GC16292@vaio.jimpryor.net> References: <20100810123410.GC16292@vaio.jimpryor.net> Date: Tue, 10 Aug 2010 08:46:49 -0400 Message-ID: Subject: Re: [Caml-list] Errors in Bignum arithmetic? From: David House To: caml-list@yquem.inria.fr Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Spam: no; 0.00; bignum:01 a's:01 val:01 wrote:01 rec:01 caml-list:01 arithmetic:01 wolfram:01 int:01 int:01 theorem:02 caml:02 let:03 indeed:07 definition:07 On 10 August 2010 08:34, Jim Pryor wrote: > Fermat's Little Theorem says that when p is prime, then for all 1<=3Da a**(p-1) mod p =3D 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 mist= ake in that list, but I've seen the segment of it < 10k also reported elsew= here. You've missed a small detail in the definition here. n is Carmichael iff a^(n-1) =3D 1 (mod n) for all a with gcd(a,n) =3D 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 =3D if b =3D 0 then a else gcd b (a mod b);; val gcd : int -> int -> int =3D # List.map (fun (a,b) -> gcd a b) [561,3; 1105,5; 2465,5; 10585,5];; - : int list =3D [3; 5; 5; 5]