Full contact – Episode II

Dans l’article précédent, nous avons vu un problème de contact dont le but était de construire un cercle à la fois tangent à une droite et un cercle donnés. Je vous propose un deuxième problème de contact, où, cette fois-ci, le but n’est pas la construction d’un cercle mais le calcul de son rayon.

Le problème que je vais vous proposer ci-dessous est un sangaku. Les sangakus étaient des problèmes géométriques d’origine japonaise, qui étaient gravés sur des tablettes en bois et accrochés dans les temples. Pour en savoir plus, vous pouvez consulter la page Wikipédia à ce sujet.

Le problème ! Le problème !

Voici sans plus attendre l’énigme à résoudre avec ce sangaku:

 Soit \mathcal{C}_1 et \mathcal{C}_2 deux cercles tangents, et d une droite tangente à ces deux cercles. On admet qu’il est possible de construire un troisième cercle qui est à la fois tangent aux cercles et à la droite. Question: si on connaît les rayons r_1 et r_2 des deux premiers cercles, que vaut le rayon r_3 du troisième cercle ?

Full_contact_II_sangaku_

Résolution

La résolution de ce problème utilisera la petite formule que nous avions démontrée dans l’ article précédent (Full contact – Episode I) (que je vous conseille d’aller lire !). Pour rappel, voici ce que nous avions démontré:

Full_contact_II_rappelSi on revient à notre sangaku, on peut appliquer notre formule trois fois:

Full_contact_II_sangaku_notations

  • \mathcal{C}_1 et \mathcal{C}_2 sont tangents donc: AB^2 = 4 r_1 r_2
  • \mathcal{C}_1 et \mathcal{C}_3 sont tangents donc: AC^2 = 4 r_1 r_3
  • \mathcal{C}_2 et \mathcal{C}_3 sont tangents donc: CB^2 = 4 r_2 r_3

D’autre part, comme les points A, B et C sont alignés, on a l’égalité AB = AC + CB et en élevant cette relation au carré, on a

AB^2 = AC^2 + 2 AC \times CB + CB^2

On remplace chaque distance par l’expression que nous avons vue ci-dessus:

4 r_1 r_2 = 4 r_1 r_3 + 2 \sqrt{4 r_1 r_3} \sqrt{4 r_2 r_3} + 4 r_2 r_3

c’est-à-dire:

4 r_1 r_2 = 4r_1r_3 + 8 r_3 \sqrt{r_1 r_2} + 4 r_2 r_3

Il reste à isoler r_3. En factorisant, on a:

4 r_1 r_2 = 4 r_3 ( r_1 + 2 \sqrt{r_1} \sqrt{r_2} + r_2)

Ce ne serait pas une petite identité remarquable, là ? Mais oui !

4 r_1 r_2 = 4 r_3 (\sqrt{r_1} + \sqrt{r_2} )^2

Et on obtient:

\boxed{ r_3 = \dfrac{r_1 r_2}{(\sqrt{r_1} + \sqrt{r_2} )^2} }

On pourrait s’arrêter là mais on peut mettre cette formule sous une autre forme que je trouve plus élégante. Commençons par prendre l’inverse de l’égalité précédente:

\dfrac{1}{r_3} = \dfrac{(\sqrt{r_1} + \sqrt{r_2} )^2}{r_1 r_2}

Puis prenons la racine carrée dans les deux membres:

\dfrac{1}{\sqrt{r_3}} = \dfrac{\sqrt{r_1} + \sqrt{r_2}}{\sqrt{r_1}\sqrt{r_2}}

ce qui donne la belle formule:

\boxed{\dfrac{1}{\sqrt{r_3}} = \dfrac{1}{\sqrt{r_1}} + \dfrac{1}{\sqrt{r_2}}}

Cette formule fait penser à la formule obtenue en physique quand on met des résistances en parallèles !

Et la construction alors ?

Il est possible de construire le troisième cercle tangent à la règle et au compas, mais bien que la construction en elle-même ne soit pas trop dure, la justification est un peu plus subtile et je me suis donc bien gardé d’en parler dans cet article. Mais pour les gens intéressés, l’idée de la construction peut être vue ici… (attention, c’est en Anglais !).

Pour finir, des coordonnées

Pour terminer cet article, donnons un reformulation en termes de coordonnées qui peut être utile. On suppose qu’on s’est donné un repère et que la tangente commune aux cercles est l’axe des abscisses:

Full_contact_II_coordonneesOn suppose que les coordonnées des centres des deux premiers cercles sont connues. Quelles sont les coordonnées du centre du troisième cercle ? Nous voyons tout d’abord que son ordonnée est son rayon r_3= \frac{r_1 r_2}{(\sqrt{r_1} + \sqrt{r_2} )^2}. Quant à son abscisse, il suffit de déterminer la distance AC pour la trouver. Or, si on réutilise les différentes formules vues précédemment, on  a AC = 2\sqrt{r_1 r_3}, donc AC =2 \sqrt{r_1} \frac{\sqrt{r_1r_2}}{\sqrt{r_1} + \sqrt{r_2}}=2r_1 \frac{\sqrt{r_2}}{\sqrt{r_1} + \sqrt{r_2}}

Ainsi, les coordonnées du troisième cercle tangent sont:

(x_1 + 2r_1 \dfrac{\sqrt{r_2}}{\sqrt{r_1} + \sqrt{r_2}} ;\dfrac{r_1 r_2}{(\sqrt{r_1} + \sqrt{r_2} )^2})

 

Au final, ce n’était pas un problème si simple que cela, il y avait pas mal de boulot. Ils ne se foutaient pas de la gueule des gens quand ils posaient des sangakus à l’époque !

Note:

Pour l’anecdote, ce sangaku-ci (coup ça) fut posé en 1824 sur une tablette dans les environs de la préfecture de Gunma au centre du Japon (source).

Publié dans Géométrie | Tagué , , , | 4 Commentaires

Full contact – Episode I

Un petit problème géométrique, ça vous dit ?

Soit \mathcal{C} un cercle et d une tangente à ce cercle en un point A du cercle. Soit B un autre point de la droite d. Comment construire le cercle \mathcal{C}' qui est à la fois tangent à la droite d au point B et au cercle \mathcal{C} ?

Vous pouvez méditer sur le schéma illustrant ce problème ci-dessous: Probleme_Full_contact_I

Prenez une feuille, une règle et un compas, ou bien utilisez Geogebra, et constatez par vous-même que le tracé de ce cercle n’est pas évident, même en tâtonnant. D’ailleurs, rien ne dit que ce cercle existe a priori, même si notre intuition géométrique ne laisse aucun doute quant à cet existence !

Double contact

Il s’agit ici de ce qu’on appelle un problème de contact, c’est-à-dire un problème où le but est de construire un cercle qui soit tangent à un (des) cercle(s) et/ou une (des) droite(s) donné(s). Ce problème que nous allons traiter n’est pas extrêmement ardu mais n’est pas non plus complètement évident.

J’ai cru entendre que la part de la géométrie dans l’enseignement secondaire est en net recul et que les problèmes de géométrie pure n’ont plus vraiment leur place dans les programmes de nos chers élèves (au détriment de la géométrie analytique, plus calculatoire donc demandant moins de réflexion…). Je me souviens pourtant que, quand j’étais élève en Seconde, notre professeur, qui était plutôt de la vieille école, aimait nous poser des exercices de géométrie du même type que celui que nous allons résoudre.

La démarche qu’il nous imposait de suivre était le schéma "Analyse/Synthèse". Dans l’analyse, nous cherchions les conditions nécessaires à l’existence du point/de la droite/du cercle demandé. Dans la synthèse, nous montrions que la condition est suffisante pour avoir l’existence de l’objet géométrique cherché. Je vous propose ici de suivre cette démarche, en espérant qu’elle puisse faire comprendre toute la beauté du raisonnement géométrique à mes lecteurs !

Mise au point sur les tangentes

Avant de procéder à notre étude, il serait bon de rappeler ce que signifie cette notion de tangence. Il y a plusieurs définitions équivalentes, mais la définition la plus intuitive est la suivante:

Définition: Deux cercles (ou un cercle et une droite) sont tangents si leur intersection est réduite à un seul point.

Et on peut démontrer la propriété suivante:

Propriété 1: Deux cercles sont tangents (extérieurement) si, et seulement si, la distance entre les centres de ces cercles est égale à la somme des deux rayons.

Full_contact_I_propriete_1

ainsi que la deuxième propriété qui suit (dont je suis sûr qu’on la voit au collège):

Propriété 2: Un cercle de centre \Omega et de rayon r' et une droite d sont tangents en un point B si, et seulement si,
a) (\Omega B) \perp d
b) \Omega B = r'Full_contact_I_propriete_2

Cette mise au point étant faite, nous pouvons y aller !

I) Analyse

Dans cette partie, on va supposer que le cercle à construire existe et voir quelles conditions son centre et son rayon vérifient. Nous allons mettre en place quelques notations: on note O le centre du cercle \mathcal{C} et \Omega le centre du cercle \mathcal{C}' que l’on cherche. On notera aussi r et r' les rayons de \mathcal{C} et \mathcal{C}'.

La difficulté dans l’analyse est de ne pas confondre les objets fixes (les hypothèses de l’énoncé) et les objets qu’on cherche à déterminer et dont on ne sait pas où ils se trouvent a priori. Pour faire cette distinction sur nos schémas, nous représenteront en noir les objet fixes et en rouge les objets à trouver:

Full_contact_I_analyse_1

Si le cercle \mathcal{C}' existe alors, puisqu’il est tangent à la droite d, on sait que les droites (\Omega B) et d sont perpendiculaires. Dit autrement, \Omega appartient à la droite perpendiculaire à d passant par B (on note d' cette droite):

Full_contact_I_analyse_2La perpendiculaire d' est représentée en noir car elle ne dépend que de B et de d, donc est fixe ! Cela nous fait donc un premier objet fixe sur lequel on est sûr que se situe \Omega. Il s’agit alors de savoir à quel niveau de cette perpendiculaire d' se situe ce point. Pour déterminer cela, il va falloir utiliser la deuxième hypothèse de l’énoncé, à savoir le fait que \mathcal{C} et \mathcal{C}' sont tangents:

Full_contact_I_analyse_3Le fait que ces cercles soient tangents se traduit par la condition O\Omega = r + r'. Si on reformule cela (et c’est là toute l’astuce !), cela signifie que le point O appartient au cercle de centre \Omega et de rayon r+r'.

