Test de primalité

Bonjour chers amis des mathématiques !

Je fais appel à l'intelligence collective du forum, certains que beaucoup d'entre vous sont plus callés que moi.

Après avoir travaillé un certain temps (...) sur les nombres premiers, j'en suis venu aux conclusions suivante que je vais m'efforcer de détailler point par point. Les résultats que j'expose ici ne sont que des exemples, mais s'efforcent de former les bribes d'une théorie plus générale.

Désolé si l'énoncé est parfois (très) mal senti, je ne suis pas du tout mathématicien de formation (et bien loin de l'être). Je compte sur vous pour m'aider à améliorer tout ça, si possible !

Petite précision, quand je parle de test de primalité par division, on considère évidemment qu'un nombre est premier si le reste de la division euclidienne est non nul (à part pour lui-même et pour 1 comme diviseur).

___________________

1) x, où x est un nombre premier, ne devient le seul diviseur d'un nombre qu'à x². Autrement dit x ne construit aucun nombre entier avant x².

2) Les nombres premiers < x suffisent donc à construire tout les nombres entiers (donc à tester la primalité par division de tout les nombres) jusqu'à x²-1 inclus.

3) On affirme donc que les nombres premiers [1, 100] suffisent à construire tout les nombres entiers jusqu'à x²-1, où x est le nombre premier suivant 100.

x² -1 = 101²-1 = 10200

Les nombres premiers [1, 100] suffisent donc à construire tout les nombres entiers jusqu'à 10200 / à tester la primalité de tout les nombres jusqu'à 10200.

Une formulation simplifiée ne nécessitant pas la connaissance de x² peut consister à dire que les nombres premiers [1, 100] suffisent à construire tout les nombres entiers jusqu'à 100², étant donné que 100² < x²-1, où x est le nombre premier suivant 100.

4) Ces constatations faîtes, on peut établir systématiquement le test de primalité suivant. On considère une suite de nombre premier, par exemple [1, 10], à savoir :

2, 3, 5, 7

Pour l'exemple, on prend 5 comme point de départ du test de primalité par division.

On sait que les nombres premiers [1, 5], donc 2,3,5, permettent de tester la primalité de tout les nombres jusqu'à x²-1, où x est le nombre premier suivant 5.

x²-1 = 49²-1 = 48

Les nombres premiers [1, 5] permettent donc de tester la primalité de tout les nombres jusqu'à 48 inclus.

Très simplement, à partir de là, on inclut un nombre premier dans le test de primalité dès qu'il s'agit de tester son carré.

2,3,5,7 permettent de tester tout les nombres jusqu'à x²-1, où x est le nombre premier suivant...


____________________

Merci d'avoir pris le temps de lire mon énoncé. Je m'excuse d'avance si c'est trivial car déjà prouvé, j'avoue que je n'ai pas (encore) avalé toute la littérature scientifique sur les nombres premiers. Je trouve en tout cas cette théorie très charmante... Jusqu'à aussi loin que mes vérifications sont allées, elle n'a pour l'instant montré aucune erreur.

Arckz

PS : peut-être que j'écrirai sous peu un programme "test de primalité" sur ce modèle, j'utilise pour le moment un crible évolutif, où l'on ne commence à tracer les multiples d'un nombre premier qu'à partir de son carré.