Comment reconnaître deux nombres premiers jumeaux ?

Deux nombres premiers p et p+2 qui ne diffèrent que de 2 s’appellent une paire de nombres premiers jumeaux. Par exemple, les nombres 3 et 5 forment une paire de nombres premiers jumeaux. Le 14 Septembre 2016, le projet de calcul distribué PrimeGrid annonçait avoir découvert que les nombres

2 \, 996 \, 863 \, 034 \, 895 \times 2^{1 \, 290 \,  000} - 1 et 2 \, 996 \, 863 \, 034 \, 895 \times 2^{1 \, 290 \,  000} + 1

sont eux aussi des nombres premiers jumeaux. Ces nombres, au demeurant gigantesques (ils sont composés de 388 342 chiffres chacun !), sont la plus grande paire de nombres premiers jumeaux qu’on n’ait jamais trouvée !

Si l’on en croît l’annonce officielle de la découverte, on a vérifié que chacun de ces deux nombres est premier en leur appliquant à chacun le test de primalité LLR. Mais saviez-vous qu’il existe une formule très simple et qui tient en une ligne permettant de dire si deux nombres quelconques qui diffèrent de 2 sont des nombres premiers jumeaux ? Bon, c’est vrai que cette formule est peu efficace en pratique comme nous le verrons, mais elle a tout de même le mérite d’exister !

Un critère de gémellité

Voici donc le critère très simple permettant de dire si deux nombres n et n+2 forment une paire de nombres premiers jumeaux:

Soit n>1 un entier naturel. Les nombres n et n+2 sont deux nombres premiers jumeaux si, et seulement si,

4 \times [(n-1)! + 1] + n \equiv 0 \mod [n(n+2)]

Comme vous l’avez peut-être noté, ce critère se rapproche beaucoup du théorème de Wilson (qui dit que n est premier si, et seulement si, (n-1)!+1 \equiv 0 \mod [n]) et ce n’est pas un hasard !

Ce critère ne s'applique pas à Igor et Grichka. Impossible donc de savoir s'ils sont premiers, ni même jumeaux.

Ce critère ne s’applique pas à Igor et Grichka. Impossible donc de savoir s’ils sont premiers, ni même jumeaux.

Quelques exemples

Pour bien comprendre ce critère permettant de déterminer des nombres premiers jumeaux, prenons quelques exemples faciles:

Exemple 1: Si l’on prend n=3 alors n(n+2) = 3 \times 5 = 15. Il s’agit de regarder le nombre 4 \times [(3-1) ! +1] + 3 modulo 15 pour savoir si 3 et 5 forment bien une paire de nombres premiers jumeaux:

4  \times [(3-1) ! +1] + 3 = 4 \times ( 2! +1) + 3 = 4 \times (2+1) + 3 = 15 \equiv 0 \mod [15]

Voilà, nous venons de démontrer en un calcul que 3 et 5 sont bien des nombres premiers jumeaux !

• Exemple 2: Si l’on souhaite montrer que 8 et 10 ne sont pas des nombres premiers jumeaux, prenons n=8 et calculons modulo 8 \times 10 = 80:

4  \times [(8-1) ! +1] + 8 =  20172 \equiv 12 \mod [80]

Comme nous n’obtenons pas 0, c’est qu’il ne s’agissait pas d’une paire de nombres premiers jumeaux. En fait, ni 8, ni 10 n’est premier mais je voulais simplement illustrer le fait que ce critère marche vraiment avec tous les nombres !

• Exemple 3: Prenons l’exemple de 9 et 11, où seul 11 est premier. Puisque n=9, alors n(n+2) = 99 et :

4  \times [(9-1) ! +1] + 9 =  161293 \equiv 22 \neq 0 \mod [99]

et on retrouve bien le fait que 9 et 11 ne forment pas une paire de nombres premiers jumeaux.

Exemple 4: Pour finir, redémontrons que 11 et 13 sont bien des nombres premiers jumeaux en prenant n=11. On a

4  \times [(11-1) ! +1] + 11 = 4 \times ( 3628800 +1 ) + 11 = 14 \, 515 \, 215 

Comme 14 \, 515 \, 215 = 11 \times 13 \times 101 \, 505 (je vous invite à vérifier mes calculs par vous-même !), c’est qu’on a bien

4  \times [(11-1) ! +1] + 11 \equiv 0 \mod[11 \times 13]

Encore une fois, le critère marche !

Vous l’avez sans doute compris, cette formule permet de montrer en une fois que deux nombres qui diffèrent de 2 sont simultanément premiers.

La démonstration (1ère mi-temps)

La démonstration de ce critère va reposer sur le théorème de Wilson que nous avons mentionné plus haut. Puisque ce critère est une équivalence, il s’agit de montrer une implication et sa réciproque.

