Crible de détermination des nombres premiers basé sur (a + b) * (a - b) = (a * a - b * b)
Un article de Wikipedia.
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.
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 sont donc les suivants :
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
soit
3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
les nombres premiers impairs (tant) attendus !
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 = 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
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.
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.
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.
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.