NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 26/07/2016

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

Nombres PREMIERS

 

Débutants

Nombres

Premiers

Probablement

Premiers ?

 

Glossaire

Nombres

Premiers

 

 

INDEX

 

Premiers et primalité

 

Crible d'Ératosthène

Presque-premiers

Carmichaël

Divisibilité

Pseudo Premiers

Carmichaël - Texte

Primalité

Liste pseudo-P.

 

Sommaire de cette page

>>> Les k-presque-premiers

>>> Les pseudo-premiers

>>> Retour sur Fermat

>>> Test de Fermat - non primalité

>>> Les nombres composés, premiers
         et les bâtards: nomenclature

>>> Statistiques 

 

 

 

 

 

 

LES PRESQUE NOMBRES PREMIERS

  

1) Par leurs facteurs: Les presque-premiers ou k-presque-premiers comprennent exactement k facteurs premiers.

 

2) Par leur résistance aux tests de primalité: ces sont les pseudo-premiers. 

Déterminer si un nombre est premier, ce n'est pas si simple ! On va découvrir des nombres pseudo-premiers de Poulet et d'autres encore "plus presque" premiers, les pseudo-premiers absolus de Carmichaël.

Ces races de nombres empêchent effectivement de trouver des critères absolus de reconnaissance de la primalité d'un nombre.

 

 

Les k-presque-premiers

 

Définition

 

Un entier n > 0 est dit k-presque premier, pour k  0, lorsqu'il est le produit d'exactement k nombres premiers.

 

Voir Nombres semi-premiers

Nombres k-presque premiers

 

Exemples

Voir Tables

 

 

 

 

 

 

Les pseudo-premiers

 

 RETOUR SUR FERMAT

 

Ce que dit le petit théorème de Fermat

 

p premier;

a et p étrangers;

a p-1 - 1 est divisible par p.

 

 

 

On sait aussi que:

 

 

Si p est premier, on a toujours cette divisibilité.

Si p n'est PAS premier, il existe des cas où la divisibilité marche aussi.

 

 

Ce théorème ne permet pas de reconnaître les nombres premiers

Il y a des p non premiers qui donnent le même résultat de divisibilité

 

Par contre, et bien obligé de s'en contenter, ce théorème donne les cas où p n'est pas premier, c'est à dire composé.

On les baptise n,  la lettre p étant réservée au nombre premiers.

 

  

TEST DE FERMAT – NON PRIMALITÉ

 

Test de Fermat

 

 

n est-il premier ou composé ?

a donné, compris entre 2 et n-1:

 

Si D = a n-1 - 1

N'est PAS divisible par n

n est composé.

 

 

 

  

Visualisons un peu ces choses!

 

*      Le test de Fermat nous permet de dire si un nombre n, à coup sûr, est composé (zone jaune).

 

*      Il nous dit aussi que, si n est premier, c'est sûr, D est divisible par n (zone verte). C'est le théorème de Fermat.

 

*      Cependant, il existe aussi des trouble-fêtes, les nombres pseudo-premiers,  qui divisent D sans être premiers.

 

 

 

 

LES NOMBRES COMPOSÉS,

PREMIERS et les bâtards

 

*      On va le dire tout de suite: il existe des pseudo-premiers encore plus coriaces: les pseudo-premiers absolus.

*      Si on avait eu l'idée de se dire: OK! Le test de Fermat ne marche pas pour une valeur de a, mais en effectuons le test pour plusieurs valeurs de a et par recoupement, on devrait y arriver.

*      C'est loupé! Car il existe des nombres pour lesquels la divisibilité est possible pour toutes les valeurs de a: les pseudo-premiers absolus.

 

 

Voyons ces familles!

Rappel:  D = a n-1 – 1

 

D ne divise pas n

D divise n

Composés

Probablement premiers

 

Pour une valeur de a données (ou des valeurs)

Pour toutes les valeurs de a

Ceux qui restent

 

Pseudo premiers

 

 

 

ou nombres de Poulet

Selon la valeur de a

on dit: 341 est 2 - pseudo premier, par exemple

 

 

 

 

Pseudo premiers absolus

 

 

 

ou nombres de Carmichaël

 

 

 

 

Premiers

 

 

 

Le problème est qu'on ne sait pas dire sûrement ceux qui restent.

Composé

1000

Poulet

341

Carmichaël

561

Premiers

 

 

 

 

 

STATISTIQUES – Pour a jusqu'à 25 milliards

Composés

Pseudo premiers

Pseudo premiers absolus

Premiers

 

95,64 %

 

Quantité de 2-pseudo-premiers :

0,00009 %

Moins de 1 sur 1 million.

Les pseudo-premiers sont rares !

Et encore plus rares pour a plus grand.

 

2-Pseudo premiers: 19 865

Pseudo premiers: 882 206 716

Pseudo premiers absolus:

 

4,36 %

Source: Merveilleux nombres premiers page 266

 

 

 

 

 

 

 

Suite

*    Pseudo Premiers

*    Théorie des nombresIndex

*    Primalité

*    Divisibilité

Voir

*    Fermat

*    Modulo & Congruences

*    Nombres Premiers

*    Primalité et suite de Perrin  

*    Pseudo Premiers

*    Pseudo Premiers Absolus

Livre

*     "Merveilleux nombres premiers" Excellent livre de Jean-Paul Delahaye qui traverse tout le monde de l'arithmétique  en douceur pour le lecteur amateur.

Cette page

http://villemin.gerard.free.fr/ThNbDemo/Primalit.htm