Le paradoxe des anniversaires à l’Euro 2016

Vous avez sans doute déjà entendu parlé du paradoxe des anniversaires qui dit que dans un groupe de 23 personnes, il y a 50% de chances pour que deux d’entre elles soient nées le même jour de l’année (mais pas forcément la même année). Ça tombe bien, 23 c’est aussi le nombre de joueurs qui composent chaque équipe lors de l’Euro 2016 !

Dimitri Payet (à gauche) et N'Golo Kante (à droite) sont tous les deux nés le 29 Mars.

Dimitri Payet (à gauche) et N’Golo Kanté (à droite) sont tous les deux nés le 29 Mars.

Démonstration du paradoxe

Avant de parler des joueurs de l’Euro, j’aimerais tout de même qu’on revienne un peu sur le paradoxe des anniversaires et qu’on le démontre car, après tout, il n’a rien du tout d’intuitif.

Commençons par traduire le paradoxe de manière un peu plus mathématique: dire que dans un groupe de 23 personnes au moins deux sont nées le même jour revient à dire que si on choisit 23 nombres au hasard entre 1 et 365, au moins deux sont égaux. Précision: les nombres seront choisis de manière équiprobable entre 1 et 365 (même si, en pratique, ce n’est pas tout à fait exact qu’il y ait autant de gens nés chaque jour de l’année, mais nous en reparlerons).

Quant à la valeur 23, elle est a priori arbitraire, donc au lieu de choisir 23 nombres au hasard entre 1 et 365, nous allons en choisir k et nous allons calculer la probabilité de l’événement « Au moins deux des k nombres choisis sont égaux ». On va même plutôt calculer la probabilité de l’événement contraire — à savoir « Tous les nombres choisis sont distincts » — car cela sera plus facile. Plus précisément:

Propriété: Si on choisit k nombres a_1, a_2, \cdots, a_k au hasard entre 1 et 365, la probabilité qu’ils soient tous distincts est:

\dfrac{365\times 364 \times 363 \times \cdots \times (365 -k +1)}{365^k}

Pour démontrer cette propriété, il faut commencer par déterminer l’univers associé à cette expérience aléatoire. Autrement dit, il faut dire combien il y a de façons de choisir k nombres au hasard entre 1 et 365. Pour cela, remarquons que choisir k nombres revient à choisir une liste (a_1, a_2, \cdots, a_k).  Pour le premier nombre a_1, il y a 365 possibilités; pour le deuxième nombre a_2, il y a aussi 365 possibilités; et ainsi de suite. Au total, cela donne 365 \times 365 \times \cdots \times 365 = 365^k listes possibles.

A présent, dénombrons les listes pour lesquels tous les nombres a_i sont distincts:

  • On commence par choisir un premier nombre a_1: puisque c’est le premier nombre à être choisi, il peut prendre n’importe quelle valeur, ce qui donne 365 possibilités.
  • Choisissons ensuite un deuxième nombre a_2: comme il doit être différent du premier nombre déjà choisi, il y a 364 possibilités de le choisir.
  • Puis, on choisit un troisième nombre a_3: comme il doit être différent de a_1 et a_2, il y a 363 possibilités seulement pour ce nombre.
  • On procède ainsi jusqu’au dernier nombre a_k à choisir. Ce dernier devant être différent des k-1 nombres déjà choisis précédemment, cela donnera 365 – (k-1) = 365 – k +1 possibilités.

En résumé, il y a donc 365\times 364 \times 363 \times \cdots \times (365 -k +1) listes de k nombres qui sont tous distincts. Pour obtenir la probabilité voulue, il faut diviser par le nombre total de listes possibles, ce qui donne une probabilité de

\dfrac{365\times 364 \times 363 \times \cdots \times (365 -k +1)}{365^k}

En passant à l’événement contraire, on a donc:

Propriété: Si on choisit k nombres a_1, a_2, \cdots, a_k au hasard entre 1 et 365, la probabilité p_k qu’au moins deux soient égaux est:

p_k = 1- \dfrac{365\times 364 \times 363 \times \cdots \times (365 -k +1)}{365^k}

En calculant cette probabilité pour différentes valeurs de k, on obtient le graphe suivant:

Anniversaires_Euro_Graphe_des_probabilitesEn particulier, si on prend la valeur k=23, on trouve une probabilité égale à 0,507. Ainsi, dans un groupe de 23 personnes, il y a un tout petit peu plus de 50% de chances que deux d’entre elles soient nées le même jour. Voilà donc qui démontre le paradoxe des anniversaires ! On pourrait alors s’arrêter là, mais tout n’est pas si simple dans la vie…

Non uniformité des naissances

Comme nous l’avons dit, dans la réalité il n’est pas vrai qu’une personne ait la même probabilité de naître chaque jour de l’année. Il y a des jours avec plus de naissances et d’autres avec moins. Par exemple, en France le nombre de naissances par jour est plus élevé au mois de Juillet qu’au mois de Novembre (à croire que les gens font plus l’amour en Octobre qu’en Février !). Est-ce que pour autant notre probabilité de 0,507 est très éloignée de la réalité ? Est-ce que le paradoxe des anniversaires est encore valable en pratique ?

Dans un article intitulé The Uniformity Assumption in the Birthday Problem (voir lien en fin d’article), l’auteur Geoffrey C. Berresford a pris en compte le fait que les naissances ne sont pas exactement uniformément réparties sur une année et a estimé, en se basant sur les statistiques des naissances de l’État de New York, que la probabilité que deux personnes soient nées le même jour dans un groupe de 23 personnes est de 0,5101. Nous pouvons donc dire qu’en pratique, même avec le fait que les naissances ne sont pas tout à fait uniformes, le paradoxe des anniversaires tient toujours !

Anniversaires_Euro_graphe_des_naissances_Etat_de_New_York_1977

Fréquences des naissances par jour de l’année relevées dans l’État de New-York en 1977 (image extraite de l’article de Berresford)

On considérera dans la suite que la probabilité que deux personnes soient nées le même jour dans un groupe de 23 personnes choisies au hasard est de 51%.

Les joueurs de l’Euro 2016

Lors de l’Euro 2016, 24 équipes nationales sont en compétition, chacune étant formée d’un groupe de 23 joueurs. Et si dans chacune d’entre elle on regardait si au moins deux joueurs sont nés le même jour ? C’est ce que j’ai fait à partir des informations données sur cette page Wikipédia qui recense les joueurs de chaque équipe. Voici ce qu’il en ressort:

Pays Joueurs nés le même jour
Albanie Orges Shehi et Arlind Ajeti (25 Septembre)
Allemagne Aucun
Angleterre Kyle Walker et John Stones (25 Mai)
Autriche Aucun
Belgique Kevin De Bruyne et Jason Denayer (28 Juin)
Croatie Mateo Kovačić et Marko Pjaca (6 Mai)
Espagne Koke et David Silva (8 Janvier)
France Dimitri Payet et N’golo Kanté (29 Mars)
Anthony Martial et André-Pierre Gignac (5 Décembre)
Hongrie Barnabás Bese et Péter Gulácsi (6 Mai)
Irlande du Nord Michael McGovern et Shane Ferguson (12 Juillet)
Islande Ragnar Sigurðsson et Ögmundur Kristinsson (19 Juin)
Italie Aucun
Pays de Galles James Chester et Joe Ledley (23 Janvier)
Ashley Williams et James Collins (23 Aout)
Pologne Wojciech Szczęsny et Łukasz Fabiański (18 Avril)
Portugal Anthony Lopes et Eliseu (1er Octobre)
José Fonte, Raphaël Guerreiro et Éder (22 Décembre)
République d’Irlande Aiden McGeady et Stephen Quinn (4 Avril)
République Tchèque Tomáš Vaclík et Marek Suchý (29 Mars)
Roumanie Aucun
Russie Roman Shishkin et Denis Glushakov (27 Janvier)
Aleksei Berezutski et Vasili Berezutski (20 Juin… Ce sont des jumeaux !)
Slovaquie Ján Mucha et Ondrej Duda (5 Décembre)
Suède Robin Olsen et Patrik Carlgren (8 Janvier)
Andreas Isaksson et Zlatan Ibrahimović (3 Octobre. Désolé M. Ibrahimović, mais vous n’avez rien de spécial !)
Suisse Aucun
Turquie Semih Kaya et Yunus Malli (24 Février)
Hakan Balta et Ozan Tufan (23 Mars)
Ukraine Aucun