Le sens direct: Soit n>1 tel que n et n+2 sont deux nombres premiers. Il s’agit de montrer que

4 \times [(n-1)! + 1] + n \equiv 0 \mod [n(n+2)]

Comme n+2 est premier, d’après le théorème de Wilson, nous savons que

(n+1)! + 1 \equiv 0 \mod[n+2]

Or, n \equiv -2 \mod[n+2] et n+1 \equiv -1 \mod[n+2] donc n \times (n+1) \equiv (-1) \times (-2) = 2 \mod [n+2]. Ainsi,

(n+1)! + 1 = (n-1)! \times n \times (n+1) + 1 \equiv 2(n-1)! + 1\mod[n+2]

En reprenant alors l’égalité du théorème de Wilson, on a

2 (n-1)! +1 \equiv 0 \mod[n+2]

Si on quitte le (magnifique) langage des congruences un moment, cela signifie qu’il existe un entier k tel que

2(n-1) ! + 1 = k (n+2) \,\, \, \, (\star)

(gardez bien cette relation à l’esprit, nous allons nous en resservir !). Si on regarde cette égalité modulo n, cela donne

2 (n-1)! + 1 \equiv k ( 0 + 2) \mod[n]

Mais comme n est premier, alors (n-1)! \equiv -1 \mod[n] (toujours d’après le théorème de Wilson !) et donc

2 \times (-1) + 1 \equiv 2 k \mod[n]

Nous venons donc de montrer que -1 \equiv 2k \mod[n]. Autrement dit, il existe un entier q tel que 2k = -1 + qn. Si on reprend alors la relation (\star) et qu’on la multiplie par 2, on obtient

4(n-1)! + 2 = 2k (n+2)

En remplaçant à présent 2k par 1 + qn, on a alors

4(n-1)!  + 2 = (-1 + qn)(n+2)

et en distribuant (n+2) sur (-1 + qn), on en déduit que

4(n-1)! + 2 = -(n+2) + qn(n+2)

qui est encore équivalent à

4 \times [ (n-1)! + 1] + n = q n (n+2)

En revenant au langage des congruences, cela veut exactement dire que

\boxed{4 \times [ (n-1)! + 1] + n \equiv 0 \mod[n(n+2)]}.

Je vous laisse souffler un peu avant d’attaquer la suite. Profitez-en pour faire une petite pause pipi qui fait toujours du bien en milieu d’article.

La démonstration (2ème mi-temps)

Le sens réciproque: On suppose à présent que 4 \times [ (n-1)! + 1] + n \equiv 0 \mod[n(n+2)]. Autrement dit, il existe un entier k tel que

4 \times  (n-1)! + 4 + n = k n(n+2) \, \, \, (\star \star)

a) Commençons par montrer que cela implique que n (et donc n+2) est nécessairement impair. Par l’absurde, si on suppose que n est pair, alors n+2 est lui aussi pair. Nous avons ainsi deux nombres pairs consécutifs, donc il y en a un des deux qui est divisible par 4 (et l’autre non).

Si c’est n qui est divisible par 4 alors n=4q avec avec q <n. Ainsi, la relation (\star \star ) implique que

4 (n-1)! + 4 + 4q = k \times 4q \times (n+2)

En la simplifiant par 4, on a alors (n-1)! + 1 + q = k \times q \times (n+2) ce qui entraîne que q divise (n-1)! + 1 + q. Or, comme q divise q (comme d’habitude, chaque article a sa phrase débile, donc la voici pour celui-là) alors q divise (n-1)! +1. Mais, q divise aussi (n-1)! car q<n. On en déduit que q divise (n-1)! + 1 - (n-1)! = 1. Ainsi, q= 1 et donc n=4. Mais cela n’est pas possible car

4 \times ( (4-1) ! + 1) + 4 = 32 \neq 0 \mod [4 \times 6]

ce qui contredit notre hypothèse de départ. Tout cela montre donc que n n’est pas divisible par 4 et que c’est n+2 qui doit l’être. En d’autres termes, n+2 \equiv 0 \mod [4] et donc n \equiv 2 \mod[4]. Sachant cela, si on regarde la relation (\star \star) modulo 4, elle donne

0 \times (n-1)! + 0 + 2 \equiv k \times 2 \times 0 \mod[4]

c’est-à-dire 2 \equiv 0 \mod [4], ce qui est, bien entendu, fichtrement absurde (si je puis me permettre).

b) Maintenant que nous avons prouvé que n est nécessairement impair, reprenons notre hypothèse de départ: 4 \times [ (n-1)! + 1] + n \equiv 0 \mod[n(n+2)].  En particulier, elle implique que

4 \times [ (n-1)! + 1] + n \equiv 0 \mod[n+2]

car si un nombre est divisible par n(n+2), il est a fortiori divisible uniquement par n+2. Nous pouvons réécrire cela sous la forme

