Crible de détermination des nombres premiers basé sur (a + b) * (a - b) = (a * a - b * b)

Un article de Wikipedia.

(Différences entre les versions)
m (Invariant et reconsidération du crible)
m (Nouveau crible)
Ligne 467 : Ligne 467 :
Si B = { b<sub>i , j</sub> } alors
Si B = { b<sub>i , j</sub> } alors
-
b<sub>i , 0</sub> = i<sup>2</sup> pour i impair &ge; 3
+
b<sub>i , 0</sub> = i<sup>2</sup> pour i = 2 k + 1 avec k &ge; 1
b<sub>i , j</sub> = b<sub>i , j - 1</sub> + 2 i pour j &ge; 1
b<sub>i , j</sub> = b<sub>i , j - 1</sub> + 2 i pour j &ge; 1

Version du 27 décembre 2016 à 22:21

Sommaire

Crible de détermination des nombres premiers basé sur (a + b) (a - b) = (a2 - b2)

But

Déterminer une méthode pour rechercher les nombres premiers en se basant sur la propriété (a + b) (a - b) = (a2 - b2).

Introduction

Soit la relation

(1) (a + b) (a - b) = (a2 - b2)

Elle peut être réécrite différemment en posant :

x = a + b
y = a - b

Il advient alors que

a = (x + y) / 2
b = (x - y) / 2

et la relation (1) se réécrit

(2) x y = [ (x + y) / 2 ]2 - [ (x - y) / 2 ]2

Cas particuliers et conséquences

Tous les nombres peuvent s'écrire comme des différences de carrés

En prenant

x = z
y = 1

alors par (2)

z = [ (z + 1) / 2 ]2 - [ (z - 1) / 2 ]2
Cas des nombres entiers impairs
Décomposition en différence de carrés successifs d'un nombre entier impair

Si z est un nombre entier impair alors il peut s'écrire comme la différence de deux carrés successifs.

Si z est un nombre entier impair

z = 2 n + 1 avec n ∈ N

alors

(z + 1) / 2 = (2 n + 1 + 1) / 2 = n + 1
(z - 1) / 2 = (2 n + 1 - 1) / 2 = n

donc par (2)

(3) z = 2 n + 1 = (n + 1)2 - n2

soit la différence de deux carrés de nombres entiers successifs.

Cas des nombres premiers impairs

Si p est un nombre premier impair alors il n'existe qu'une manière de l'écrire comme une différence de carrés.

Si p est un nombre premier impair alors par (3)

p = 2 n + 1 = (n + 1)2 - n2

Supposons maintenant qu'il existe deux nombres entiers positifs k et m non successifs tels que

p = k2 - m2 avec k - m > 1 et k > 0 et m > 0

alors

p = k2 - m2 = (k + m) (k - m)

p a donc deux diviseurs, k + m et k - m

Pour k + m, comme

m > 0

alors

m + 1 > 1
k + m > k

D'autre part, comme

k - m > 1

alors

k > m + 1

et donc,

k + m > k > m + 1 > 1  

Pour k - m, comme

k > m + 1

alors

k - m > 1

Ce qui impliquerait qu'il existerait deux diviseurs du nombre premier p plus grand que 1 ce qui contredit le fait que p est un nombre premier.

Donc, il n'existe qu'une manière d'écrire un nombre premier comme une différence de carrés soit par la différence de carrés successifs.

Cas des nombres entiers composés impairs

Si n est un nombre entier composé impair, alors il existe plusieurs représentations sous forme de différence de deux carrés.

Si n est un nombre entier composé impair

z = 2 n + 1 = k m avec k, m ∈ N et k, m > 1

alors il existe au moins deux représentations sous forme d'un différence de carrés :

La première pour z comme étant un nombre impair par (3)

z = 2 n + 1 = (n + 1)2 - n2

et la deuxième pour z comme étant un nombre composé en utilisant le cas général (2)

z = k m = [ (k + m) / 2 ]2 - [ (k - m) / 2 ]2

A chaque décomposition du nombre z, il existe une autre représentation par une différence de carrés.

Décomposition d'un nombre entier composé impair

Avec z = k m impair, k et m sont impairs

k = 2 q + 1
m = 2 r + 1