Comme vous pouvez le constater, il y a 18 équipes sur 24 qui possèdent au moins deux joueurs nés le même jour, ce qui représente 75% des équipes. Le paradoxe des anniversaires prédisait, quant à lui, qu’environ 50% des équipes auraient au moins deux joueurs nés le même jour. Y a pas quelque chose de louche ? Le nombre d’équipes avec des joueurs nés le même jour n’est-il pas un peu élevé ? Ou bien, cette valeur de 75% est-elle normale et n’est que le fruit du hasard ?

« Tu peux pas test »

Pour le savoir, nous allons faire ce qu’on appelle un test d’hypothèse.

1ère étape: Pour faire un test d’hypothèse, on commence par faire une hypothèse (j’écris vraiment des trucs très cons sur ce blog…) dont on veut tester la validité. Cette hypothèse que l’on veut étudier s’appelle l’hypothèse nulle et dans notre cas nous ferons l’hypothèse nulle suivante:

Dans un groupe de 23 joueurs de l’Euro, la probabilité p que deux soient nés le même jour vaut p = 0,51.

Autrement dit, nous allons tester si les joueurs de l’Euro ont des naissances qui ressemblent à celles du reste de la population. Dans un test d’hypothèse, on se donne aussi une hypothèse alternative. Ici, ce sera:

La probabilité précédente est telle que p>0,51.

2ème étape: On se donne, de manière arbitraire, une certaine probabilité de se tromper lors de notre test, qu’on appelle seuil. Le choix le plus courant est un seuil de 5%: cela signifie que si on arrive à la conclusion que l’hypothèse nulle n’est pas valable, cela sera avec une probabilité de 5% de se tromper (et donc 95% de dire vrai).

3ème étape: On reprend les résultats de notre échantillon de 24 équipes de l’Euro qui disait que 18 équipes avaient au moins deux joueurs nés le même jour et nous allons déterminer quelle était la probabilité d’avoir au moins 18 équipes qui ont au moins deux joueurs nés le même jour, dans le cas où on considère que l’hypothèse nulle est vraie. Cette probabilité qu’on souhaite calculer est la fameuse valeur p ou p-value en Anglais.

Pour calculer cette probabilité, on considérera en première approximation que lorsque nous avons étudié les équipes de l’Euro, nous avons fait 24 tirages indépendants de groupes de 23 personnes, chaque tirage ayant une probabilité p=0,51 de donner un groupe où deux personnes au moins sont nées le même jour. Vous l’avez compris, il s’agit ici d’une loi binomiale de paramètres n=24 et p=0,51. Si on note X le nombre d’équipes qui ont au moins deux joueurs nés le même jour, le calcul de la valeur p revient donc à calculer P(X \geqslant 18) (en rouge sur le schéma suivant).Anniversaires_Euro_loi_binomialeCe qui est bien avec la loi binomiale, c’est qu’on sait parfaitement la calculer. Avec une calculatrice, on trouve P(X \geqslant 18) \simeq 0,015.

4ème étape: Pour finir un test d’hypothèse, on confronte la valeur p avec notre seuil:

  • si la valeur p est plus grande que le seuil, alors on ne peut pas rejeter notre hypothèse nulle;
  • si elle est plus petite, c’est que notre hypothèse nulle est fausse et on peut donc la rejeter.

Ici, il est clair que la valeur p de 0,015 est plus petite que notre seuil de 5\% = 0,05. Autrement dit, il y avait moins de 5% de chances d’avoir au moins 18 équipes qui possèdent au moins deux joueurs nés le même jour (ça fait beaucoup d’ « au moins » !). On peut donc affirmer, avec 5% de chances de se tromper, que la probabilité que, dans un groupe de 23 joueurs de l’Euro, deux soient nés le même jour est strictement plus grande que p=0,51. Il y a donc bien quelque chose qui cloche dans les dates de naissance des joueurs de l’Euro !

Enquête en profondeur

Nous venons de voir que la proportion de 75% d’équipes possédant deux joueurs nés le même jour est anormale et elle suppose que la répartition des naissances des joueurs de l’Euro n’est pas conforme à celle de l’ensemble de la population. Pour comprendre pourquoi, il faut se plonger plus précisément dans les statistiques des dates de naissance des 552 joueurs qui participent à cet Euro. Je m’y suis collé et les voici représentées sous forme de graphique:

Anniversaires_Euro_naissances_par_jourJe précise que les jours de l’année vont jusque 366 car il y a un joueur à cet Euro qui est né le 29 Février (il s’agit de Benedikt Höwedes de l’équipe d’Allemagne). On voit qu’il y a quand même plus de naissances dans la première partie de l’année que dans la deuxième. Pour préciser cela, regroupons les dates de naissance par mois de naissance:

Anniversaires_Euro_naissances_par_moisOn voit maintenant clairement que les cinq premiers mois de l’année sont quand même prédominants (même le mois de Février, qui compte pourtant le moins de jours dans l’année, est le 3ème mois avec le plus de naissances). Si on compare avec les mois de naissance dans la population globale en Europe (voir schéma ci-dessous), on remarque qu’il y a une vraie différence.

Anniversaires_Euro_naissances_par_mois_population_globale source: Wikipédia

Tout est relatif

Pourquoi donc la répartition des naissances chez les joueurs de l’Euro n’est pas la même que dans le reste de la population ? Cette question possède une réponse dans un phénomène appelé Relative age effect (l’effet de l’âge relatif en Français). Ce phénomène dit que les personnes nées en début d’année ont plus de chance de devenir footballeurs professionnels que celles nées dans la 2ème partie de l’année. Il est dû au fait que les catégories de jeunes joueurs sont déterminées par l’âge (moins de 15 ans, moins de 16 ans, moins de 17 ans…) et qu’il y a une date-limite qui est le 1er Janvier pour chaque catégorie. Ainsi, dans une même catégorie d’âge, un jeune né en Janvier aura un écart de développement physique et de maturité plus important qu’un jeune né en Novembre ou Décembre (puisqu’ils auront entre 11 mois et un an d’écart !) et il aura donc plus de chance d’être repéré par des recruteurs. Si vous doutez encore de ce phénomène, consultez l’effectif actuel de l’équipe de France des moins de 17 ans et vous remarquerez que tous, sauf deux, sont nés dans les 6 premiers mois de l’année !

L’effet de l’âge relatif est très marqué pour les footballeurs des jeunes catégories d’âge mais tend à s’estomper dans les catégories plus âgées, sans toutefois jamais disparaître complètement. L’effet de l’âge relatif ne concerne d’ailleurs pas que le Football puisqu’on le retrouve dans tout un tas de sport dont le Hockey ou encore le Baseball. Là encore, c’est la présence d’une date-limite qui crée ce phénomène.