2 \times 2  (n-1)! + 4 + n \equiv 0 \mod[n+2]

Or, nous avions vu plus haut dans cette démonstration (voir le sens direct) que 2(n-1)! \equiv (n+1)! \mod[n+2]. Cela, plus le fait que 4+n \equiv 2 \mod [n+2], nous permet de dire que

2 (n+1)! + 2 \equiv 0 \mod [n+2]

et en factorisant, on a

2 [ (n+1)! + 1 ] \equiv 0 \mod [n+2]

C’est à présent que nous allons utiliser le fait que n+2 est impair: il est donc premier avec 2, ce qui veut dire que 2 admet un inverse modulo n+2. Bref, tout cela permet de simplifier par 2 et on obtient

(n+1)! + 1 \equiv 0 \mod [n+2]

D’après le théorème de Wilson, cette relation entraîne alors que n+2 est premier. Pour montrer que n est lui aussi premier, on suit un raisonnement analogue: de l’hypothèse de départ on tire que

4 \times [ (n-1)! + 1] + n \equiv 0 \mod[n]

comme n \equiv 0 \mod [n], cela est équivalent à

4 \times [ (n-1)! + 1]  \equiv 0 \mod[n]

Comme n est impair, il est premier avec 4 et donc on peut simplifier cette relation par 4, ce qui donne

(n-1)! + 1 \equiv 0 \mod [n]

et donc d’après le théorème de Wilson, n est premier. Les nombres n et n+2 sont bien des nombres premiers jumeaux ! CQFD.

Que donne ce critère en pratique ?

A l’instar du théorème de Wilson, en pratique, ce critère est inutilisable: à cause de la présence d’une factorielle dans la relation, le temps de calcul devient beaucoup trop long lorsque n devient très grand. Il faudrait une éternité (au sens propre) pour montrer que les gigantesques nombres découverts en Septembre dernier sont bien des premiers jumeaux en utilisant ce critère !

Malgré tout, on peut utiliser ce critère pour des nombres d’une taille raisonnable. Par exemple, ce test n’a mis « que » 14 secondes sur mon pauvre petit PC bien frêle pour montrer que 18 409 199 et 18 409 201 sont bien des nombres premiers jumeaux (à eux deux, ils forment la 100 000ème paire de nombres premiers jumeaux). Le programme utilisé se trouve ici.

Ce qui a pris 14 secondes pour mon ordi aurait sans doute pris des mois et des mois pour Euler... Vive les ordinateurs !

Ce qui a pris 14 secondes à mon ordi aurait sans doute pris des mois et des mois à Euler… Vive les ordinateurs !

3ème mi-temps: une généralisation

Le critère que nous avons donné peut se généraliser pour déterminer non plus des paires de nombres premiers jumeaux, mais des triplets de nombres premiers, c’est-à-dire trois nombres premiers de la forme n, n+2 et n+6 (on n’a pas mis n+4 car parmi l’un des trois nombres n, n+2 et n+4 l’un au moins est divisible par 3…). Plus précisément, on peut montrer que

Soit n>1 un entier naturel. Les nombres n, n+2 et n+6 sont trois nombres premiers si, et seulement si,

4320 \times ( 4 \times [(n-1)! + 1] + n ) + 361n(n+2) \equiv 0 \mod [n(n+2)(n+6)]

Par exemple, si on prend n=11:

4320 \times ( 4 \times [(11-1)! + 1] + 11 ) + 361 \times 11 \times ( 11 +2) = 62 \, 705 \, 780 \, 423

et comme 62 \, 705 \, 780 \, 423 = 11 \times 13 \times 17 \times 25 \, 794 \, 233 , cela veut dire que

4320 \times ( 4 \times [(11-1)! + 1] + 11 ) + 361 \times 11 \times 13 \equiv 0 \mod [11 \times 13 \times 17]

Nous avons bien redémontré que 11, 13 et 17 forment un triplet de nombres premiers !

Référence:

Congruences for Sets of Primes, P. A. Clement, The American Mathematical Monthly, Vol. 56, No. 1 (Jan., 1949), pp. 23-25

(Dans cet article, la démonstration de la réciproque du critère est vraiment torchée, pour ne pas dire laissée au lecteur en exercice… L’auteur donne aussi à la fin de son article un critère du même type pour que quatre nombres n, n+2, n+6 et n+8 soient tous premiers !)

Publicités
Cet article, publié dans Arithmétique, est tagué , , , , , , . Ajoutez ce permalien à vos favoris.

2 commentaires pour Comment reconnaître deux nombres premiers jumeaux ?

  1. lucien pascal dit :

    Prem’s !
    huhuhu
    Article intéressant et fluide, comme tous ceux de ce blog.
    Merci.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s