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

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