Full_contact_I_analyse_4Si on note C le point d’intersection de ce cercle avec la perpendiculaire d', on remarque que ce point se situe à une distance r du point B et donc que le point C ne dépend ni de \Omega, ni de r' et est donc fixe ! A partir de là, on constate que le point \Omega est situé à la même distance de deux points entièrement connus, à savoir O et C et donc \Omega se situe sur le médiatrice de [OC] (noté \Delta sur le schéma).

Full_contact_I_analyse_5Nous voyons ainsi que pour construire \Omega, il suffit de prendre le point d’intersection de la droite d avec la médiatrice \Delta de [OC]. Peut-on faire plus simple ?  En fait, cette construction est si simple qu’elle a été présentée dans l’épisode n°164 des Télétubbies.

Non, ce n’est pas vrai, inutile de chercher cet épisode sur Youtube !

II) Synthèse

Il faut vérifier réciproquement que le point d’intersection de la médiatrice \Delta de [OC] avec la perpendiculaire à d passant par B est bien le centre d’un cercle qui est à la fois tangent à \mathcal{C} et à la droite d. On considère le cercle \mathcal{C} de centre \Omega et de rayon r':=\Omega B.

  • Ce cercle est tangent à d. En effet, comme \Omega appartient à la perpendiculaire d alors (\Omega B) \perp d. De plus, \Omega B= r' et donc la propriété 2 nous permet d’affirmer que la droite et le cercle sont tangents.
  • Ce cercle est aussi tangent à \mathcal{C}. Pour montrer cela, d’après la propriété 1, il suffit de montrer que O \Omega = r +r'. Mais comme \Omega est situé sur la médiatrice de [OC], O \Omega = OC. Et comme \Omega, B et C sont alignés, on a donc \Omega C = OB + BC = r' + r !

Résumé de la construction

Voici ce qu’il faut retenir de notre étude précédente si, à partir d’un cercle \mathcal{C} de rayon r, tangent à une droite d, vous souhaitez construire à la règle et au compas le cercle \mathcal{C}' qui est à la fois tangent à \mathcal{C} et à la droite d en un point B donné:

  1.  Tracez la perpendiculaire à d passant par B.
  2. Placez sur cette perpendiculaire le point C, situé à une distance égale à r de B (de l’autre côté que le cercle).
  3. Tracez la médiatrice de [OC]. On appelle \Omega l’intersection de cette médiatrice avec la perpendiculaire.
  4. Tracez le cercle de centre \Omega et de rayon \Omega B.
Fun fact: j'en ai chié pour faire cette animation

Fun fact: j’en ai chié pour faire cette animation.

Bonus: valeur du rayon !

La question subsidiaire que l’on pourrait poser ici est: quelle est la valeur du rayon r' ? Eh bien nous allons la déterminer bravement, ce qui nous donnera encore une fois une jolie formule. Full_contact_I_calcul_rayonComme vous le voyez sur le schéma, il n’y a pas besoin de plus que le théorème de Pythagore. En effet, nous voyons sur la figure que:

(r+r')^2 = (r-r')^2 + AB^2

donc

r^2 + 2rr' + r'^2 = r^2 - 2rr' + r'^2 + AB^2

et après simplification et regroupement des termes,

4 rr' = AB^2

d’où

