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é , , , , , , | 17 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é , , , , | 7 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

Nombres de Fermat (1ère partie): Comment Euler a factorisé F5 ?

Dernièrement, on a beaucoup parlé des nombres de Mersenne avec la découverte d’un nouveau nombre de Mersenne premier: il s’agit de 2^{74 \, 207 \, 281} - 1, nombre qui comporte plus de 22 millions de chiffres en base 10. Pendant ce temps-là, le plus grand nombre de Fermat premier connu n’est que 65537. Et alors qu’on connaît 49 nombres de Mersenne premiers, on ne connaît que 5 nombres de Fermat premiers. Pourtant, ils sont tout aussi intéressants !

Que sont les nombres de Fermat ?

Un nombre de Fermat est un nombre qui peut s’écrire sous la forme 2^{2^n}+1. Par exemple, voici la liste des cinq premiers nombres de Fermat:

Nombres de Fermat

Comme leur nom l’indique, ces nombres ont été introduits par Pierre de Fermat, et la première trace que nous en avons est une lettre envoyée par Pierrot (oui c’est mon pote), datant de 1640.

Vous aurez peut-être remarqué que les cinq nombres de Fermat de la liste ci-dessus (3, 5, 17, 257 et 65537) sont tous des nombres premiers, ce qui a poussé Fermat à émettre la conjecture que tous les nombres de la forme 2^{2^n}+1 sont premiers. Nous savons aujourd’hui que cette conjecture est fausse, c’est-à-dire qu’il existe des nombres de Fermat qui ne sont pas premiers (et même pire que cela, nous n’avons pas découvert ne serait-ce qu’un seul autre nombre de Fermat premier !).

Le premier à avoir prouvé que cette conjecture est fausse est Euler qui, en 1732, a démontré que le nombre F_5=2^{2^5}+1=4 \, 294 \, 967 \, 297 n’est pas premier en donnant une factorisation explicite de ce nombre. Plus précisément, il a prouvé que

F_5 = 641 \times 6 \, 700 \, 417

Le plus beau dans cette histoire est que cela ne lui a demandé de faire en tout et pour tout que 5 divisions. Comment a-t-il donc fait ?

Une condition nécessaire sur les diviseurs des nombres de Fermat

Euler ne s’est bien entendu pas bêtement lancé dans une succession de divisions de F_5 par 2, 3, 4, 5, … jusqu’à ce qu’il tombe sur un facteur. Non, il a été plus malin que cela car il a utilisé (et démontré) le théorème  suivant:

Tout diviseur premier p de F_n=2^{2^n}+1 est de la forme

p=k \times 2^{n+1}+1

k est un entier.

Voici une démonstration de cette propriété sans doute plus moderne que celle d’Euler, qui utilise la notion de congruence. Rappelons deux choses au préalable. Si a et p sont deux entiers premiers entre eux alors:

  1. Il existe un plus petit entier m>0 tel que a^m \equiv 1 \mod [p] qu’on appelle l’ordre de a modulo p.
  2. Si m' est un autre nombre tel que a^{m'} \equiv 1 \mod [p] alors le nombre m' est divisible par l’ordre de a.

Cela étant dit, nous pouvons à présent prouver la propriété. Soit p un diviseur premier du nombre de Fermat F_n. Comme les nombres de Fermat sont impairs, on ne peut pas avoir p=2 et donc p est premier avec 2 (cela nous permettra de parler de l’ordre de 2 modulo p).

• Commençons par montrer que l’ordre de 2 modulo p est 2^{n+1}. Tout d’abord, le fait que p divise F_n se traduit par la congruence:

F_n \equiv 0 \mod [p]

d’où 2^{2^n} \equiv -1 \mod[p]. En prenant cette relation au carré (comme les règles sur les congruences le permettent), on obtient \left(2^{2^n}\right)^2 \equiv (-1)^2 \mod [p] c’est-à-dire

2^{2^{n+1}} \equiv 1 \mod [p]

D’après le rappel n°2, cela signifie que l’ordre de 2 modulo p est un diviseur de 2^{n+1} donc un nombre de la forme 2^r avec 0 \leqslant r \leqslant n+1. Si on avait r\leqslant n, en prenant la relation 2^{2^r} \equiv 1 \mod [p] au carré n-r fois (autant de fois qu’il faut pour aller de r à n), on trouverait 2^{2^n} \equiv 1 \mod [p] ce qui n’est pas possible car nous avons dit que 2^{2^n} \equiv -1 \mod[p].  Ainsi, r=n+1 et donc l’ordre de 2 modulo p est 2^{n+1}.

