Un test de primalité… qui ne sert à rien

Je suis récemment tombé sur l’exercice suivant:

Montrer que si p est un nombre premier >3 alors $p^2-1$ est divisible par 24

L’exercice en lui-même n’est pas très difficile et peut même être posé en Terminale.

Vérifions que la propriété est bien vraie pour les premiers nombres premiers:

si p=5 alors $p^2-1 = 24$
si p=7 alors $p^2-1 =48$
si p=11 alors $p^2-1=120 = 24 \times 5$
…

Il reste à le prouver pour un quelconque nombre premier. Pour ceux qui sèchent, voici plusieurs solutions:

1ère solution

C’est la solution qui m’est venue à l’esprit. On considère un nombre premier p>3. Puisque 24=8×3 et puisque 8 et 3 sont premiers entre eux, il faut et il suffit de montrer que $p^2-1$ est divisible par 8 et par 3.

Or $p^2-1=(p-1)(p+1)$ . Comme p est impair (c’est un nombre premier >3), les nombres (p-1) et (p+1) sont deux nombres pairs consécutifs. Cela signifie que l’un est divisible par 2, et l’autre par 4. Donc le produit (p-1)(p+1) est divisible par 2×4=8.

Ensuite, puisque p>3, p n’est pas divisible par 3, donc soit $p \equiv 1 [3]$ , soit $p \equiv 2 [3]$ :

Si $p \equiv 1 [3]$ , alors $p-1 \equiv 0 [3]$ et donc p-1 est divisible par 3 et il en va de même pour $p^2-1$ .
Si $p \equiv 2 [3]$ alors $p+1 \equiv 3 \equiv 0 [3]$ et donc $p^2-1$ est bien divisible par 3.

2ème solution

Après avoir trouvé cette solution, j’ai cherché sur le net une solution plus élégante. J’ai trouvé celle-ci:

Comme p est un nombre premier >3, il est de la forme $p=6k\pm 1$ (en effet, il ne peut pas être de la forme 6k, 6k+2 ou 6k+3 car il serait respectivement divisible par 6, 2 et 3. Il est donc de la forme 6k+1 ou 6k+ 5 c’est-à-dire de la forme 6k+1 ou 6k-1).

On calcule:

$p^2-1 = (6k \pm 1)^2-1=36k^2 \pm 12k = 12k(3k \pm 1)$

Si k est pair alors $12k$ est divisible par 24, et si k est impair, alors $3k \pm 1$ est pair donc $12(3k \pm 1)$ est divisible par 24.

Un test de primalité intéressant ?

La forme sous laquelle la propriété est énoncée est un peu trompeuse. Cette propriété caractérise-t-elle les nombres premiers ? Ça serait fort étonnant (bye bye le million de dollars). Et d’ailleurs, ce n’est pas le cas, puisque $25^2-1= 624 = 24 \times 26$ . Et 25 n’est pas premier, comme chacun le sait (je l’espère).

La contraposée de l’exercice se lit:

Soit p un entier naturel. Si $p^2-1$ n’est pas divisible par 24, alors p n’est pas premier.

On peut donc en déduire le test de primalité suivant: (disons plutôt un test de non-primalité):

On veut savoir si un nombre p est premier ou non
on calcule $p^2-1$
Si le résultat n’est pas divisible par 24, alors p n’est pas premier à coups sûrs.
Sinon, on ne peut rien dire (voir le cas p=25).

Du point de vue de la complexité de cet algorithme (ah… voilà le moment où je commence à parler de choses auxquelles je n’y connais pas grand chose), c’est très rapide (garder à l’esprit que le nombre p à tester est immense en général… des centaines de chiffres): on effectue juste un produit ( $p^2$ ), puis une division par 24. Autrement dit, quasiment rien.

On disposerait d’un algorithme qui permet d’affirmer instantanément si un nombre n’est pas premier à l’aide de deux ou trois opérations ? On m’aurait menti ? Où est l’arnaque ? Car oui, il y en a une.

Où est l’arnaque ?

Pour voir ce qui ne va pas, intéressons-nous de plus près aux nombres qui, dans le test, rentrent dans la case « 4. On ne peut rien dire ». Plus précisément, nous allons déterminer tous les entiers p tels que $p^2-1$ est divisible par 24.

On peut tester à la main un à un les nombres dans l’ordre, puis voir si la condition est vérifiée. Je me suis remis récemment au C++ (ce qui m’amuse beaucoup d’ailleurs, mais ce n’est pas le sujet…), et j’ai donc écrit un programme qui donne la liste des entiers p inférieurs à un entier n (entré par l’utilisateur) vérifiant la condition: « $p^2-1$ est divisible par 24″.

Voici ce que retourne le programme pour n=300:

Tester les 300 premiers entiers est largement suffisant pour formuler une conjecture… Quoi ? Vous voulez plus ? ARE YOU NOT ENTERTAINED ? Bon, ok, Allons-y:

Regardons parmi les 100 premiers entiers lesquels ne sont pas premiers mais qui pourtant vérifient cette propriété de divisibilité par 24. Il y a: 25, 35, 49, 55, 65, 77, 85, 91, 95.

Y a-t-il un schéma qui se répète dans tout ces nombres ? Pour le savoir, décomposons chacun en produit de facteurs premiers:

25= 5²
35 = 7 x 5
49 = 7²
55 = 5 x 11
65 = 5 x 13
77 = 7 x 11
85 = 5 x 17
91 = 7 x 13
95 = 5 x 19

Vous voyez quelle conjecture on peut formuler ? Si la réponse est non, continuez avec les nombres après 100… vous avez de quoi faire !

L’exercice posé sous forme d’équivalence

