02/01/2010
Petit théorème de Fermat, nombres pseudo-premiers et nombres de Carmichael
Théorie des nombres -- Divisibilité et congruence
Théorie des nombres -- Nombres premiers
Théorème : Soit p un nombre premier, et a un entier premier avec p. Alors ap-1 a pour reste 1 dans la division par p : |
Malheureusement, le petit théorème de Fermat n'est pas une condition nécessaire et suffisante, et il existe des entiers n non premiers pour lesquel an-1=1 mod n. De tels entiers sont dits pseudopremiers de base a. Par exemple,
- 341=11×31 est pseudo-premier en base 2.
- 91=7×13 est pseudo-premier en base 3.
Théorème : n, entier non premier, est un nombre de Carmichael si, et seulement si, n =p1×...×pk, où p1,...,pk sont des nombres premiers deux à deux distincts tels que (pi-1) divise (n-1) pour tout i de {1,2,...,k}. |
Consulter aussi...
18:35 Publié dans Petit théorème de Fermat, nombres pseudo-premiers | Lien permanent | Commentaires (0) | Tags : petit théorème de fermat, nombres pseudo-premiers et nombres de carmichael | | del.icio.us | | Digg | Facebook