• Il nous reste à montrer que p est de la forme p=k \times 2^{n+1}+1. Comme p est premier, le petit théorème de Fermat nous dit que:

2^{p-1} \equiv 1 \mod [p]

et donc le rappel n°2 nous dit que l’ordre de 2 modulo p (dont on sait qu’il vaut 2^{n+1} ) divise p-1. Ainsi, il existe un entier k tel que p-1 = k \times 2^{n+1} et on trouve bien que

\boxed{ p = k \times 2^{n+1}+1 }

La factorisation de F5

Grâce à la propriété précédente, Euler a d’abord remarqué que les diviseurs premiers de F_5 = 2^{2^5} +1 sont de la forme:

p=k \times 2^{5+1}+1 = 64k+1

Puis il a essayé de diviser F_5 par les différentes valeur de p obtenues pour k=1, 2, 3.... Petite remarque avant de le faire nous-mêmes: si le nombre p obtenu pour une certaine valeur k n’est pas premier, alors il ne peut forcément pas diviser F_5 car, si c’était le cas, les diviseurs premiers de p (qui sont strictement plus petits que lui-même) seraient aussi de la forme k\times 2^{n+1}+1 et donc nous devrions être déjà tombé sur un diviseur de F_5 ! Cela étant dit, allons-y:

• Si k=1 alors p=64 \times 1 + 1=65 qui n’est pas premier (car divisible par 5), donc ne perdons pas notre temps à diviser F_5 par 65.

• Si k=2 alors p=64 \times 2 + 1 = 129 qui n’est pas premier non plus (car divisible par 3) donc passons au suivant.

• Si k=3, on trouve p=193 qui est bien premier. Mais en effectuant la division de F_5=4 \, 294 \, 967 \, 297 par 193, on trouve un reste non nul, signe que F_5 n’est pas divisible par 193. Passons donc au suivant.

• Si k=4, on a p=257 qui est lui aussi premier. Là encore, en effectuant la division de F_5 par 257, on trouve un reste non nul, donc 257 n’est pas un diviseur premier de F_5.

• Si k=5, on a p=321 qui n’est pas premier (car divisible par 3).

• Si k=6, on trouve p=385 qui n’est pas premier non plus car divisible par 5.

• Si k=7, on trouve p= 449 qui est premier mais la division de F_5 par 449 donne un reste non nul.

• Si k=8, on a p=513 qui n’est pas premier (divisible par 3).

• Si k=9, on a p=577 qui est bien premier mais le reste de la division de F_5 par 577 est non nul.

• Si k=10, alors p=641 et là… YOUPI ! La division de F_5 par 641 tombe juste et donne le quotient 6  700 417. Cela démontre que F_5 = 641 \times 6 \, 700 \, 417 et donc que F_5 n’est pas premier.

Comme on le voit, il a fallu 5 divisions à Euler pour arriver à la factorisation voulue. En fait, on aurait même pu n’en faire que 4 car il était certain d’avance que 257 ne pouvait pas diviser F_5. La raison en est que 257 est le nombre de Fermat F_3 et que deux nombres de Fermat sont toujours premiers entre eux ! Pour en savoir plus à ce propos, vous pouvez lire un autre article que j’avais écrit.

Lucas pour faire mieux qu’Euler

Je vous propose à présent de factoriser nous-mêmes d’autres nombres de Fermat. Mais avant cela, nous allons être encore plus astucieux qu’Euler car nous allons donner un raffinement du théorème précédent dû au mathématicien Édouard Lucas (bien moins connu qu’Euler, mais pourtant grand mathématicien lui aussi) qui  nous permettra de faire moitié moins de divisions !  Voici l’énoncé de ce théorème:

Si n \geqslant 2, tout diviseur premier p de F_n=2^{2^n}+1 est de la forme

p=k \times 2^{n+2}+1

k est un entier.

Vous ne voyez pas de différence ? Regardez un peu l’exposant de 2, qui est n+2 au lieu de n+1 dans la propriété précédente. Par exemple, pour factoriser F_5, ce théorème dit que les diviseurs premiers sont de la forme p=k \times 2^{5+2}+1=128k+1. Il nous aurait donc seulement fallu tester les valeurs p=129, 257, 385, 513, 641 (correspondant respectivement à k=1,2,3,4,5), ce qui nous aurait valu de faire uniquement 2 divisions car seuls 257, et 641 sont premiers (et même une seule vu que 257 est un nombre de Fermat et qu’il ne peut pas diviser un autre nombre de Fermat).