\boxed{ r' = \dfrac{AB^2}{4r} }

 

Je ne sais pas vous mais moi je trouve qu’on lui a quand même bien réglé son compte à ce problème !

Publié dans Géométrie | Tagué , , , , , , | 8 Commentaires

Le théorème de Niven

Vous vous souvenez sans doute tous de ce fameux tableau des valeurs remarquables du cosinus, vu en classe de 3ème ou de Seconde:

valeurs_remarquables_du_cosinusSans doute vous rappelez-vous que, la première fois que vous avez vu ce tableau, toutes les valeurs du cosinus paraissaient très étranges – ces racines carrées sorties de nulle part – et que seules les valeurs 0, \frac{1}{2} et 1  étaient faciles à retenir (et à visualiser sur le cercle trigonométrique).

Si vous aviez eu un professeur sadique, peut-être vous a-t-il donné un tableau encore plus complet, avec encore plus de valeurs remarquables comme ci-dessous:valeurs_remarquables_du_cosinus_version_dingue

Et vous auriez vu qu’il n’y a toujours pas de valeur simple du cosinus hormis les fameux 0, \frac{1}{2} et 1. En fait, ce n’est pas votre professeur qui était sadique mais la fonction cosinus elle-même car, selon un théorème dû au mathématicien Ivan Niven, on pourrait continuer ce tableau indéfiniment en mettant encore plus d’angles \theta mais il n’y aura toujours que trois valeurs simples du cosinus: 0, \frac{1}{2} et 1 (qui correspondent respectivement aux angles \frac{\pi}{2}, \frac{\pi}{3} et 0).

Dans cet article, nous allons tout simplement prouver cette propriété. Car en plus d’être un résultat surprenant, la démonstration de ce théorème est juste magnifique ! Quand je vous dis que les mathématiques, c’est de l’art…

Enoncé rigoureux du théorème de Niven

Il faut tout d’abord s’entendre sur ce qu’on entend par une valeur simple du cosinus. Ici, nous dirons que le cosinus a une valeur simple quand le cosinus est un nombre rationnel c’est-à-dire une fraction de deux entiers. Rappelons que l’ensemble des nombres rationnels se note \mathbb{Q}.

Il faut aussi s’entendre sur quels angles \theta on place dans le tableau des valeurs remarquables: ce seront les angles qui sont des multiples fractionnaires de \pi, c’est-à-dire les angles \theta de la forme \dfrac{a}{b}\pia et b sont des entiers. Par exemple, \dfrac{\pi}{3}, \dfrac{2\pi}{7}, \dfrac{4\pi}{13}

Voici donc l’énoncé du magnifique théorème de Niven (j’en tremble):

barreThéorème: Soit \theta \in [0, \frac{\pi}{2}] un angle de la forme \theta = \dfrac{a}{b} \pi (avec a,b \in \mathbb{N}, b\neq 0).  Alors:

Si \cos\left( \theta \right) \in \mathbb{Q} alors \cos(\theta) = 0 , \dfrac{1}{2} \text{ ou } 1

(ce qui correspond donc respectivement à \theta = \dfrac{\pi}{2}, \dfrac{\pi}{3} \text{ ou } 0).

 

Thm_de_Niven_figure

Dit autrement, le théorème de Niven dit que les seuls angles de la forme \frac{a \pi}{b} pour lesquels le cosinus (double flèches bleues sur la figure ci-dessous) est un nombre rationnel sont les angles 0, \frac{\pi}{3} et \frac{\pi}{2}

Aller, en route vers cette démonstration que je trouve si jolie car si simple ! (pour dire, je pense qu’elle est accessible à un élève de Terminale).

Nous allons décomposer cette démonstration en 3 lemmes dans lesquels nous utiliserons utilement la notion de polynômes à coefficients entiers. Qui l’eut crû ? Utiliser des polynômes pour un problème sur le cosinus…

Lemme n°1: une belle identité trigonométrique

barrelemme: Pour tout entier naturel n, et pour tout réel x

\boxed{\cos((n+1)x)= 2 \cos(nx)\cos(x) - \cos((n-1)x)}

 

Je reconnais que ce n’est pas une formule de trigo qu’on a l’habitude de voir, mais elle est sympa quand même.

Démonstration: On connaît la formule classique suivante:

\cos(A)+\cos(B) = 2 \cos(\frac{A+B}{2}) \cos(\frac{A-B}{2})

qui est bien entendu équivalente à:

\cos(A) = 2 \cos(\frac{A+B}{2}) \cos(\frac{A-B}{2})-\cos(B)

En posant A=(n+1)x et B=(n-1)x, on a donc

\cos((n+1)x) = 2 \cos(\frac{(n+1)x+(n-1)x}{2}) \cos(\frac{(n+1)x-(n-1)x}{2}) - \cos((n-1)x)

ce qui après simplification donne bien:

\cos((n+1)x) = 2 \cos(nx)\cos(x) - \cos((n-1)x)

  Lemme n°2: des "presque" polynômes de Tchebichev

A l’aide du lemme précédent et d’un raisonnement par récurrence, nous allons montrer que:

barrelemme: Pour tout entier naturel n, il existe un polynôme unitaire T_n de degré n dont les coefficients sont des nombres entiers et tel que:

\forall x \in \mathbb{R}, \,\, T_n\left(2\cos(x)\right)=2\cos(nx)

Rappelons qu’un polynôme unitaire est un polynôme dont le coefficient du terme de plus haut degré est 1. Par exemple, X^2 +1 est unitaire, mais 5X^4 -3X + 1 ne l’est pas.

Démonstration:

■ Si n=1 alors on voit immédiatement que le polynôme T_1(x)=x convient.

■ Soit n est un entier naturel non nul quelconque. On suppose que pour tout entier naturel non nul k \leq n, on ait déjà construit un polynôme T_k vérifiant les conditions énoncées dans le lemme (on fait ici ce qu’on appelle une récurrence forte). Il s’agit alors de montrer l’existence d’un polynôme T_{n+1} unitaire à coefficients entier de degré n+1 tel que T_{n+1}(2\cos(x))=2\cos((n+1)x). On distingue deux cas:

a) si n+1=2 alors il suffit de prendre T_{n+1}(x)=T_2(x)=x^2-2 car

(2\cos(x))^2 - 2= 4 \cos^2(x) - 2 =4 (\frac{1+\cos(2x)}{2}) -2 = 2\cos(2x)

(On a utilisé ici la formule dite de réduction du carré).

b) si n+1>2, alors d’après le lemme précédent, on sait que :

\cos((n+1)x) = 2 \cos(nx)\cos(x) - \cos((n-1)x)

Donc, en multipliant le tout par 2, on a:

2\cos((n+1)x) = 2\cos(nx) 2\cos(x) - 2\cos((n-1)x)

Ainsi, la condition T_{n+1}(2\cos(x)) = 2\cos((n+1)x) est équivalente à

T_{n+1}(2\cos(x)) = 2 \cos(nx) 2\cos(x) - 2\cos((n-1)x)

et donc par hypothèse de récurrence, elle est encore équivalente à:

T_{n+1}(2\cos(x))=2\cos(x) T_n(2\cos(x)) - T_{n-1}(2\cos(x))

Cela incite donc à poser:

\boxed{T_{n+1}(x)= x T_n(x) - T_{n-1}(x)}

