From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 78B57BBAF for ; Tue, 10 Aug 2010 14:52:20 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AmwCABPoYEzRVaE0kGdsb2JhbACDFZBMjG4IFQEBAQEJCQwHEQMfqA2IVDyCEYYrLohUAQEDBYEhgyFzBIhbXw X-IronPort-AV: E=Sophos;i="4.55,348,1278280800"; d="scan'208";a="55270297" Received: from mail-fx0-f52.google.com ([209.85.161.52]) by mail3-smtp-sop.national.inria.fr with ESMTP; 10 Aug 2010 14:52:20 +0200 Received: by fxm10 with SMTP id 10so740689fxm.39 for ; Tue, 10 Aug 2010 05:52:19 -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; bh=o/fjQfXxfsIUsHXQc9f7W9ogazxTewmNkiYfk9mqjcI=; b=AQ2+PJUby3E/FYcuAuI/YIw5QKrYgKBrOhW7AWGZE68buB5ZlAUwjWvsjVjR+xzkK2 0sA+W61CtELiCFBOiYaxMq0Y+ATt4ZaI/Fa0DQDZ2hgTN9DkKVpVOtbO1xnCPwDkrBMI bzCjGH4lZPRE1qJleqhIQxO4kOEjVVYUCVoZ8= 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; b=JIv5nVB+WCg8/eUDLZQcbrj2R6ET6ssO8oBJnl/xUzdJpvge8ynyVYVHWSka+FNWPb BCIsyvVFXuIXsdmCXbA/juH/Gxh4RNmb2jMPWGt8pjNT9xFsE7pLa7mQ/WNOwmnnVxp2 NyfGfCyPMxI83ldXvFsfW4ZPvLlYfOTTaX2ZE= MIME-Version: 1.0 Received: by 10.223.103.134 with SMTP id k6mr18167936fao.5.1281444739471; Tue, 10 Aug 2010 05:52:19 -0700 (PDT) Received: by 10.223.85.144 with HTTP; Tue, 10 Aug 2010 05:52:19 -0700 (PDT) In-Reply-To: <20100810123410.GC16292@vaio.jimpryor.net> References: <20100810123410.GC16292@vaio.jimpryor.net> Date: Tue, 10 Aug 2010 14:52:19 +0200 Message-ID: Subject: Re: [Caml-list] Errors in Bignum arithmetic? From: Ronan Le Hy To: caml-list@yquem.inria.fr Content-Type: text/plain; charset=UTF-8 X-Spam: no; 0.00; bignum:01 ronan:01 ronan:01 caml-list:01 arithmetic:01 wolfram:01 theorem:02 caml:02 examples:07 2010:83 hello:17 explains:17 then:17 mod:18 mod:18 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 : > 3**(561-1) mod 561 = 1 > 5**(1105-1) mod 1105 = 1 > 5**(2465-1) mod 2465 = 1 > 5**(10585-1) mod 10585 = 1 -- Ronan