Voyons maintenant comment démontrer ce théorème de Lucas. Là encore, voici deux rappels (beaucoup moins évidents que les rappels précédents) qui nous allons utiliser:

  1. Si un entier a est un carré modulo p alors a^{\frac{p-1}{2}} \equiv 1 \mod [p] (on appelle cela le critère d’Euler).
  2. Si p est de la forme p=8m+1 alors 2 est un carré modulo p.

C’est parti pour la démonstration. On considère un diviseur premier p de F_n. Nous avions démontré qu’il existe alors un entier k tel que p=k \times 2^{n+1}+1. Comme on suppose n \geqslant 2, on a n+1 \geqslant 3 ce qui entraîne que  2^{n+1} est divisible par 2^3=8. Donc, le nombre p est de la forme p=8m +1 (avec m=k\times 2^{n-2}). D’après le second rappel, on en déduit que 2 est un carré modulo p ce qui, d’après le premier rappel, nous donne la relation:

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

Ainsi, l’ordre de 2 modulo p (dont nous avions vu qu’il valait 2^{n+1}) doit diviser \frac{p-1}{2}. Il existe donc un entier k' tel que:

k' \times 2^{n+1} = \frac{p-1}{2}

ce qui donne bien p = k' \times 2^{n+2} +1. CQFD.

Factorisation de quelques nombres de Fermat

Avec le théorème de Lucas et un ordinateur, on va pouvoir factoriser F_6, F_9, F_{10}, F_{11} et F_{12}. Pour cela j’ai écrit un programme qui renvoie le plus petit nombre qui divise F_n (ce nombre étant forcément premier). Le programme est disponible ici:

Plus petits diviseurs des nombres de Fermat

et le voici en action:

Programme_factorisation_nombres_de_FermatPour obtenir une factorisation, il suffit de diviser par le facteur premier trouvé. Par exemple, en divisant F_6 par 274 177, on trouve:

F_6 = 274 \, 177 \times 67 \, 280 \, 421 \, 310 \, 721

Attention: cette factorisation n’est peut-être pas une décomposition en facteurs premiers car il se peut que le deuxième facteur (67 280 421 310 721) ne soit pas premier.

Mais au fait, vous devriez me demander: pourquoi avoir soigneusement évité de factoriser F_7 ? Si vous lancez le programme pour ce nombre, vous constaterez que le programme tourne, tourne, tourne… sans s’arrêter ! Il y a deux raisons possibles à cela: soit il est premier, soit ses facteurs premiers sont gigantesques !

En lançant le programme pour F_8, on se retrouve confronté au même problème. En fait, il se trouve que F_7 et F_8 ne sont pas premiers, mais le montrer en essayant de trouver un facteur premier a l’air de prendre du temps. Nous verrons donc dans la deuxième partie de cet article comment prouver qu’ils ne sont pas premiers, sans même être capables de donner explicitement leurs facteurs !

Sources et notes

  • Pour de plus amples précisions historiques, vous pouvez consulter avec profit: « How Euler did it? Factoring F5 » (par Ed Sandifer).
  • Si vraiment vous voulez connaître les factorisations de F_7 et F_8, vous pouvez consulter la page Wikipédia à ce sujet (et vous constaterez que leurs plus petits facteurs premiers sont respectivement des nombres à 17 et 16 chiffres !).
  • Pour finir, voici les démonstrations des rappels énoncés dans cet article. La dernière démonstration (qui est un cas particulier de la loi de réciprocité quadratique) est particulièrement intéressante ! Normal, elle est due à Gauss…
Publié dans Arithmétique, Nombres | Tagué , , , , , | 1 commentaire

Combien de temps faut-il attendre avant de gagner au Loto ?

Attention: jouer à des jeux d’argents comporte des risques de choper des morpions, de devenir un pilier de comptoir ou de connaître des noms d’équidés par cœur. Nan, sérieux, faites gaffe !

Saviez-vous que si vous jouez suffisamment de fois au Loto, tôt ou tard vous gagnerez le gros lot et que cela est un fait mathématiquement démontrable ? Comme nous allons le voir, la théorie des probabilités dit qu’en jouant indéfiniment, on finit à un moment par gagner, ce qui n’est d’ailleurs pas sans rappeler la célèbre maxime des Shadoks:

Ce n’est qu’en essayant continuellement que l’on finit par réussir. En d’autres termes, plus ça rate et plus on a de chances que ça marche.

Attention cependant: ce n’est pas parce que vous avez perdu les 10 000 dernières fois que vous avez plus de chance de gagner à la prochaine ! Tous les parties sont indépendantes et tout recommence à zéro à chaque fois. Ainsi, localement on ne peut rien prévoir mais sur le long terme, une tendance se dégage où vous gagnerez à un moment donné.

Sans doute que vous allez me demander où est l’arnaque car s’il suffisait de jouer au Loto constamment pour gagner, ça devrait faire longtemps que certains auraient décroché le gros lot. Et pourtant, je vous le promets, d’arnaque il n’y a point ! Tôt ou tard vous gagnerez ! Mais en fait, plus tard que tôt, et c’est bien là le problème… Voici donc la question à laquelle nous allons répondre dans cet article: en moyenne, au bout de combien de temps (c’est-à-dire de combien de parties) gagne-t-on au Loto ?

Le cas d’une pièce

Avant de nous attaquer au cas du Loto, commençons par un exemple sans doute plus facile à concevoir, celui d’un pièce de monnaie. Je pense que vous arriverez tous à admettre que, si vous lancez une pièce suffisamment de fois, il y a un moment où vous tomberez sur Pile (c’est d’ailleurs amusant que ce résultat soit plutôt intuitif dans le cas d’une pièce et beaucoup moins dans le cas du Loto, alors que les situations sont quasi-identiques). Pour savoir au bout de combien de lancers on tombe sur Pile en moyenne, j’ai réalisé une petite simulation:

Loto_simulation_lancers_pieceSi on en croit cette simulation, il faut lancer une pièce environ deux fois en moyenne pour que Pile apparaisse. Ce qui est remarquable, c’est qu’à aucun moment le programme n’a tourné sans se terminer, signe qu’à chaque fois, Pile est bien sorti à un moment ou à un autre.

Le cas du dé

Prenons un autre exemple pour bien fixer les idées et essayer de voir si on peut conjecturer quelque chose. Si on lance un dé suffisamment de fois, je pense que là aussi il vous est facile d’arriver à concevoir que tôt ou tard on tombera sur un 4. Pour savoir en moyenne au bout de combien de lancers cela arrivera, j’ai encore fait une simulation:

Loto_simulation_lancers_deOn voit donc qu’en moyenne il faut  lancer un dé environ 6 fois pour obtenir un 4.

Conjecture

Résumons ce qu’on a vu:

  • dans le cas d’une pièce de monnaie, on a une chance sur 2 de tomber sur Pile et, en moyenne, Pile sort au bout de 2 lancers;
  • dans le cas d’un dé, on a une chance sur 6 de tomber sur un 4 et, en moyenne, le 4 sort au bout de 6 lancers.

Vous la voyez venir la conjecture ? La voici:

Dans une expérience aléatoire qu’on répète de manière identique et indépendante, si un événement a une probabilité p de se réaliser, alors il faut en moyenne \frac{1}{p} répétitions de cette expérience pour que cet événement se réalise.

Nous allons bien entendu prouver cette conjecture dans la suite mais, nous allons d’abord prouver que tôt ou tard on gagne bien au Loto.

Pourquoi gagne-t-on forcément un jour ou l’autre ?

On considère une expérience aléatoire dont la probabilité de succès est notée p. On notera q=1-p la probabilité de perdre. Enfin, nous noterons X le nombre de parties à effectuer avant de gagner.

La première chose à faire est d’étudier cette variable aléatoire X, autrement dit, de déterminer la valeur des nombres P(X=n) pour tout n (on dit qu’on détermine la loi de probabilité de X). Pour bien visualiser les choses, on peut représenter la répétition de ces expériences à l’aide du graphe très simple suivant:

La boucle vers le haut signifie qu'on perd la partie et la flèche vers la droite signifie qu'on gagne. Tant qu'on perd, on revient au point de départ, quoi !

La boucle vers le haut signifie qu’on perd la partie et la flèche vers la droite signifie qu’on gagne. Tant qu’on perd, on revient au point de départ !