Pour revenir au paradoxe des anniversaires, puisque les naissances des joueurs de l’Euro sont plus concentrées sur certains mois, il y avait donc plus de chances que plusieurs d’entre eux soient nés le même jour.

Sur ce, je vous laisse, je retourne regarder les matchs…

Références:

Publié dans Dénombrement, Probabilités | Tagué , , , , , , | 12 commentaires

Le Roi des Catalans (1ère partie)

Un Roi situé sur la case tout en bas à gauche d’un échiquier souhaite (pour des raisons personnelles que nous ne détaillerons pas ici) se rendre sur la case située tout en haut à droite.Roi_des_Catalans_figure_initialeContrairement au jeu d’Échecs où il peut se déplacer d’une case dans toutes les directions, notre Roi ne pourra ici se déplacer que d’une case vers la droite ou d’une case vers le haut à chaque fois.Roi_des_Catalans_deplacements_possibles_du_RoiEn plus de ça, notre Roi ne peut pas aller dans la partie haute de l’échiquier (trop fainéant), c’est-à-dire qu’il devra rester toujours en-dessous ou sur la diagonale principale:Roi_des_Catalans_figure_initiale_contrainte_de_la_diagonale(Remarquez au passage la belle illusion d’optique créée par cette figure…)

Voici donc la question qui va nous intéresser: de combien de façons un Roi sur un échiquier partant de la case la plus en bas à gauche peut-il rejoindre la case la plus en haut à droite en se déplaçant à chaque étape uniquement soit d’une case vers la droite, soit d’une case vers le haut, sans jamais aller au-delà de la diagonale principale ?

Nous verrons que ce problème d’apparence anecdotique renferme en fait une des suites de nombres les plus intéressantes en mathématiques.

Généralisation

En bons mathématiciens que nous sommes, nous voyons qu’il n’y a aucune raison de se restreindre à un échiquier de 8 cases par 8 cases. D’une part, parce qu’il est plus facile de comprendre et de résoudre ce problème si les échiquiers sont plus petits (on peut considérer des échiquiers de 1 par 1, ou de 2 par 2 pour commencer) et d’autre part, parce que vous n’êtes pas curieux de savoir ce qui se passe pour un échiquier de 9, 10 ou même 30 000 cases de côté ? Moi, si…

Si on reformule notre problème de façon plus générale, cela donne: si n est un entier naturel, et si on place le Roi sur un échiquier de (n +1) \times (n +1) cases, de combien de façons peut-il aller de la case (0,0) à la case (n,n) sans jamais aller au-dessus de la diagonale principale ?

Nous appellerons C_n ce nombre de chemins et notre but va être de déterminer le nombre C_7 (qui correspond au nombre de chemins sur un échiquier standard de 8 par 8).

Quelques cas particuliers

Comme on l’a dit, pour comprendre cette suite (C_n) le mieux est encore de regarder comment elle se comporte pour de petites valeurs de n. Je vous propose donc de commencer par voir ce qui se passe pour n=0. Car, non, il n’y a rien de honteux à commencer à n=0. On a tous un ami, ou un proche qui a commencé à n=0 un jour dans sa vie.Roi_des_Catalans_n_egale_0Nous voyons donc qu’il n’y a qu’un seul chemin, celui qui consiste à ne pas se déplacer puisqu’on est déjà sur la case d’arrivée dès le départ ! Ainsi, C_0=1. Passons au cas n=1, qui correspond à un échiquier de 2 par 2:Roi_des_Catalans_n_egale_1_videEt nous voyons facilement qu’il n’y a qu’un seul chemin possible:Roi_des_Catalans_n_egale_1_avec_parcoursNous venons de démontrer, non sans fierté, que C_1 = 1. Et pour n=2 alors ? Eh bien sortons un échiquier de 3 cases sur 3 cases et comptons:Roi_des_Catalans_n_egale_2On voit alors qu’il n’y a que deux chemins possibles donc C_2 = 2.

La marche de l’empereur

Vous pouvez vous amuser à compter tous les chemins pour n=3, 4, 5, mais à partir de n=6 cela commence à devenir fastidieux. Alors imaginez pour n=7… Donc, plutôt que de compter tous les chemins, nous allons plutôt essayer de trouver une relation de récurrence vérifiée par la suite (C_n) afin de laisser le soin à un ordinateur de faire le calcul à notre place (y a pas que le Roi qui est fainéant !)

Supposons que nous connaissions déjà C_0, C_1, C_2, …, C_n et essayons de voir comment en déduire C_{n+1}. Il nous faut pour cela nous placer sur un échiquier à (n+2) \times (n+2) cases:Roi_des_Catalans_echiquier_C_n_plus_1_videTout d’abord, si un chemin va de (0,0) à (n+1, n+1), il passera au moins une fois par la diagonale principale autrement qu’en (0,0) (au pire, en (n+1,n+1)). Considérons un chemin quelconque, et notons k>0 le plus petit entier strictement positif tel que ce chemin passe par la case caca… pardon, (k,k):Roi_des_Catalans_echiquier_C_n_plus_1_CACALOLAinsi, avant la case (k,k) aucune case de la diagonale n’est visitée (hormis (0,0) bien sûr). Après cette case, une ou plusieurs cases de la diagonale pourront être traversées. Notre but va être de dénombrer combien de tels chemins passant par (k,k) sont possibles. Mais avant cela, pour bien comprendre la situation, voici un exemple de tel chemin:Roi_des_Catalans_echiquier_C_n_plus_1_exemple_de_cheminCe chemin peut être décomposé en deux morceaux: un chemin allant de (0,0) à (k,k) (en bleu sur le schéma ci-dessous) et un chemin allant de (k,k) à (n+1,+1) (en vert sur le schéma):Roi_des_Catalans_echiquier_C_n_plus_1_exemple_avec_chemins_bleu_et_vertPour obtenir le nombre total de chemins passant pour la première fois sur la diagonale en (k,k), il suffira de faire le produit du nombre de chemins bleus possibles par le nombre de chemins verts possibles.

Dénombrement des chemins bleus

Pour dénombrer tous les chemins allant de (0,0) à (k,k) qui ne passent par aucune case de la diagonale principale, il faut d’abord remarquer deux choses:

  1. Puisque le Roi ne se déplace que vers la droite ou vers le haut, alors le tout premier déplacement qu’il effectue au départ est nécessairement vers la droite, donc vers la case (1,0).
  2. Pour la même raison, lorsque le Roi arrive à la case (k,k), c’est forcément en provenance de la case située juste en dessous, c’est-à-dire de la case (k,k-1).

Roi_des_Catalans_echiquier_C_n_plus_1_chemins_bleus_cases_forceesPuisque ces deux déplacements sont forcés, pour déterminer le nombre de chemins bleus il suffit de déterminer tous les chemins allant de (1,0) à (k,k-1) qui ne passent pas par la diagonale principale.Roi_des_Catalans_echiquier_C_n_plus_1_chemins_bleus_sous_echiquierCela revient donc à déterminer tous les chemins ne dépassant pas la diagonale principale d’un sous-échiquier à k \times k cases. Par définition, il y a donc C_{k-1} chemins bleus.

Dénombrement des chemins verts