et

z = k m = [ (2 q + 1 + 2 r + 1) / 2 ]2 - [ (2 q + 1 - 2 r - 1) / 2 ]2 = (q + r + 1)2 - (q - r)2

Dans ce cas, la différence des carrés est différente d'une différence de carrés de nombres successifs.

Seul la différence de deux carrés de parités différentes est impaire

La différence de carrés de nombres de même parité est paire.

Si k et m sont des entiers pairs

k = 2 q
m = 2 r

alors

k2 - m2 = (k + m)(k - m) = (2 q + 2 r)(2 q - 2 r) = 4 (q + r)(q - r)

soit un nombre pair.

Si k' et m' sont des entiers impairs

k' = 2 q' + 1
m' = 2 r' + 1

alors

k'2 - m'2 = (k' + m')(k' - m') = (2 q' + 1 + 2 r' + 1)(2 q' + 1 - 2 r' - 1) = 4 (q' + r' + 1)(q' - r')

soit un nombre pair.

La différence de carrés de nombres de parités différentes est impaire.

Si k' est un entier impair et m est un entier pair

k' = 2 q' + 1
m = 2 r

alors

k'2 - m2 = (k' + m)(k' - m) = (2 q' + 1 + 2 r)(2 q' + 1 - 2 r) = [ 2 (q' + r) + 1 ][ 2 (q' - r) + 1 ]

soit le produit de deux nombres impairs qui est impair.

Si k est un entier pair et m' est un entier impair

k = 2 q
m' = 2 r' + 1

alors

k2 - m'2 = (k + m')(k - m') = (2 q + 2 r' + 1)(2 q - 2 r' - 1) = [ 2 (q + r') + 1 ][ 2 (q - r') - 1 ]

soit le produit de deux nombres impairs qui est impair.

Crible de détermination des nombres premiers

Le crible de détermination des nombres premiers se déduit des considérations précédentes.


Dans une une matrice A = {ai , j} de k lignes et k colonnes il faut calculer ai , j = i2 - j2 pour i ≤ k et j ≤ i - 3

Les nombres impairs qui apparaissent sont alors des nombres composés qu'il faut exclure de la liste des nombres premiers.


Remarques

La borne supérieure pour j provient des considérations suivantes :

Pour j > i, la différence est négative;

Pour j = i, la différence est nulle;

Pour j = i - 1, c'est la seule manière de produire les nombres premiers;

Pour j = i - 2, les nombres sont de parités identiques et produisent des nombres pairs.


Tous les carrés doivent être calculés, zéro et 1 compris, mais par contre, seul les carrés des nombres impairs et la différence de carrés de nombres de parités différentes produiront des nombres impairs à exclure.

Révision du crible

Une fois les calculs effectués le résultat conduit à une manière bien plus simple de réaliser le calcul des nombres impairs à exclure de la liste des nombres premiers potentiels (voir les résultats ci-dessous).

Taille minimale de la matrice pour déterminer les nombres premiers inférieurs ou égal à N

Pour i donné, la différence impaire la plus petite des carrés est obtenue pour j = i - 3.

Donc

i2 - j2 = (i + j)(i - j) = (i + i - 3)(i - i + 3) = 3 (2 i - 3)

Pour un N donné, il faut disposer d'une matrice k x k telle que

(4) 3 ( 2 k - 3 ) ≥ N

soit

(4') k ≥ (N / 3 + 3) / 2

ou

(4") k ≥ (N + 9) / 6

Limite inférieure dans la détermination des nombres premiers inférieurs ou égal à N

Avec

n = i2 - j2

Pour que

n ≤ N

il faut que

i2 - j2 ≤ N

et donc

j2 ≥ i2 - N

Limite à postériori du début de la tige des valeurs

En calculant uniquement les valeurs pour lesquelles i2 - j2 ≤ N, il apparaît que les valeurs semblent se détacher en deux parties, celles des i inférieurs regroupées en grappe et à celles à partir d'une certaine limite, qui est calculée ici, qui forment comme une tige correspondant à l'unique valeur associé à j = i - 3.

Le début de la tige commence lorsque la valeur associée à j = (i - 3) - 2 = i - 5 est supérieure à N, soit

i2 - j2 > N pour j = i - 5

soit

i2 - (i - 5)2 > N

ou

(i + i - 5)(i - i + 5) > N

5 ( 2 i - 5) > N

ou encore

i > (N / 5 + 5) / 2

soit

(5) i > (N + 25) / 10

Résultats

Une simple feuille de calcul permet un rapide calcul des nombres impairs à exclure de la liste des nombres premiers.

Un exemplaire d'une feuille de calculs LibreOffice Calc est fournie dans les ressources.

Un exemple de calcul est fourni ci-dessous pour N = 51.

La valeur de N = 51 a été déterminée à partir de l'équation (4) pour k = 10 soit

N ≤ 3 ( 2 k - 3) = 3 ( 2 * 10 - 3) = 3 * 17 = 51
i*i-j*j	j	0	1	2	3	4	5	6	7	8	9	10	11	12
j * j 0 1 4 9 16 25 36 49 64 81 100 121 144
i i * i
0 0
1 1
2 4
3 9 9
4 16 15
5 25 25 21
6 36 35 27
7 49 49 45 33
8 64 39
9 81 45
10 100 51
11 121
12 144

Nous avons bien qu'au delà de i = 10, plus aucune valeur n'est inférieure à N = 51.


Nombres premiers impairs inférieurs à 51

Et finalement, le cœur de cet article, les nombres premiers impairs inférieurs ou égal à 51 s'obtiennent en supprimant de la liste des nombres impairs

3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51

les nombres impairs calculés

9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51

soit

3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51

pour enfin obtenir

3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

la liste de nombres premiers impairs inférieurs ou égal à 51 !


Grappe et tige

Ce qui apparaît est un ensemble de valeurs qui semblent former deux groupes différents, une grappe pour des valeurs inférieures à un certain i et une tige constituée d'une unique valeur calculée à j = i - 3.

Cette limite apparaît quand la valeur calculée à j = (i - 3) - 2 = i - 5 est supérieure à N soit

i2 - j2 > N pour j = i - 5

i2 - (i - 5)2 > N

(i + i - 5)(i - i + 5) > N

5 (2 i - 5) > N

i > (N / 5 + 5) / 2

i > (N + 25) / 10

Ici, avec N = 51,

i > (51 + 25) / 10
 
i > 76 / 10
 
i > 7.6

Et nous voyons bien qu'effectivement, à partir de i = 8, une unique valeur est inférieure à N, celle calculée à j = i - 3.

Propriétés de la tige

Nombres premiers consécutifs

Dans la tige précédente, nous voyons que l'écart entre les valeurs à exclure donnent la place à deux nombres premiers consécutifs potentiels mais nous voyons aussi que des valeurs de la grappe viennent contrecarrer cette régularité.

Par exemple, dans la tige, entre 45 et 51, la grappe contient 49 qui détruit la régularité des nombres premiers consécutifs.

Nombre de valeurs entre i et i + 1 pour j = i - 3 :

Pour un i donné à j = i - 3

i2 - j2 pour j = i - 3
i2 - (i - 3)2 = (i + i - 3)(i - i + 3) = 3 (2 i - 3)

La différence entre les valeurs à i et i + 1 vaut alors

(6) 3 (2 (i + 1) - 3) - 3 (2 i - 3) = 6

Il y a 6 - 1 = 5 valeurs entres les deux nombres impairs et (5 - 1) / 2 = 2 valeurs impaires.


En effet, pour une différence de 6 entre deux valeurs impaires

1 2 3 4 5 6 7

il y a 6 - 1 = 5 valeurs

2 3 4 5 6

et seulement (5 - 1) / 2 = 2 valeurs impaires

3 5

Quantité de nombres impairs dans la tige

La différence entre la taille de la matrice pour N donné (4") et la limite inférieure de la tige (5) donne une idée du nombre de valeurs impaires dans la tige.

Estimation du nombre de valeurs impaires dans la tige

(N + 9) / 6 - (N + 25) / 10 = N (1 / 6 - 1 / 10) + 9 / 6 - 25 / 10 = N / 15 - 1

soit

estimation du nombre de valeurs impaires dans la tige = N / 15 - 1

La quantité de valeurs impaires croît linéairement avec N ce qui donne la place à une infinité de nombres premiers consécutifs.

Invariant et reconsidération du crible

Le résultat de l'équation (6) indiquant que la différence entre les valeurs de la tige pour les j = i - 3 est constante sur la tige met le doigt sur un point intéressant.

En regardant de plus près le calcul des nombres impairs, nous constatons d'une part que pour la tige, les nombres successifs sont espacés de 6 et que la situation est similaire pour les autres trajectoires parallèles à la tige.

Depuis 25 nous avons 35, 45, ... soit une différence de 10 entre les nombres.

Depuis 49 c'est impossible à voir dans le résultat indiqué mais la feuille de calcul permet de voir que la suite est 49, 63, 77 soit une différence de 14 entre les nombres.

Calculons alors la différence entre la valeur en i, j et en i + 1, j + 1

d = (i + 1)2 - (j + 1)2 - (i2 - j2) = (i + 1 + j + 1)(i + 1 - j - 1) - (i2 - j2)
d = (i + j + 2)(i - j) - (i2 - j2) = (i2 - j2) + 2 (i - j) - (i2 - j2)
(7) d = 2 (i - j)


i - j est invariant sur la tige et les lignes parallèles à la tige.


Un simple calcul permet de confirmer le résultat

i = 3
j = 0
d = 2 (3 - 0) = 6

qui est bien la différence du calcul de la tige.

Et de même pour les autres différences

i = 5
j = 0
d = 2 * 5 = 10

et

i = 7
j = 0
d = 2 * 7 = 14

Nouveau crible

Le crible devient encore plus simple.

En partant de i = 3, il faut calculer i2 et les valeurs successives en ajoutant 2 i tant que le résultat est inférieur à N puis passer à i + 2 et continuer tant que les valeurs sont inférieures à N.


Si B = { bi , j } alors

bi , 0 = i2 pour i = 2 k + 1 avec k ≥ 1
bi , j = bi , j - 1 + 2 i pour j ≥ 1

avec

bi , j ≤ N


Un point intéressant est la possibilité de calculer en parallèle les différentes valeurs en partant d'un i2 donné.

Conclusions

Pour commencer, c'est lors de la Résolution d'une équation du second degré de manière graphique qu'est apparue une relation (équation (13) entre le produit et la différence des carrés de la moyenne et de la différence des solutions de l'équation du second degré qui s'est avérée être une réécriture de (a + b)(a - b) = a2 - b2 et qui est à l'origine des considérations de cet article.

Un intérêt de ce crible est sa fuite en avant dans la recherche des nombres à exclure, aucune nécessité de retour en arrière pour répéter des opérations. A une nouvelle étape, il faut calculer un nouveau carré et les différences avec les carrés précédemment calculés. Mais, bien sûr, au prix de la conservation de tous les carrés et des nombres impairs déjà calculés et qu'il faudra exclure aux étapes suivantes. ... pas de repas gratuit (No Free Lunch) ...

C'est toujours une surprise de voir qu'une relation simple que j'ai utilisée un nombre incalculable de fois peut encore être interprétée d'une nouvelle façon pour révéler des choses insoupçonnées.

La présence d'une tige dans les valeurs à exclure pour laisser la place à deux nombres premiers potentiels consécutifs a été une autre surprise inattendue. Au lieu de parler d'explication aux nombres premiers consécutifs, je dirais plutôt que c'est un révélateur d'une structure intrinsèque des nombres premiers. En fait, il faudrait même dire que c'est lié au caractère composé des nombres non premiers puisque c'est la présence des nombres composés de la grappe qui contrarie l'apparition des nombres premiers consécutifs de la tige.

Ressources

Feuille de calculs LibreOffice Calc 4.3.7.2 permettant de calculer les nombres impairs à exclure de la liste des nombres premiers potentiels pour N ≤ 591 (100 lignes et 100 colonnes) Determination-des-nombres-premiers.ods.zip.

Pour les utilisateurs de Microsoft Excel, le même fichier que précédemment enregistré au format Microsoft Excel 2007/2010/2013 XML Determination-des-nombres-premiers.xlsx.zip et au format Microsoft Excel 97/2000/XP/2003 Determination-des-nombres-premiers.xls.zip.