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)
(Crible de détermination des nombres premiers)
(Conclusions)
Ligne 194 : Ligne 194 :
== Conclusions ==
== 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.
 +
== Ressources ==
== Ressources ==

Version du 26 décembre 2016 à 13:18

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 et k > m + 1

alors

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é impaire

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 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 en différence de carrés successifs d'un nombre entier composé impair

Par le cas général des nombres entiers impairs, un nombre entier composé impair est aussi représenté par une différence de carrés 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é différente 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 - 2 (i la ligne et j la colonne)

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 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ésultats

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.

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