Le dénombrement des chemins verts est beaucoup plus immédiat. En effet, un chemin vert est un chemin allant de (k,k) à (n+1,n+1) qui ne va pas au-delà de la diagonale (mais qui peut tout à fait passer sur celle-ci).Roi_des_Catalans_echiquier_C_n_plus_1_chemins_verts_sous_echiquierIl y a donc autant de chemins verts que de chemins ne dépassant pas la diagonale dans un échiquier de ((n+1)-k+1) \times ((n+1)-k+1) cases, c’est-à-dire C_{n-k+1} chemins, par définition.

Dénombrement final

D’après ce que nous venons de voir, il y a donc C_{k-1} \times C_{n-k+1} chemins allant de (0,0) vers (n+1,n+1) ne passant jamais au-dessus de la diagonale et passant pour la première fois sur celle-ci en (k,k).Roi_des_Catalans_echiquier_C_n_plus_1_denombrement_finalAinsi, si on prend un chemin quelconque, alors:

  • Soit la première case de la diagonale par laquelle il passe est (1,1) (c’est-à-dire k=1), ce qui donne C_{1-1} \times C_{n-1+1} = C_0 \times C_{n} possibilités;
  • Soit la première case de la diagonale par laquelle il passe est (2,2), ce qui donne C_1 \times C_{n-1} possibilités;
  • Soit la première case de la diagonale par laquelle il passe est (3,3), ce qui donne C_2 \times C_{n-2} possibilités;
  • etc.
  • Soit la première case de la diagonale par laquelle il passe est (n+1,n+1), ce qui donne C_n \times C_{0} possibilités.

Puisque tous ces cas sont disjoints, le nombre total de chemins est donc:

C_{n+1}  = C_0 \times C_n + C_1 \times C_{n-1} + C_2 \times C_{n-2} + \cdots + C_n \times C_0

ce qu’on peut réécrire sous la forme plus compacte et plus jolie suivante:

\boxed{ C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i} }

Le calcul pour un échiquier standard

Par exemple, si on souhaite calculer C_3, on écrira:

C_3 = C_0 \times C_2 + C_1 \times C_1 + C_2 \times C_0

Comme nous avions vu que C_0 = 1, C_1 = 1 et C_2 = 2, alors:

C_3 = 1 \times 2 + 1 \times 1 + 2 \times 1 = 5

De la même façon, on peut facilement calculer le nombre chemins sur un échiquier de 8 par 8, mais comme les ordinateurs font ça beaucoup mieux que nous, il est préférable d’écrire un petit programme (non optimal), qui nous dit que C_7 = 429. Et voilà, nous avons la réponse à notre question de départ !

Pour le plaisir, on peut s’amuser à calculer les valeurs suivantes de cette suite:

n C_n
0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
11 58786
12 208012
13 742900
14 2674440

Enquête de satisfaction

Nous avons donc réussi à trouver une formule de récurrence pour la suite (C_n) mais, franchement, pensez-vous vraiment que nous allons nous satisfaire de cela ? Nous valons mieux que ça, voyons… visons plus haut ! Pourquoi ne pas essayer de trouver une formule explicite de cette suite ? C’est ce que nous tenterons de faire dans la deuxième partie de cet article… ce qui nous donnera l’occasion de faire encore plus de dénombrement !

Note:

Les nombres C_n que nous avons étudiés dans cet article s’appellent les nombres de Catalan, du mathématicien Eugènes Charles Catalan, qui, comme son nom ne l’indique pas, était un mathématicien franco-belge.

Publié dans Dénombrement, Nombres | Tagué , , , , , , , | 5 commentaires

Séries géométriques, géométriquement !

Prenez un nombre x (disons positif), et formez la somme de toutes les puissances de x:

x^0 + x^1 + x^2 + x^3 + \cdots + x^n + \cdots

Vous calculez alors ce qu’on appelle la somme de la série géométrique de raison x. Par exemple, la somme de la série géométrique de raison x=\frac12, est:

1 + \dfrac12 + \dfrac14 + \dfrac18 + \cdots + \dfrac{1}{2^n} + \cdots

Les séries géométriques sont connues depuis très longtemps et apparaissent un peu partout en mathématiques (par exemple, pour montrer que tôt ou tard vous gagnerez au Loto !). En fait, on les connaît tellement bien qu’on sait même calculer leur somme. En effet, on peut montrer que pour 0 \leqslant x <1:

\boxed{ 1+x+x^2 + \cdots + x^n + \cdots = \dfrac{1}{1-x} }

(En fait, cette formule est valable même pour -1<x<1, mais nous ne nous occuperons pas des x négatifs dans cet article. Et si x \geqslant 1 ? la somme tend grossièrement vers +\infty, donc nous ne nous en occuperons pas non plus…)

Tout ça est bien beau mais comment prouver cette formule pour les séries géométriques ? Eh bien, grâce à de la géométrie ! (ce qui est quand même la moindre des choses, vu leur nom…)

Le cas 1/2

Commençons par un cas particulier, celui de la somme de la série géométrique de raison x=\frac12. Si on en croit la formule précédente, nous devrions trouver que:

1 + \dfrac12 + \dfrac14 + \dfrac{1}{8}\cdots = \dfrac{1}{1-\frac12}=2

Voyons voir comment montrer géométriquement cette égalité. Pour cela, commençons par considérer un carré de côté 1. Ce carré a donc pour aire totale 1:series_geometriques_de_raison_un_demi-carre_1Coupons ce carré en deux:
series_geometriques_de_raison_un_demi-carre_2L’aire en rouge vaut donc \frac12. Coupons à nouveau en deux la partie restante en blanc:series_geometriques_de_raison_un_demi-carre_3Comme l’aire en blanc valait \frac12 à l’étape précédente, quand on la coupe en deux, elle devient \frac12 \times \frac12 =\frac14. On recommence ainsi de suite, et on coupe en deux à chaque fois la partie restante:series_geometriques_de_raison_un_demi-carre_4Si on découpe indéfiniment le carré, nous voyons que l’aire totale en rouge sera de \frac12 + \frac14 + \frac18 + \cdots Comme cette aire en rouge va remplir tout le carré (qui a pour aire 1, rappelons-le), on peut affirmer que:

\dfrac12 + \dfrac14 + \dfrac18 + \cdots = 1

et donc :

1 + \dfrac12 + \dfrac14 + \dfrac18 + \cdots  = 2

Joli, n’est-ce pas ? Mais inutile… car cette démonstration, aussi élégante soit-elle, ne se généralise pas très bien au cas d’une série géométrique de raison x quelconque (essayez par exemple de couper le carré en 3 à chaque étape, vous verrez que vous ne remplirez jamais tout le carré…). Certes, il existe des découpages du carré qui permettent de prouver la formule dans le cas général (voir figure ci-dessous) mais, hormis pour x=\frac14, je ne les trouve pas géométriquement très parlants (si tant est que cette phrase ait un sens… et si tant ait que vous partagiez mon opinion !).

series_geometriques_Proof_without_words

Source: https://www.maa.org/sites/default/files/Ajose61740393.pdf
Je ne sais pas pour vous, mais la figure de droite ne me parle pas du tout…

Je vous ai quand même promis une preuve géométrique en début d’article (oui, je vends du rêve !), donc il va falloir trouver autre chose. On va changer de stratégie: au lieu d’utiliser la notion d’aire, nous allons plutôt utiliser la notion de distance.

Une figure étrange…

Voici la figure que nous allons utiliser pour déterminer la somme de la série géométrique de raison x:series_geometrique_demonstration_par_les_distances_fig_1_figure_de_base

Si vous n’êtes pas convaincu que cette figure permettra bel et bien de calculer la somme 1+x+x^2 + \cdots, attendez de voir la suite…