et on voit de suite dans ce cas que T_{n+1} est de degré n+1 et à coefficients entiers. CQFD.

Remarque: Comme le nombre n-1 apparaît à un moment donné, pour pouvoir utiliser l’hypothèse de récurrence il fallait s’assurer que n-1\geq 1 c’est-à-dire n+1 \geq 3. C’est pour cela que nous avons traité le cas n+1=2 à part.

Lemme n°3: racines rationnelles d’un polynôme à coefficients entiers

Ce dernier lemme sera utile pour utiliser les polynômes T_n qu’on vient de déterminer.

barrelemme: Si P est un polynôme unitaire à coefficients entiers et s’il possède une racine qui est un nombre rationnel alors ce nombre est nécessairement entier.

Démonstration: Soit P = X^n + a_{n-1}X^{n-1} + \cdots + a_1 X + a_0 (où les a_i sont des nombres entiers) un polynôme unitaire de degré n (qu’on peut supposer strictement supérieur à 1 sinon le lemme est évident. Pourquoi ?) et soit \frac{p}{q} une racine de P (on peut toujours supposer p et q premiers entre eux). Alors P(\frac{p}{q})=0, ce qui nous donne:

(\frac{p}{q})^n + a_{n-1}(\frac{p}{q})^{n-1} + \cdots + a_1 (\frac{p}{q}) + a_0=0

En multipliant les deux membres par q^n, on a:

p^n + a_{n-1}qp^{n-1} + \cdots + a_1 q^{n-1}p + a_0q^n=0

donc:

p^n = q( a_{n-1}p^{n-1} + \cdots + a_1 q^{n-2}p + a_0q^{n-1})

donc q divise p^n, mais comme q est premier avec p, cela n’est possible que si q=\pm 1 ! Donc, le nombre \frac{p}{q} est bien un nombre entier.

Le bouquet final

Nous sommes maintenant parés pour démontrer le théorème de Niven. Soit \theta \in [0, \frac{\pi}{2}] un angle de la forme \theta = \dfrac{a}{b}\pi (a, b entiers). Quitte à multiplier le quotient \dfrac{a}{b} par 2 au numérateur et au dénominateur, on peut toujours supposer que \theta est de la forme \dfrac{2k}{m}\pi (par exemple, \frac{\pi}{3} = \frac{2\pi}{6}). Cette forme sera très utile comme vous allez le voir…

Nous savons qu’il existe un polynôme T_m unitaire à coefficients entiers tel que:

\forall x, T_m (2\cos(x) ) = 2 \cos(mx)

En particulier, si x=\theta=\frac{2k}{m}\pi alors

T_m(2\cos(\theta))=2\cos(m \frac{2k}{m}\pi)

et là, hormis Steevie Wonder, tout le monde voit la simplification arriver à des kilomètres:

T_m(2\cos(\theta))= 2\cos(2k\pi) = 2

 Le nombre 2\cos(\theta) est donc racine du polynôme unitaire à coefficients entiers P = T_m(x) - 2. Donc, si on suppose que \cos(\theta) est un nombre rationnel, alors 2\cos(\theta) est un nombre rationnel qui est racine d’un polynôme unitaire à coefficients entiers. D’après le lemme 3, il s’ensuit que 2\cos(\theta) est nécessairement un nombre entier.

Mais, on sait aussi que si \theta \in [0; \frac{\pi}{2}] alors 0 \leqslant \cos(\theta) \leqslant 1 et donc 0 \leqslant 2 \cos(\theta) \leqslant 2. Ainsi, 2\cos(\theta) est un nombre entier compris entre 0 et 2 d’où:

2 \cos(\theta) = 0, 1, \text{ ou } 2

et donc les seules valeurs simples possibles pour le cosinus sont:

\cos(\theta) = 0, \frac{1}{2} \text{ ou } 1 !

CQFD.

Je ne sais pas si je vous l’ai dit, mais je trouve cette démonstration magnifique.

Note:

La démonstration suivie ici s’inspire largement de celle postée sur ProofWiki qui elle-même s’inspire de la preuve donnée par un certain Olmsted.

Publié dans Géométrie | Tagué , , , , , , | 9 Commentaires

Tableau périodique des mathématiciens

Je me suis amusé à remplir le tableau périodique des éléments chimiques avec des noms de mathématiciens en suivant le principe suivant: pour chaque symbole chimique, j’ai placé le nom d’un mathématicien dont le nom correspond aux lettres de ce symbole. Par exemple, le symbole chimique du Gallium est Ga, ce qui fait penser à Gauss.

Ce ne fut pas simple de remplir toutes les cases, et il a parfois fallu faire des choix quand plusieurs noms de mathématiciens convenaient. J’ai essayé du plus possible de mettre le nom de mathématiciens célèbres et de grande importance (même si malgré tout certains sont peu connus, comme vous le verrez). J’ai aussi essayé de balayer la plus large période historique possible: cela va de mathématiciens de l’Antiquité jusqu’à des mathématiciens du XXème siècle. Bonus: en cliquant sur chaque case, vous atterrirez sur la page Wikipédia expliquant un théorème, un lemme ou une notion qui a été inventée ou qui porte le nom de ce mathématicien. Trêve de blablas, voici le tableau au format PDF (cliquez sur l’image pour ouvrir le fichier):