Déterminons donc les probabilités P(X=n):

  • L’événement X=1 veut dire « On gagne dès la première partie » et donc correspond au chemin qui, partant du départ, va directement à l’arrivée. On a donc P(X=1)=p.
  • L’événement X=2 signifie « On perd à la première partie, et on gagne à la deuxième ». Autrement dit, depuis le départ on parcourt une boucle vers le haut puis on parcourt le chemin allant vers l’arrivée. Ainsi, P(X=2) = qp.
  • L’événement X=3 se traduit par « On perd à la première et à la deuxième partie, puis on gagne à la troisième ». Cela veut donc dire que l’on parcourt deux boucles vers le haut, puis on parcourt le chemin qui va vers l’arrivée. On a donc P(X=3) = q \times q \times p = q^2 p.
  • Plus généralement, l’événement X=n veut dire « On perd à la première, à la deuxième, … et à la (n-1)-ème partie et on gagne à la n-ème partie. On parcourt donc n-1 boucles vers le haut puis le chemin qui va à l’arrivée. Ainsi, P(X=n) = q^{n-1} p.

Cela étant dit, ce qui nous intéresse ici est l’événement « On gagne un jour ou l’autre ». Ce dernier se traduit par:

  • Soit on gagne à la première partie (X=1);
  • Ou bien on perd à la première mais gagne à la deuxième partie (X=2);
  • Ou bien on perd à la première et la deuxième mais on gagne à la troisième (X=3);
  • etc.
  • Ou bien on perd aux n-1 premières parties et on gagne à la n-ème (X=n).
  • etc.

Autrement dit, comme ces événements sont disjoints deux à deux, la probabilité p_{\infty} de gagner un jour ou l’autre est:

\begin{array}{rcl} p_{\infty} & = & P(X=1) + P(X=2) + \cdots + P(X=n) + \cdots \\  & = & \displaystyle{ \sum_{n=1}^{+\infty} P(X=n)}\\  & = & \displaystyle{ \sum_{n=1}^{+\infty} q^{n-1}p} \end{array}

En factorisant par p et en réindexant cette suite, on obtient donc

\displaystyle p_{\infty} = p \sum_{n=0}^{+\infty} q^n

On reconnaît ainsi une série géométrique toute gentillette que l’on sait calculer parfaitement:

\displaystyle p_{\infty} = p \times \frac{1}{1-q}

En se souvenant que q=1-p, on a donc

\displaystyle p_{\infty} = p \times \frac{1}{1-(1-p)} = \frac{p}{p}=1

La probabilité de gagner un jour ou l’autre au Loto est donc bien de 100%… Mais cela ne nous dit toujours pas au bout de combien de temps !

Faut-il être patient pour jouer au Loto ?

Comme X compte le nombre de parties qu’il faut faire avant de gagner, pour connaître le temps d’attente avant de gagner au Loto (c’est-à-dire le nombre de parties à jouer en moyenne avant de gagner le gros lot), il faut calculer l’espérance de la variable X. Par définition,

\displaystyle E(X) = \sum_{n=1}^{+\infty} n P(X=n)

donc

\displaystyle E(X) = \sum_{n=1}^{\infty}n q^{n-1} p= p \sum_{n=1}^{\infty}n q^{n-1}

Pour calculer \displaystyle \sum_{n=1}^{\infty}n q^{n-1}, il suffit de constater  que c’est la dérivée par rapport à q de \displaystyle \sum_{n=0}^{\infty} q^{n}= \frac{1}{1-q}. Je pense que vous savez tous dériver \displaystyle \frac{1}{1-q}, ce qui donne :

\displaystyle \sum_{n=1}^{\infty}n q^{n-1} = \frac{1}{(1-q)^2}

On en déduit alors que

\displaystyle E(X) = p \times \frac{1}{(1-q)^2} = p \times \frac{1}{(1-(1-p))^2} =\frac{p}{p^2} = \frac{1}{p}

ce qui prouve la conjecture émise précédemment.

Dans le cas du Loto (dans sa version actuelle), la probabilité de gagner le gros lot est de p =\frac{1}{19 068 840}, et donc le temps d’attente avant de gagner est en moyenne de \frac{1}{p}= 19 068 840 parties. A raison d’une partie jouée par semaine, il vous faudra attendre en moyenne 366 708 ans avant de gagner le jackpot.

J’espère en tout cas que cela vous aura convaincu qu’avant de gagner au Loto, il vous faudra en moyenne perdre 19 068 839 fois auparavant. En revanche, la Française des Jeux gagne à chaque fois !

Notes:

  • La variable aléatoire X que nous avons étudiée dans cet article suit ce qu’on appelle une loi géométrique.
  • Voici le code utilisé pour simuler les lancers de pièce et de dé.
Publié dans Probabilités | Tagué , , , , | 3 commentaires