Expliquons tout de même comment construire cette figure: tracez un segment horizontal [OA] de longueur 1, puis, à partir de A, construisez un segment vertical [AB] de longueur x (où x représente la raison de notre série géométrique). Vous obtenez donc un triangle OAB rectangle en A. Ensuite, à partir de A, prolongez le segment [OA] en un segment [AC] de longueur 1. Et à partir de C, tracez un segment vertical [CD] de longueur 1 lui aussi:series_geometrique_demonstration_par_les_distances_fig_2_explication_de_la_construction

A partir de là, prolongez les demi-droites [OB) et [AD). Elles se coupent en un point P. Le point N est défini alors comme le pied de la perpendiculaire à (OA) passant par P:series_geometrique_demonstration_par_les_distances_fig_3_explication_de_la_construction_suite

(Remarque: vous comprenez sans doute à ce moment-là que les demi-droites [OB) et [AD) ne se coupent en un point P que si x<1; je vous laisse méditer là-dessus pour le moment…)

Il se trouve alors que le triangle APN est isocèle. Si vous voulez vous en convaincre, un petit coup de théorème de Thalès donne  \frac{AC}{AN}= \frac{CD}{PN} c’est-à-dire \frac{1}{AN}=\frac{1}{PN} donc AN=PN.

Quel est l’intérêt de cette figure ?

Si on était dans un repère, on dirait que la droite (OP) a pour coefficient directeur x et que la droite (AP) a pour coefficient directeur 1.

series_geometrique_demonstration_par_les_distances_fig_4_intepretation_coefficient_directeur

Vous vous souvenez peut-être qu’au collège, votre prof vous a dit que pour trouver graphiquement le coefficient directeur d’une droite, il faut partir d’un point de cette droite, se décaler d’une unité horizontalement vers la droite et alors la distance (algébrique, c’est-à-dire positive ou négative) qu’il faut parcourir verticalement pour retomber sur la droite est le coefficient directeur.

On en déduit la propriété suivante:

Propriété 1: Si on part d’un point de la droite (OP) et qu’on se déplace horizontalement d’une distance y, alors il faut se déplacer verticalement d’une distance y \times x pour revenir sur cette droite.series_geometrique_demonstration_par_les_distances_fig_5_propriete_1

Dans un repère, cette propriété peut se comprendre de la façon suivante: puisque la droite (OP) a pour coefficient directeur x, un vecteur directeur de cette droite est \begin{pmatrix} 1 \\ x\\  \end{pmatrix} donc pour tout y non nul , le vecteur y \times \begin{pmatrix} 1 \\ x\\  \end{pmatrix} = \begin{pmatrix} y \\ y \times x\\  \end{pmatrix} est aussi un vecteur directeur de cette droite.

On a une propriété équivalente pour l’autre droite:

Propriété 2: Si on part d’un point de la droite (AP) et qu’on se déplace verticalement d’une distance y, alors il faut se déplacer horizontalement d’une distance y pour revenir sur cette droite.series_geometrique_demonstration_par_les_distances_fig_6_propriete_2

Voilà, avec tout cela, nous sommes prêts à démontrer la formule sur la somme de la série géométrique de raison x.

La démonstration tant attendue…

Pour démontrer la formule à partir de cette figure, nous allons faire une petite balade… nous allons partir du point O pour arriver au point P de la façon suivante:

Étape 1: On part de O et on se déplace horizontalement de 1 unité.series_geometrique_demonstration_par_les_distances_fig_7_deplacement_etape1

Étape 2: On se déplace ensuite verticalement jusqu’à revenir sur la droite (OP). Puisqu’on était parti de cette droite à l’étape précédente et qu’on s’était déplacé de 1 unité, la propriété 1 précédente nous dit qu’il faut se déplacer de 1 \times x = x unités pour retomber sur la droite.series_geometrique_demonstration_par_les_distances_fig_8_deplacement_etape2

Etape 3: On se déplace ensuite horizontalement jusqu’à atteindre la droite (AP). Mais puisqu’à l’étape précédente nous étions partis de cette même droite (AP) et que nous nous étions déplacés de x unités verticalement, alors la propriété 2 nous dit que pour rejoindre (AP), il faut se déplacer de x unités horizontalement également.series_geometrique_demonstration_par_les_distances_fig_9_deplacement_etape3

Etape 4: On se déplace verticalement jusqu’à rejoindre la droite (OP). Puisqu’à l’étape précédente on s’était déplacé horizontalement de x unités horizontalement, la propriété 1 nous dit que pour rejoindre (OP), il faut se déplacer de x\times x = x^2 unités verticalement.series_geometrique_demonstration_par_les_distances_fig_10_deplacement_etape4

Etape 5: On se déplace horizontalement de façon à rejoindre la droite (AP). Comme à l’étape précédente on s’était déplacé de x^2 verticalement en partant de (AP), la propriété 2 nous dit qu’il faut aussi se déplacer horizontalement de x^2 pour rejoindre cette droite:series_geometrique_demonstration_par_les_distances_fig_11_deplacement_etape5

Bon, inutile de faire plus d’étapes, je pense que vous avez compris le principe. Voici la belle figure obtenue lorsqu’on répète indéfiniment ces déplacements:series_geometrique_demonstration_par_les_distances_fig_12_figure_finale

Intéressons-nous à présent à la distance totale parcourue horizontalement: lorsqu’on s’est déplacé de O à P, la distance qu’on a balayée horizontalement est

1+x+x^2+x^3 + \cdots + x^n + \cdots

Il s’agit de la somme des distances de tous les segments en rouge sur la figure précédente. Mais, le déplacement horizontal total effectué quand on va de O à P est aussi égal à la longueur du segment [ON], d’où:

1+x+x^2+x^3 + \cdots + x^n + \cdots = ON

Il nous faut donc déterminer la distance ON. Pour cela, reprenons notre configuration de départ:series_geometrique_demonstration_par_les_distances_fig_1_figure_de_baseD’après le théorème de Thalès, on a:

\dfrac{OA}{ON} = \dfrac{AB}{PN} \Rightarrow \dfrac{1}{ON} = \dfrac{x}{PN}

mais comme PN = AN = ON-OA= ON-1, on en déduit que:

\dfrac{1}{ON} = \dfrac{x}{ON-1}

donc: ON \times x = ON-1, c’est-à-dire 1 = ON (1-x) d’où:

\boxed{ON = \dfrac{1}{1-x}}

ce qui prouve bien que 1+x+x^2+x^3 + \cdots + x^n + \cdots = \dfrac{1}{1-x}.

Source:

Cette image dont je ne sais même pas de quel bouquin elle est extraite ! N’hésitez pas à me le dire si vous le savez…

(Finalement, la référence a été trouvée et elle a été donnée par « none » dans les commentaires)

Ajout:

Il y a quand même une chose que l’on a affirmée dans cette démonstration et qui mérite qu’on s’y attarde un peu: c’est l’égalité 1+x+x^2+\cdots+x^n+\cdots=ON (qui signifie que quand on part du point O, on arrive bien au point P et on ne s’arrête pas avant). Pour la prouver, nous allons évaluer la différence ON- (1+x+x^2+\cdots+x^n), qu’on appelle reste partiel:series_geometrique_demonstration_par_les_distances_fig_13_reste_partielCe reste partiel correspond à la distance RE sur la figure. D’après le théorème de Thalès appliqué au triangle PAN, on a:

\dfrac{PE}{PA}=\dfrac{RE}{AN}

