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 C0883BBAF for ; Tue, 10 Aug 2010 15:40:55 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AscAAFPzYExCbwQZkWdsb2JhbACTYYx2FQEBAQEJCwoHEQQewnQFhTqIX1+CXg X-IronPort-AV: E=Sophos;i="4.55,348,1278280800"; d="scan'208";a="67463342" Received: from out1.smtp.messagingengine.com ([66.111.4.25]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/ADH-AES256-SHA; 10 Aug 2010 15:40:55 +0200 Received: from compute3.internal (compute3.internal [10.202.2.43]) by gateway1.messagingengine.com (Postfix) with ESMTP id 66167247 for ; Tue, 10 Aug 2010 09:40:53 -0400 (EDT) Received: from frontend1.messagingengine.com ([10.202.2.160]) by compute3.internal (MEProxy); Tue, 10 Aug 2010 09:40:53 -0400 DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=messagingengine.com; h=date:from:to:subject:message-id:mime-version:content-type:in-reply-to; s=smtpout; bh=SD9cnR+uU6E0UOdO0e5hqUeY6YY=; b=HlDAhVcIu/gSsFmeb2zhtN6KPEAc270Rwzp5SiPg1l8YZqjH9ww98fRFh7eXsq6eLRzZcmfDtnZKYmi4cc4ng8uNz2HcdWFfzr18piJ+kzRXG1bTUIxhA103Z3fnujR7aTkT1KIqKUCwK4A795hWHRPaESo+78QW2r63XuWNBkA= X-Sasl-enc: IZhY0lFqtjwiFJsxV4G3exiM+C+9f01p7IGEygBd7A8X 1281447653 Received: from localhost (unknown [69.86.121.157]) by mail.messagingengine.com (Postfix) with ESMTPSA id 22DEE40060F for ; Tue, 10 Aug 2010 09:40:53 -0400 (EDT) Date: Tue, 10 Aug 2010 09:42:12 -0400 From: Jim Pryor To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Errors in Bignum arithmetic? Message-ID: <20100810134212.GD16292@vaio.jimpryor.net> Mail-Followup-To: caml-list@yquem.inria.fr MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.20 (2009-06-14) X-Spam: no; 0.00; bignum:01 a's:01 0200,:01 ronan:01 10,:98 10,:98 wrote:01 wrote:01 caml-list:01 arithmetic:01 wolfram:01 theorem:02 caml:02 caml:02 tue:06 On Tue, Aug 10, 2010 at 08:46:49AM -0400, David House wrote: > > 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. > On Tue, Aug 10, 2010 at 02:52:19PM +0200, Ronan Le Hy wrote: > Hello, > > 2010/8/10 Jim Pryor : > > Fermat's Little Theorem says that when p is prime, then for all 1<=a > a**(p-1) mod p = 1. [...] > > > > The Carmichael numbers are a series of composites that have the property > > for all choices of a. http://mathworld.wolfram.com/CarmichaelNumber.html > > This page says "for every choice of a [...] where a and p are > relatively prime". I believe that explains that your examples below do > not work : Excellent, I thought the error was most likely my own. Thanks for identifying it so quickly. -- Jim Pryor profjim@jimpryor.net