Tableau_periodique_des_mathematiciens_miniature

Note:

Rendons à César ce qui est à César: pour créer ce joli tableau périodique, je me suis inspiré du code posté par un certain dénommé Ivan Griffin.

Publié dans Inclassable | Tagué , | 14 Commentaires

Savez-vous factoriser à la mode de Fermat ?

La question de savoir factoriser un nombre entier est cruciale de nos jours: de nombreux systèmes cryptographiques (dont le fameux RSA) reposent dessus. Mais, au 17ème siècle, du temps du mathématicien Pierre de Fermat, savoir factoriser un entier n’avait absolument aucune application pratique; le seul intérêt de trouver une factorisation était éventuellement ludique (on s’amusait comme on pouvait à l’époque).

Disons-le tout de suite, savoir factoriser un entier est un problème difficile. Par exemple, si je vous donne le nombre 15, vous me direz immédiatement que c’est 3 fois 5 mais si je vous donne 2 473 859, peu d’entre vous me répondront qu’il s’agit du produit de 1039 par 2381. L’exemple que je viens de vous donner reste relativement simple (!), mais dans une lettre envoyée à Fermat en 1643, le père Mersenne (il était prêtre), lui demanda de factoriser le nombre 100 895 598 169. Rien que ça ! Quel farceur ce Mersenne… Cependant, sa blague tomba à l’eau car il reçut aussitôt une lettre de Fermat (datée du 7 Avril 1643) dans laquelle on pouvait lire ceci:

Vous me demandez si le nombre 100 895 598 169 est premier ou non, et une méthode pour découvrir, dans l’espace d’un jour, s’il est premier ou composé. À cette question, je réponds que ce nombre est composé et se fait du produit de ces deux : 898 423 et 112 303, qui sont premiers.

Impressionnant. Sans calculatrice et en moins d’un jour, Fermat a réussi à factoriser un nombre à 12 chiffres ! Mais comment Fermat a-t-il fait pour factoriser ce nombre ? Car malheureusement Fermat n’a pas donné sa méthode dans cette lettre… (certaines mauvaises langues diront qu’il était coutumier du fait, et que sa marge était aussi courte que le Pape est une femme).

Ce que l’on sait en revanche, c’est que Fermat avait développé une méthode de factorisation, dite méthode de factorisation de Fermat (original comme nom) que je vais tenter de vous expliquer ici.

Une idée simple mais brillante

Soit N un entier naturel qu’on veut factoriser. La méthode de Fermat découle de l’idée toute simple suivante: si on peut écrire N comme une différence de deux carrés N=a^2 -b^2 alors N=(a+b)(a-b). Le problème de la factorisation se ramène donc à un problème de soustraction. Par exemple, 15=4^2 - 1^2 donc 15 = (4+1) (4-1) = 5 \times 3.

Remarque: si N est un nombre impair, une telle factorisation existe toujours. En effet, si N=2n+1 alors vous pouvez vérifier que  N= (n+1)^2 - n^2. Il faut faire tout de même attention car dans ce cas nous avons a=n+1 et b=n, ce qui donne a-b=1 et a+b=2n+1=N: la factorisation obtenue est donc triviale (savoir que N=N \times 1 n’a aucun intérêt, vous en conviendrez).

Deux conditions nécessaires

Dans toute la suite, on supposera que N n’est pas un carré (car sinon, la factorisation de N est facile à trouver: c’est N = \sqrt{N} \times \sqrt{N}). Si on est capable de trouver une décomposition comme une différence de deux carrés, autrement dit si N = a^2 - b^2 alors,

1) a^2 -N est un carré
2) a \geqslant E( \sqrt{N}) +1E( \sqrt{N}) est la partie entière de \sqrt{N}.

Explication: Le 1) est évident. Pour le 2), il faut remarquer que a^2 = N + b^2 > N (strict car N n’est pas un carré) et donc a > \sqrt{N}, ce qui implique a \geqslant E( \sqrt{N}) +1.

Ces deux conditions vont nous permettre, comme vous allez le voir, de donner un algorithme de factorisation.

La méthode de factorisation de Fermat

On note toujours N le nombre à factoriser et on pose q= E(\sqrt{N}). Puisque l’idée est de trouver a et b tels que N=a^2 -b^2 et puisqu’on a vu que si a existe alors a \geqslant q+1, alors on va choisir successivement a=q+1 , a=q+2, a=q+3, … jusqu’à ce qu’il y ait un a tel que a^2 - N soit un carré. Facile, non ?

Je donne un exemple simple: supposons qu’on souhaite factoriser N= 799. On a \sqrt{799} \simeq 28,26... donc q=28.

  • On essaye avec a=q+1 = 29. On a a^2 - N = 29^2 - 799 = 43. Ce n’est pas un carré.
  • On essaye avec a=q+2 = 30. On a a^2 - N = 30^2 - 799 = 101. Ce n’est pas un carré.
  • On essaye avec a=q+3 = 31. On a a^2 - N = 31^2 - 799 = 162. Ce n’est pas un carré.
  • On essaye avec a=q+4 = 32. On a a^2 - N = 32^2 - 799 = 225 qui est un carré !

Comme 225 = 15^2, on pose b=15, et on a donc la relation a^2 - N = b^2. Ainsi, N = a^2 - b^2 = 32^2 - 15^2. On en déduit que N=(32+15) (32-15) c’est-à-dire N = 47 \times 17.