Voilà la propriété que nous allons prouver:

Soit p un entier naturel. Les propriétés suivantes sont équivalentes:

(i) $p^2-1$ est divisible par 24.

(ii) p n’est divisible ni par 2, ni par 3.

Prouvons ces dires.

$(ii) \Rightarrow (i)$ : Finalement, le raisonnement est le même exactement que dans la 1ère solution que j’ai donné plus haut. Du fait que p est premier >3, nous n’avions utilisé que le fait que p est impair et que p n’est pas divisible par 3.

$(i) \Rightarrow (ii)$ : Si $p^2-1$ est divisible par 24, alors $p^2-1$ est divisible par 8 et par 3. A fortiori, ce nombre est divisible par 2 et par 3.

Puisque, 2 divise $(p-1)(p+1)$ et comme 2 est premier, on en déduit que 2 divise (p-1) ou (p+1). Autrement dit, (p-1) est pair, ou (p+1) est pair. Dans un cas, comme dans l’autre, cela signifie que p est impair (le successeur ou le prédécesseur d’un nombre pair est un nombre impair. Donc p n’est pas divisible par 2.
Puisque 3 divise $(p-1)(p+1)$ et comme 3 est premier, on en déduit que 3 divise (p-1) ou (p+1). Donc, $p \equiv 1 [3]$ ou $p \equiv -1 [3]$ . Dans tous les cas, p n’est pas divisible par 3.

Pourquoi ce test de primalité ne servait à rien…

Le nombre de nombres composés (c’est-à-dire qui ne sont pas premiers) qui rentrent dans la case 4. de l’algorithme précédent est très grand. Ce sont tous les nombres qui ne sont pas divisibles par 2 et par 3. Autrement dit, ce sont ceux de la forme $5^\alpha 7^\beta 11^\gamma ...$ (il s’agit d’un produit fini bien entendu… ce qui veut dire que la famille $(\alpha, \beta, \gamma, ...)$ est presque nulle.)

Et quant aux nombres pour lesquels on est certain qu’ils sont composés après le test (ceux qui tombent dans la case 3.), ce sont ceux qui sont divisibles par 2 ou par 3. Mais il est bien plus simple de voir qu’un nombre est divisible par 2 en regardant son dernier chiffre, ou de voir qu’il est divisible par 3 en vérifiant que la somme de ses chiffres est divisible par 3.

Un test pour lequel on ne peut rien dire pour un aussi grand nombre de nombres ne sert à rien. Surtout quand, pour ceux pour lesquels on peut dire quelque chose, il y a des moyens plus simples. Mais nous nous sommes bien amusés.

7 commentaires pour Un test de primalité… qui ne sert à rien

The Dude dit :

24 mai 2012 à 17 h 35 min

Bon article !

Merci !

J’aimeJ’aime

Réponse
The Dude dit :

24 mai 2012 à 18 h 06 min

Bon article !

Merci !

J’aimeJ’aime

Réponse
- blogdemaths dit :
  
  24 mai 2012 à 20 h 27 min
  
  Merci à toi !
  
  J’aimeJ’aime
  
  Réponse
Ping : The Dude Minds… › Un curieux test de primalité…
Ping : Revisitons le crible d’Ératosthène | Blogdemaths
Ping : Revisitons le crible d’Ératosthène (1ère partie) | Actumaths
Gonzague de Villemagne dit :

28 novembre 2013 à 22 h 27 min

Bonjour,
La solution à vos questionnements se trouve dans un crible d’Eratosthène à 24 colonnes à construire de la façon suivante :

1ère ligne de 2 à 25 (1)
2ème ligne de 26 à 49 (2)
etc…
Xème ligne de 602 à 625
etc…

a. Vous cochez tous les multiples de 2 : il ne reste plus que les impairs, dont les multiples de 3
b. Vous cochez tous les multiples de 3 : il ne reste plus que des nombres de la forme 6k+/-1, dont
tous les nombres premiers et les multiples de 5, 7, 11, 13, 17, 19, 23, 29, 31 etc…

Il apparaît en fait dans ce tableau à 24 colonnes, que c’est autour des colonnes 6, 12, 18 et 24
que l’on va voir se placer tous ces 6k+/-1.
On y verra ainsi s’aligner ligne après ligne les paires de nombres premiers jumeaux, ainsi, la ligne
(1) se voit de la sorte :

2 3 5 – 7 – – – 11 – 13 – – – 17- 19 – – – 23 – (25)
la ligne (2) verra les nombres premiers et les jumeaux suivants :
– – – 29 – 31 – – – – – 37 – – – 41 – 43 – – -47 – (49) <= 35 a été coché comme 5m

L'on remarque en effet que 25 – 1 = 24 ……..divisible par 24
" " " aussi que 49 – 1 = 48 = 2×24

Et si l'on nomme p et q deux nombres premiers quelconques, on remarquera
que p² – q² = 24m

25² – 1 = 624 = 24×26

En fait, vous l'avez démontré, tout (6k+/-1)² – 1 = 24m.

Ce crible d'Eratosthène à 24 colonnes vous donne l'explication selon laquelle il est nécessaire
que tout p soit supérieur à 3 ( a fortiori, supérieur à 2 ).

Tout l'intérêt de ce tableau des nombres premiers à 24 colonnes est de se poser comme une base de réflexion au sujet de l'existence et de la pérennité des nombres premiers jumeaux dans l'infini des nombres entiers.

Merci de votre article, qui rejoint mes recherches.

A vous lire

J’aimeJ’aime

Réponse

Votre commentaire Annuler la réponse.

Entrez votre commentaire...

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

E-mail (adresse strictement confidentielle)

Nom

Site web

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

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

Annuler

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.