Mais d’après le théorème de Thalès appliqué cette fois-ci au triangle POA, on a:

\dfrac{PE}{PA}=\dfrac{EF}{OA} \Rightarrow \dfrac{PE}{PA}=\dfrac{x^n}{1}

On en déduit que \dfrac{RE}{AN} = \dfrac{x^n}{1}, et donc, le reste partiel de cette série vaut : RE = x^n \times AN. Comme la suite (x^n) tend vers 0, cela veut bien dire que 1+x+x^2+\cdots+x^n+\cdots=ON.

Bonus (quand y en a plus, ben y en a encore): Comme ON- (1+x+x^2+\cdots+x^n) =RE on en déduit que:

1+x+x^2+\cdots+x^n = ON - RE = ON -  x^n\times AN  = ON - x^n (ON-1)

donc:

1+x+x^2+\cdots+x^n = ON (1-x^n) + x^n

Or, on a vu que ON = \dfrac{1}{1-x}, donc

1+x+x^2+\cdots+x^n = \dfrac{1-x^n}{1-x} + x^n

ce qui donne la formule bien connue de la somme partielle d’une série géométrique:

\boxed{ 1+x+x^2+\cdots+x^n = \dfrac{1-x^{n+1}}{1-x} }

Publié dans Géométrie | Tagué , , , , , , | 18 commentaires

Êtes-vous aussi bon qu’un élève de CM1 ?

Voici une photo de deux petits exercices extraits d’un manuel de mathématiques Islandais de niveau CM1 (donc pour des élèves de 9 à 10 ans):

manuel_de_mathématiques_Islandais

Même sans savoir lire l’Islandais, on comprend que chaque figure géométrique correspond à un certain nombre de points, qu’il faut déterminer. (En fait, d’après la traduction Google, « hvert er gildi hverrar myndar ? » signifie « Quelle est la valeur de chaque image? »)

Je ne doute pas un seul instant que vous êtes capable de résoudre ces deux problèmes. Je vais plutôt simplement vous demander de réfléchir au raisonnement que suivrait un élève de CM1 pour résoudre ces deux problèmes.

Et une fois que vous aurez réfléchi à cela, lisez la suite !

Analyse du 1er problème

Je vous remets l’énoncé du 1er exercice:

probleme_niveau_CM1_1er_probleme

On peut imaginer que l’élève de CM1 moyen va commencer par regarder la 1ère ligne et se dire que « Si quatre triangles valent 80, alors un triangle vaut 20 ». Puis, il regardera la 2ème ligne, et il se dira : « Les triangles valent 60 à eux trois. Les trois cercles valent donc 75 moins 60, c’est-à-dire 15. Donc un cercle vaut 5 ». Il sautera ensuite la troisième ligne car il n’a encore aucune information sur les étoiles et les carrés et il ira directement à la dernière ligne: deux triangles et un cercle valent 20+20+5=45. Donc, les trois étoiles valent 75 moins 45 c’est-à-dire 30. Ainsi, une étoile vaut 10. Il reviendra pour finir à la 3ème ligne et il déduira qu’un carré vaut 35.

Analyse du second problème

Pour rappel, voici l’énoncé:

probleme_niveau_CM1_2eme_probleme

Pour ce problème, l’élève de CM1 moyen se dira qu’il est plus simple d’introduire des variables que des formes géométriques, donc il posera sans doute:

x = nombre de points d’un disque jaune
y = nombre de points d’un rectangle vert
z = nombre de points d’une étoile rose
t = nombre de points d’un triangle rouge.

Puis, il comprendra assez vite qu’il s’agit d’un système linéaire de 3 équations à 4 inconnues qu’il s’empressera d’écrire plus simplement sous la forme:

\left\{  \begin{array}{ccccccccc}  6x & + & 3y & & & & & = & 30 \\  x & + & y & + & z & + & t & = & 20 \\  3x & + & 3y & + & 3z & & & = & 33 \\  \end{array}  \right.

système qui est encore équivalent à:

\left\{  \begin{array}{cccccccccl}  2x & + & y & & & & & = & 10 & (L_1)\\  x & + & y & + & z & + & t & = & 20 &(L_2)\\  x & + & y & + & z & & & = & 11 & (L_3)\\  \end{array}  \right.

Il pensera alors sans doute à combiner les équations, et en particulier, il remplacera la deuxième ligne par la deuxième moins la troisième (L_2 \leftarrow L_2 - L_3):

\left\{  \begin{array}{cccccccccl}  2x & + & y & & & & & = & 10 & (L_1)\\  & & & & & & t & = & 9 &(L_2) \leftarrow (L_2) - (L_3)\\  x & + & y & + & z & & & = & 11 & (L_3)\\  \end{array}  \right.

Il constatera alors avec joie que t=9 et que donc l’ensemble des solutions est contenu dans un hyperplan de \mathbb{R}^4, ce qui signifie qu’il peut être plongé dans un espace à trois dimensions, ce qui est génial car il pourra interpréter cela en termes d’intersection de plans dans l’espace, notion qu’il venait tout juste de découvrir l’an passé en CE2 !

Mais il gardera son calme encore un peu, puisqu’il n’aura pas encore fini la résolution en tant que telle. Il sera bien sûr content d’avoir trouver t=9, mais il lui restera à comprendre ce que donnera l’intersection des deux plans d’équations cartésiennes 2x+y=10 et x + y + z = 11 (ce sont bien des plans lorsqu’ils sont vus comme des sous-espaces affines de l’espace à 3 dimensions d’équation cartésienne t=9 !). Il griffonnera probablement sur un bout de papier une représentation en 3D de ces plans:

Eleve_CM1_représente_les_plansIl comprendra alors que ces plans ne sont pas parallèles (ce qui était de doute façon évident pour lui car des vecteurs normaux à ces plans sont respectivement \vec{n_1} = \begin{pmatrix} 2 \\ 1 \\ 0\\ \end{pmatrix} et \vec{n_2} = \begin{pmatrix} 1 \\ 1 \\ 1\\ \end{pmatrix}, qui ne sont clairement pas colinéaires), donc il saura que ce système aura pour ensemble de solution toute une droite, qu’il essaiera de donner sous forme paramétrique (tant qu’à faire). Pour cela, il repartira du système:

\left\{  \begin{array}{cccccccccl}  2x & + & y & & & & & = & 10 & (L_1)\\  & & & & & & t & = & 9 &(L_2)\\  x & + & y & + & z & & & = & 11 & (L_3)\\  \end{array}  \right.

et il fera la combinaison:

\left\{  \begin{array}{cccccccccl}  2x & + & y & & & & & = & 10 & (L_1)\\  & & & & & & t & = & 9 &(L_2) \\  -x & & & + & z & & & = & 1 & (L_3) \leftarrow (L_3)-(L_1) \\  \end{array}  \right.

ce qui lui donnera:

\left\{  \begin{array}{ccc}  y & = & -2x + 10 \\  t & = & 9 \\  z & = & x + 1 \\  \end{array}  \right.

En prenant x comme paramètre, il obtiendra alors l’équation paramétrique suivante:

\exists \lambda \in \mathbb{R} , \left\{  \begin{array}{cl}  x & = \lambda \\  y & = -2\lambda + 10 \\  z & = \lambda +1 \\  t & = 9  \end{array}  \right.

Notre élève de CM1 moyen se dira sans doute qu’il vient de prouver qu’il y a une infinité de solutions, mais que, quand même, il n’est qu’en CM1 et que les les nombres réels ne sont peut-être pas au programme, donc il imaginera que les solutions qu’il doit donner à ce problème devront être des nombres entiers. Il supposera ainsi x, y, z , t\in \mathbb{N} , ce qui, d’après l’équation paramétrique précédente lui donnera les conditions suivantes:

\left\{  \begin{array}{l}  x = \lambda \in \mathbb{N} \\  y = -2\lambda + 10 \geq 0 \\  z = \lambda +1 \geq 0 \\  t = 9  \end{array}  \right.

c’est-à-dire:

\left\{  \begin{array}{l}  \lambda \in \mathbb{N} \\  5 \geq \lambda \\  \lambda \geq -1 \\  \end{array}  \right.

Il en déduira que \lambda ne peut valoir que 0, 1, 2, 3, 4 ou 5, ce qui lui donnera finalement les six solutions suivantes:

x = 0, y = 10, z = 1, t = 9
x = 1, y = 8, z = 2, t = 9
x = 2, y = 6, z = 3, t = 9
x = 3, y = 4, z = 4, t = 9
x = 4, y = 2, z = 5, t = 9
x = 5, y = 0, z = 6, t = 9

Mais comme il trouvera que les formes géométriques, c’est quand même vachement plus joli que les x et les y, voici la réponse finale qu’il rendra à son professeur:eleve-CM1-reponse-finale-complete-au-2eme-exercicePourquoi poser un tel problème à des CM1 ?

Je précise que l’image de ce manuel est authentique. Le fait qu’il n’y a pas une seule solution alors que la question était (si on en croit la traduction !) « quelle est la valeur de chaque image ? » pourrait faire croire qu’il y a eu une erreur dans l’énoncé du second exercice (il n’y a que 3 équations et il en faudrait une quatrième pour avoir une solution unique). Mais on peut aussi penser que tout cela est volontaire et qu’on n’attendait pas des élèves qu’ils trouvent toutes les solutions, mais qu’ils trouvent au moins une solution en tâtonnant ! (ce qui est tout à fait raisonnable en CM1). A moins qu’on attendait d’eux qu’ils écrivent un programme « Brute Force » pour trouver toutes les solutions entières en quelques lignes de code…

Et vous, aviez-vous trouvé au moins une solution ?

Publié dans Inclassable, Nombres | Tagué , , , , | 12 commentaires

Nombres de Fermat (2ème partie): comment montrer que F7 n’est pas premier ?

Conseil au lecteur avisé: il est recommandé d’avoir lu la première partie de cet article avant de se lancer dans celui-ci. Et puisque je me soucie sincèrement du bien-être de mes lecteurs, j’en profite aussi pour vous dire qu’il est recommandé de manger F_1 = 2^{2^1}+1 fruits et légumes par jour.

Dans la première partie de cet article, nous avions vu comment Euler avait réussi à montrer que le nombre de Fermat F_5=2^{2^5}+1 n’est pas premier, en déterminant une factorisation explicite de ce  nombre. Nous avions aussi vu que, malheureusement, cette méthode se révélait inefficace en pratique pour montrer que le nombre F_7=2^{2^7}+1 n’est pas premier. Mais, rassurez-vous, nous allons tout de même réussir à montrer que F_7 n’est pas premier, sans même avoir besoin de trouver sa factorisation !

Houston, on a un Pépin !

Il existe un test qui permet de prouver plutôt rapidement qu’un nombre de Fermat est ou n’est pas premier, qui s’appelle le test de Pépin, en l’honneur du mathématicien français Théophile Pépin (1826-1904). Ce test a permis de prouver que F_7 n’est pas premier pour la première fois en 1905 (par un certain J. C. Morehead), alors qu’un facteur explicite de ce nombre  n’a été trouvé que 65 ans plus tard ! Allez, sans plus attendre, voici le test de Pépin:

Soit F_n=2^{2^n}+1 pour n>0. Le nombre F_n est premier si, et seulement si,

3^{\frac{F_n-1}{2}} \equiv -1 \mod [F_n]

 

Là, vous êtes censés me dire « Mais d’où sort ce 3 ? » et moi je suis censé vous dire que cette question est légitime et qu’originellement, Pépin avait utilisé 5 à la place de 3. Et là, vous allez répondre: « Bon, on a toujours pas compris pourquoi ce 3, et en plus, d’où vient cet exposant au-dessus du 3 ? ». Et je vous répondrais d’être un peu patients, car on a tout l’article pour voir d’où tout cela vient, mais s’il y a une chose à retenir, c’est que ce test est basé sur le fait que 3 est (ou n’est pas) un carré modulo F_n, et est donc intimement lié à loi de réciprocité quadratique.

Avant de poursuivre, j’aimerais juste faire remarquer que 3 est toujours premier avec F_n lorsque n > 0. Cela provient d’une propriété dont on avait déjà parlé dans l’article précédent: deux nombres de Fermat (et 3 est un nombre de Fermat !) sont toujours premiers entre eux.

Condition suffisante

Commençons par montrer le sens le moins difficile du théorème de Pépin, à savoir: si 3^{\frac{F_n-1}{2}} \equiv -1 \mod [F_n] alors le nombre de Fermat F_n est premier. En prenant cette congruence au carré, on a:

\left(3^{\frac{F_n-1}{2}}\right)^2 \equiv (-1)^2 \mod [F_n]

ce qui donne 3^{F_n-1} \equiv 1 \mod [F_n]. Autrement dit, l’ordre de 3 modulo F_n divise F_n - 1 = 2^{2^n} donc est de la forme 2^k avec 0 \leqslant k \leqslant 2^n. Mais si on avait k < 2^n alors en prenant la relation 3^{2^k} \equiv 1 \mod [F_n] au carré autant de fois qu’il le faut (c’est-à-dire 2^n -1 - k fois), on trouverait

3^{2^{2^n - 1}} \equiv 1 \mod [F_n]

ce qui voudrait dire que 3^{\frac{F_n-1}{2}} \equiv 1 \mod [F_n] et donc cela contredirait notre hypothèse de départ. On a donc k=2^n, ce qui signifie que l’ordre de 3 est 2^{2^n} = F_n - 1. Autrement dit, quand on regarde modulo F_n les puissances:

3^0, 3^1, 3^2, \cdots, 3^{F_n - 2}

on obtient tous les nombres 1, 2, 3, \cdots, F_n-1 (pas forcément dans cet ordre, mais on les obtient tous. C’est bien ce que veut dire que l’ordre de 3 est F_n-1). Puisque chaque puissance 3^k est première avec F_n (car 3 est premier avec F_n), on en déduit que F_n est premier avec tous les nombres 1, 2, 3, \cdots, F_n-1. En particulier, F_n n’est divisible par aucun nombre strictement inférieur  à lui-même; c’est donc qu’il est premier !

Nous venons donc de montrer que le test de Pépin est suffisant pour prouver que F_n est premier; il nous reste à voir qu’il est aussi nécessaire. Mais avant cela, comme nous avons déjà beaucoup réfléchi et que la suite s’annonce un peu plus difficile, je vous propose de vous détendre un peu l’esprit en regardant cette petite vidéo d’un phoque qui tourne sur lui-même.

Interlude: le critère d’Euler et la loi de réciprocité quadratique

Avant de se lancer dans la condition nécessaire, il va nous falloir faire quelques rappels. Comme dit plus haut, le test de Pépin est fortement lié au fait que 3 est, ou n’est pas, un carré modulo F_n et, il se trouve qu’il existe un critère assez simple pour savoir si c’est le cas ou non: il s’agit du critère d’Euler (dont nous avions déjà parlé dans la première partie de l’article… vous comprenez pourquoi je vous ai demandé de lire cette première partie ? Si ce n’est pas encore fait, allez-y ! Et attention, je vous surveille…) Dans le cas qui nous intéresse ici, si on suppose que F_n est premier, le critère d’Euler s’énonce ainsi:

  • 3 est un carré modulo F_n si, et seulement si, 3^{\frac{F_n - 1}{2}} \equiv 1 \mod [F_n]
  • 3 n’est pas un carré modulo F_n si, et seulement si, 3^{\frac{F_n - 1}{2}} \equiv -1 \mod [F_n]

Pour énoncer ce critère plus simplement, on définit le symbole de Legendre \left( \dfrac{3}{F_n} \right) de la façon suivante:

\left( \dfrac{3}{F_n} \right) = \begin{cases} +1 \text{ si 3 est un carr\'e modulo } F_n \\ -1 \text{ si 3 n'est pas un carr\'e modulo } F_n \end{cases}

Le critère d’Euler s’écrit alors comme suit:

3^{\frac{F_n - 1}{2}} \equiv \left( \dfrac{3}{F_n} \right) \mod [F_n]

Ce qui va nous intéresser dans la suite va être de savoir pourquoi ce fameux symbole de Legendre vaut ici forcément -1. Et pour cela, nous aurons besoin de la belle loi de réciprocité quadratique…

Condition nécessaire

Montrons l’autre sens du théorème de Pépin: si on suppose que F_n est un nombre premier alors la loi de réciprocité quadratique nous dit que

\left( \dfrac{3}{F_n} \right) \times \left( \dfrac{F_n}{3} \right) = (-1)^{\frac{(3-1)(F_n -1)}{4}}

Autrement dit,

\left( \dfrac{3}{F_n} \right) \times \left( \dfrac{F_n}{3} \right) = (-1)^{\frac{2\times 2^{2^n}}{4}} = (-1)^{\frac{2^{2^n}}{2}}

Comme n>0, le nombre \frac{2^{2^n}}{2} est pair, ce qui donne \left( \frac{3}{F_n} \right) \times \left( \frac{F_n}{3} \right)=1. Ainsi, pour savoir si \left( \frac{3}{F_n} \right) vaut 1 ou -1, il suffit de déterminer le nombre \left( \frac{F_n}{3} \right), ce qui revient à savoir si F_n est un carré modulo 3 ou non. Comme 2 \equiv -1 \mod [3], pour tout entier n>0,

2^{2^n} \equiv (-1)^{2^n}=1 \mod [3]

ce qui signifie que F_n - 1 \equiv 1 \mod [3]. Ainsi, F_n \equiv 2 \mod [3]. Mais on sait que 2 n’est pas un carré modulo 3, car il n’apparait pas dans la deuxième ligne du le tableau suivant:

n \mod [3] 0 1 2
n^2 \mod [3] 0 1 1

 

Donc, F_n n’est pas non plus un carré modulo 3, c’est-à-dire \left( \frac{F_n}{3}\right) = - 1. Ainsi, en reprenant la relation que nous avait donnée la loi de réciprocité quadratique, on trouve que:

\left( \dfrac{3}{F_n} \right) \times (-1) = 1

et donc \left( \dfrac{3}{F_n} \right) = - 1. Le critère d’Euler nous dit alors que:

3^{\frac{F_n - 1}{2}} \equiv \left( \dfrac{3}{F_n} \right) = - 1 \mod[F_n]

ce qui montre bien que cette condition est nécessaire. Ouf, on y est arrivé ! Y avait quand même pas mal de bouleau… un vrai travail de pépiniériste ! (oui, je sais, cette expression n’existe pas. Et c’est bien dommage.)

Comment implémenter ce test en pratique ?

La théorie c’est bien beau, mais la pratique, c’est autre chose. Un des problèmes que l’on peut rencontrer pour appliquer ce test, est le fait qu’il faille calculer une très grande puissance de 3. Par exemple, si on souhaite appliquer le test de Pépin au cas du nombre de Fermat F_7, on sera amené à calculer:

3^{\frac{F_7-1}{2}} = 3^{2^{2^7-1}}=3^{2^{127}}

qui est un nombre absolument GIGANTESQUE (de l’ordre de 10^{10^{37}}). Il est évident que nous n’allons pas faire bêtement le produit 3 \times 3 \times \cdots \times 3 (où le nombre 3 apparaît 2^{127} fois !). Nous allons plutôt remarquer que:

3^{2^{127}} = (\cdots (3^2)^2)^2 \cdots )^2

où il y a 127 mises au carré (ce qui fait donc 127 multiplications… c’est qui est quand même  beaucoup plus raisonnable. Pour information, cela s’appelle la méthode d’exponentiation (MEGA-)rapide et l’idée est, comme vous le voyez, de réutiliser astucieusement les produits déjà effectués.)

Vous allez peut-être me dire que, peu importe le nombre de produits effectués, le résultat est toujours un nombre gigantesque. Ce à quoi je répondrai qu’il ne faut pas oublier que la seule chose qui nous intéresse dans le test de Pépin, c’est le reste modulo F_7 de ce nombre. Donc, à chaque étape, après avoir calculé le carré, on réduit le résultat obtenu modulo F_7 avant de reprendre à nouveau le carré du nombre obtenu. Voici une implémentation en Python de cet algorithme:

Test de Pépin

et voici ce que l’on obtient pour le nombre F_7:

test_de_Pepin_F7_pas_premierComme on le voit, il ne nous a fallu que quelques centièmes de secondes pour montrer que F_7 n’est pas premier ! Il n’y a bien entendu aucune raison de s’arrêter à n=7 alors voici ce que le test donne pour les nombres de Fermat qui suivent:

n F_n premier ? Durée du test (en s)
2 oui 0,008
3 oui 0,008
4 oui 0,008
5 non 0,008
6 non 0,008
7 non 0,008
8 non 0,008
9 non 0,017
10 non 0,045
11 non 0,269
12 non 1,881
13 non 13,591
14 non 104,444
15 non 817,277

 

Au-delà de F_{15}, mon pauvre petit PC commençait à mettre un peu trop de temps pour réaliser le test… mais ce n’est pas grave, nous voyons déjà qu’après F_4, les 11 nombres de Fermat qui suivent ne sont pas premiers. Et ça, c’est chouette ! Bon, c’est vrai qu’on le savait déjà pour F_5, F_6, F_9, F_{10}, F_{11} et F_{12} après la première partie de cet article (puisqu’on en avait trouvé des facteurs explicites), mais là nous l’avons prouvé pour F_{7}, F_8, F_{13}, F_{14} et F_{15}. Et tout cela, plutôt rapidement… c’est pourquoi je propose d’appeler cela le test de Pépin le Bref, et c’est sur cette blague hilarante que je vous laisse !

Notes:

✓ Vous pouvez voir sur la page Wikipédia anglaise l’historique des test de Pépin.
✓ Vous pouvez aussi consulter l’article original de J. C. Morehead (1905), où il explique qu’il a appliqué le test de Pépin au nombre F_7  et qu’il a trouvé (à la main !) que:

\begin{array}{cl} 3^{\frac{F_7 - 1}{2}} \equiv & \text{ 11078095439554051657911156260048860 \ } \mod F_7 \end{array}

qui est donc bien différent de -1 modulo F_7, comme on le voit (ou pas !). On ne blaguait pas avec les calculs à l’époque !

Publié dans Arithmétique, Nombres | Tagué , , , , , , | 3 commentaires