Raffinement

Dans le cas où le nombre N est très grand, le nombre d’étapes et de calculs est potentiellement très élevé. Pour que cette méthode soit utilisable d’un point de vue pratique, il va falloir minimiser le nombre de calculs, et pour cela, on va essayer de voir comment réutiliser les calculs déjà effectués au fur et à mesure. En particulier il va être possible de calculer les a^2 - N facilement.

Puisqu’on pose successivement a=q+1, a=q+2, etc. nous allons donc utiliser la notation a_k = q + k. Essayons de trouver une relation de récurrence:

a_{k+1} - N^2 = ((q+k)+1)^2 - N = (q+k)^2 + 2 (q+k) + 1 - N

En réarrangeant les termes, on a donc:

a_{k+1} - N^2 = (q+1)^2 - N + 2(q+k) + 1

Nous voyons donc que:

\boxed{ a_{k+1}^2 - N = a_k ^2 - N + 2 a_k + 1}

Il reste maintenant à voir sur un exemple pratique comment utiliser cette relation de récurrence pour exécuter la méthode de Fermat.

Un exemple donné par Fermat lui-même

Fermat avait expliqué cette méthode dans une lettre datant de 1643 et dans laquelle il expliquait comment factoriser le nombre 2 027 651 281:

Fermat explique sa méthode.

Fermat explique sa méthode.

(Cette image est extraite de: Œuvres de Fermat, publiées par les soins de MM. Paul Tannery et Charles Henry sous les auspices du Ministère de l’instruction publique. On peut trouver ce livre en ligne ici !)

Voici ce que l’exemple de Fermat donne sous forme de tableau (avec des notations modernes):

factorisation_Fermat_exemple_2027651281

Chaque nombre de la dernière colonne s’obtient en faisant la somme des deux nombres au-dessus.

Vous voyez que ce tableau est très facile à remplir car:

  • a augmente de 1 à chaque fois
  • 2a+1 augmente de 2 à chaque fois
  • a^2-N s’obtient en faisant la somme des deux cases situées au-dessus (à la manière du triangle de Pascal) et cela vient de la relation de récurrence que nous avons exhibée plus haut. Il n’y a donc aucune multiplication à faire, ni aucun carré à calculer ! (à part pour la première ligne bien sûr).

Dans l’exemple ci-dessus, on s’est arrêté dès qu’on est tombé sur un carré dans la dernière colonne: en effet, on a 1040400 = 1020² et donc, comme énoncé par Fermat dans son texte, on a

N = 45 041^2 -1020^2 = (45 041+1020)(45 041-1020) = 46 061 \times 44 021

Remarque: Comme vous l’avez sans doute constaté dans la lettre, Fermat savait directement reconnaître si un nombre n’est pas un carré, s’épargnant ainsi un calcul de racine carrée. Il utilisait la condition nécessaire suivante: si un nombre est un carré alors ses deux derniers chiffres sont 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89, ou 96 (mais attention, ce n’est pas une condition suffisante). Dans l’exemple ci-dessus, vous voyez tout de suite dans la dernière colonne que les seuls nombres qui peuvent potentiellement être des carrés sont 499 944 et 1 040 400.

Retour sur la blague de Mersenne

J’ai implémenté la méthode de Fermat en Python et pour N=100 895 598 169  (donc q=E(\sqrt{100 895 598 169}) = 317640), on trouve qu’il faudrait k=187723 étapes avant que l’algorithme se termine ! Et on a alors

a^2-N=(q+k)^2 - N = (317640+187723)^2 - 100 895 598 169 = 154496163600

qui est le carré de b=393060. Ainsi, on a

N=(a+b)(a-b) = (q+k +b) (q+k -b)

donc

N= (317640+187723+393060) \times (317640 + 187723 - 392060)

c’est-à-dire

N= 898423 \times 112303

On retrouve bien la réponse donnée par Fermat à Mersenne. Cependant, il est très peu probable que Fermat se soit tapé à la main le calcul des 187 723 étapes (sauf s’il aimait se faire mal…) et il n’a donc probablement pas utilisé cette méthode pour répondre au problème de Mersenne (mais au moins ça nous a donné une occasion de parler de cette méthode…). Mais alors, comment ce filou a-t-il donc fait, nom d’une pipe en acajou ?

Des explications possibles

Voici ci-dessous trois hypothèses possibles (la plus probable et la plus vraisemblable étant la première je pense):

Hypothèse n°1: les nombres parfaits multiples

Si on retranscrit fidèlement la correspondance de Fermat, le problème de la factorisation du nombre 100 895 598169 intervient à l’intérieur d’un problème sur les nombres parfaits multiples. Voici un extrait plus long de la lettre de Fermat à Mersenne:

La note de l'éditeur des Ouvres de Fermat contient une hypothèse possible sur la factorisation.

La note (1) de l’éditeur des Œuvres de Fermat contient une hypothèse possible sur la factorisation de 100 895 598 169.

Traduction : Ce que demandait plus globalement Mersenne à Fermat, c’est de dire si oui ou non la somme des diviseurs propres ("parties aliquotes") du nombre:

