Version française
Home     About     Download     Resources     Contact us    
Browse thread
Errors in Bignum arithmetic?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Ronan Le Hy <ronan.lehy@g...>
Subject: Re: [Caml-list] Errors in Bignum arithmetic?
Hello,

2010/8/10 Jim Pryor <lists+caml@jimpryor.net>:
> Fermat's Little Theorem says that when p is prime, then for all 1<=a<p,
> 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