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 (Résultats)
m (Résultats)
Ligne 319 : Ligne 319 :
Cette limite apparaît quand la valeur calculée à j = (i - 3) - 2 = i - 5 est supérieure à N soit
Cette limite apparaît quand la valeur calculée à j = (i - 3) - 2 = i - 5 est supérieure à N soit
-
i<sup>2</sup> - j<sup>2</sup> > N
+
i<sup>2</sup> - j<sup>2</sup> N
-
i<sup>2</sup> - (i - 5)<sup>2</sup> > N
+
i<sup>2</sup> - (i - 5)<sup>2</sup> N
(i + i - 5)(i - i + 5) > N
(i + i - 5)(i - i + 5) > N

Version du 27 décembre 2016 à 08:26

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 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 à 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

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

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

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é de la tige

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 valeurs entres les deux nombres impairs et (6 - 1 - 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

Conclusions

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) ...

Ressources

Lors de la Résolution d'une équation du second degré de manière graphique 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.