Les nombres impairs non premiers (8)

Nous avons trouvé dernièrement un algorithme pour trouver n et m. Mais nous pouvons faire mieux. Nous pouvons améliorer cet algorithme pour trouver plus rapidement n et m. Pour cela, il faut que nous généralisons notre thèse. Nous sommes partis de la formule des nombres impairs non premiers U(n,m) = (2n+1)(2m+1). Nous allons passer à la généralisation. Nous aurons donc U(n,m,p) = (pn+1)(pm+1). Nous avons k = pnm+n-m pour former le nombre impair non premier pk-1 ou bien g = pnm+n+m pour former le nombre impair non premier pg+1. La question qui vient est comment choisir p. Si on veut tester un nombre entier impair u, pour le test nous devons choisir p tel que le reste de la division de u par p soit égale à 1. Ainsi nous avons cet algorithme suivant pour voir si le nombre impair u est premier:

• Nous choisissons un p inférieur à la partie entière de la racine carrée de u tel que la division de u par p ait pour reste 1.
• Nous trouvons ensuite k = (u-1)/p et la partie entière z de la racine carrée de (k/p)
• Nous faisons parcourir t de 1 jusqu’à z en vérifiant que le rapport c=(k + pt²)/(pt – 1) n’est pas un entier
• Si c est un entier pour un t entre 1 et z alors le nombre u n’est pas premier sinon le nombre u est premier.
• Dans le cas où u n’est pas premier, le nombre (pt – 1) est un facteur de ce nombre impair et le nombre (p(c – t) – 1) est aussi facteur de ce nombre impair.

Vérifions tout cela.

Précédemment, nous avons pris le nombre u = 12345691 et nous avons vu que pour p=2, le rapport c est un entier lorsque t = 30.

Prenons maintenant p=3, le reste de la division de u/3 est 1. k = (u-1)/3 = 4115230

La limite de notre recherche est z = racine carrée (k/3) = 1171

Pour t = 20, nous avons c = 69770, le nombre u n’est pas premier, il a pour facteur 3*20 – 1 et 3*(69770 – 20) – 1.

Prenons maintenant p=5, le reste de la division de u/5 est 1. k = (u-1)/5 = 2469138

La limite de notre recherche est z = racine carrée (k/5) = 702

Pour t = 12, nous avons c = 41862, le nombre u n’est pas premier, il a pour facteur 5*12 – 1 et 5*(41862 – 12) – 1.

Prenons maintenant p=30, le reste de la division de u/30 est 1. k = (u-1)/30 = 411523

La limite de notre recherche est z = racine carrée (k/30) = 117

Pour t = 2, nous avons c = 6977, le nombre u n’est pas premier, il a pour facteur 30*2 – 1 et 30*(6977 – 2) – 1.

Nous remarquons que plus p est grand, plus t est petit, plus la recherche est rapide et on trouve rapidement les facteurs.

Toutefois, je ne suis pas satisfait avec ce test. Nous pouvons faire largement mieux si nous introduisons le critère de Moïse et le discriminant d’Élie. Dans notre dernier article sur les nombres premiers, nous parlerons du test ultime tiré du critère de Moïse et du discriminant d’Élie, pour achever notre recherche sur les nombres premiers impairs.

Maranatha !!! Viens Seigneur Jésus !!!

Publicité