N = 214 748 364 800 000 \times 11 \times 19 \times 43 \times 61 \times 83 \times 169 \times 223 \times 331\times 379\times 601 \\  \times 757 \times 961 \times 1201 \times 7 019 \times 823 543 \times 616 318177 \times 6 561 \times 100 895 598 169

est égale à un multiple de N (les diviseurs propres sont les diviseurs de N différents de N). Une explication probable du raisonnement que Fermat aurait suivi pour factoriser 100 895 598 169 est donnée par la note de l’éditeur des Oeuvres de Fermat (de l’édition que j’ai cité plus haut dans l’article). Mais, telle qu’elle est écrite, on n’y comprend rien, donc la voici rédigée dans le fichier PDF ci-dessous :

 Comment Fermat a-t-il factorisé 100 895 598 169 ?

Il s’agit de l’explication la plus probable car elle permet de répondre en même temps aux deux questions que Mersenne posait.

Hypothèse n°2: l’astuce de calcul ad hoc

Fermat se serait rendu compte que sa méthode n’aboutirait pas rapidement et donc, plutôt que de factoriser N, il se serait dit "pourquoi ne pas factoriser un multiple de N, quitte à rediviser par ce multiple ensuite ?" Et voici ce que ce qu’il aurait peut-être fait: il aurait multiplié N par 32, ce qui donne 32 N = 3228659141408 et il se serait rendu compte que ce nombre est presque un carré. Plus précisément, 32 N +1 =3228659141409 = (1796847)^2 (rappelons que Fermat savait reconnaître rapidement si un nombre n’est pas un carré et qu’il savait extraire une racine carré sans trop de difficulté).  Ainsi,

32N = (1796847)^2 - 1 = (1796847+1) (1796847 -1) = 1796848 \times 1796846

Puis, il suffit de diviser par 32, en remarquant que le premier facteur est divisible par 16 et le deuxième est divisible par 2:

N = \dfrac{1796848 }{16} \times \dfrac{1796846}{2}

et donc on trouve bien:

N = 112 303 \times 898 423

L’idée de trouver une décomposition en différence de deux carrés d’un multiple de N est l’idée de base d’un crible moderne appelé crible quadratique, où le principe est de chercher deux nombres a et b tels que a^2 \equiv b^2 \mod[N]. On peut imaginer que Fermat avait eu l’intuition de cette méthode déjà à l’époque.

Hypothèse n°3: la méthode de Daniel Perrin

Daniel Perrin a donné une autre explication possible, mais je ne vais pas rentrer dans les détails de celle-ci (car cet article commence à devenir un peu long !). Vous pouvez lire cette explication très intéressante (qui est un raffinement de la méthode de Fermat) en annexe de ce document qu’il a posté sur sa page.

Quelques notes en guise de conclusion:

■ En pratique, la méthode de factorisation de Fermat est plutôt longue, et le nombre d’étapes nécessaires est en moyenne souvent très élevé. Elle n’est donc quasiment pas utilisée de nos jours, mais elle a donné naissance à d’autres algorithmes comme la méthode de Dixon et la très efficace méthode du crible quadratique.

■ Dans sa réponse, Fermat affirmait que 898 423 et 112 303 sont des nombres premiers. Pour le vérifier, Fermat a sans doute utilisé la méthode du crible d’Ératosthène. Par exemple, comme la racine carrée de 898 423 est  environ 947, il suffit de montrer que 898 423 n’est divisible par aucun des nombres premiers inférieurs ou égaux à 947 (en faisant une bête division euclidienne). Sachant qu’il n’y a que 161 tels nombres premiers, cela pouvait se faire à la main en l’espace d’une journée. Dans le cas de 112 303, il n’y a que 67 nombres premiers à tester.

■ Ce problème de la factorisation de N=100 895 598 169 est cité dans l’article Wikipédia sur le petit théorème de Fermat:Page_wikipedia_petit_theoreme_FermatContrairement à ce qui est suggéré, le petit théorème de Fermat n’a pas du tout été utilisé et ne permet certainement pas de donner les facteurs de la décomposition d’un nombre qui n’est pas premier ! Tout au plus il permet de montrer que N n’est pas premier mais utiliser ce théorème pour cela serait une douce folie car il faudrait montrer que:

\exists a : a^{100895598168} \not\equiv 1 \mod [100895598169]

ce qui du point de vue du calcul, serait plutôt long…. surtout si, comme Fermat, vous n’avez pas de calculatrice ! (Heureusement, de nos jours on possède de rapides ordinateurs et on peut voir en une fraction de seconde que si a=2 alors le reste n’est pas 1).

Références:

 Voici un article détaillant la note de l’éditeur qui donnait la méthode probable utilisée par Fermat.  (c’est de cet article que je me suis inspiré pour rédiger l’hypothèse n°1 et, pour ça, j’ai dû me mettre à l’italien… Faut être polyglotte pour faire des maths, je vous jure…):
Giuseppe Palamà – Su di una regola di Fermat per la fattorizzazione dei numeri e su di una sua questione relativa alle parti aliquote.


 Pour l’aspect historique de l’étude des nombres multiples parfaits (y compris le résumé des correspondances entre Fermat, Descartes, Mersenne et d’autres), vous pouvez consulter le chapitre I de:
L.E. Dickson – History of the Theory of Numbers, Volume I: Divisibility and Primality

Publié dans Arithmétique | Tagué , , , , , , | 12 Commentaires