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

Le petit monde de Pac-man

En 1980 sortait un des jeux les plus mythiques de l’univers des jeux vidéos: Pac-man. Le principe de ce jeu est plutôt simple: vous incarnez une personnage qui ressemble à une petite pastille jaune et vous vous déplacez dans un labyrinthe dans lequel sont disposées des petites gommes que vous devez toutes gobé sans jamais vous faire attraper par 4 terrifiants fantômes. Bon, inutile que je décrive plus ce jeu mythique car vous y avez sans doute déjà joué. Si ce n’est pas le cas, vous allez réparer toute de suite cette faute grave en jouant à la version que Google avait créé et mise sur sa page d’accueil à l’occasion de l’anniversaire des 30 ans de ce jeu (attention, ce jeu est plus addictif que Flappy bird et 2048 réunis).

Ecran de jeu du tout premier Pac-Man (image issue de l'article Pac-Man Wikipédia anglais)

Écran de jeu du tout premier Pac-Man (image issue de l’article Pac-Man Wikipédia anglais)

Mais quel est le rapport entre ce jeu vidéo et les mathématiques ? C’est simple: tel M. Jourdain, Pac-man fait de la topologie sans le savoir.

Téléportation

Il faut se souvenir qu’une des caractéristiques du déplacement de Pac-Man dans le labyrinthe, c’est que sur la gauche de l’écran de jeu, il y a un tunnel qui, lorsqu’il est emprunté par Pac-Man, le téléporte sur la droite de l’écran du jeu (et vice-versa) ! Pac-man_deplacement_teleportationD’un point de vue du jeu, cela donne plus de possibilités d’échapper aux fantômes, mais d’un point de vue mathématique, cette propriété nous permet d’affirmer que Pac-man vit sur un cylindre ! (ou sur un rouleau de PQ, c’est selon…). Afin de comprendre ce fait, nous allons d’abord donner une explication visuelle, puis une explication mathématique dans laquelle nous ferons un peu de topologie.

Explication visuelle

Étant donné que le bord gauche de l’écran est directement relié au bord droit de l’écran, on peut donc les identifier. Imaginez donc que l’écran soit une feuille de papier, et imaginez qu’on mette de la colle (segments verticaux bleus ci-dessous) sur le bord gauche et sur le bord droit de cette feuille puis qu’on colle le bord gauche sur le bord droit en les superposant. Voici ce qu’on obtiendrait:

Pac-man_recollement_cylindre_figureAinsi, après collage des extrémités, on se rend compte que Pac-man se déplace bel et bien sur un cylindre !

Explication mathématique

L’explication mathématique est moins évidente et requiert, comme dit plus haut, quelques notions de topologie que je vais essayer d’esquisser ici. Une démonstration rigoureuse du fait que Pac-Man vit sur un cylindre est disponible plus bas dans un fichier PDF pour les plus courageux d’entre vous.

Pour montrer que Pac-man vit sur un cylindre, on va procéder en deux étapes:
1) On commence par définir un ensemble qui représente le monde de Pac-man, c’est-à-dire dans lequel le bord gauche et le bord droit sont "identiques".
2) On montre ensuite que cet ensemble est semblable à un cylindre du point de vue topologique. Une autre façon de le dire est qu’on peut obtenir un cylindre à partir de cet ensemble juste en le déformant "continûment".

Étape n°1: On commence par modéliser l’écran sur lequel se déplace Pac-man en considérant qu’il s’agit du carré X = [0,1] \times [0,1]. Pour exprimer mathématiquement le fait que les points du bord gauche sont identiques à ceux du bord droit, on utilise la notion de relation d’équivalence. On définit sur X la relation notée \sim telle que pour tout y \in [0,1], (0,y) \sim (1,y):

blabla

Les points P et Q sont équivalents. L’ensemble {P,Q} correspond donc à un point de l’ensemble quotient.

Le monde de Pac-man est alors l’ensemble (dit quotient) des classes d’équivalences pour cette relation, c’est-à-dire l’ensemble qu’on note X / \!\sim dont chaque élément est un paquet qui regroupe tous les points du carré X qui sont équivalents entre eux. Dans l’ensemble quotient, les points du bord gauche et du bord droit sont donc confondus.

Étape n°2: L’espace quotient X/ \! \sim est muni d’une topologie naturelle, appellée topologie quotient. Muni de cette topologie, on peut montrer que cet espace est alors compact.

On définit le cylindre \mathcal{C} comme étant l’ensemble des points (x,y,z) de \mathbb{R}^3 tels que x^2+z^2 =1 et y \in [0,1] qu’on munit de la topologie induite par celle de \mathbb{R}^3.

cylindre_pac-man

Nous avons donc deux objets: d’un côté le monde de Pac-man X / \! \sim et de l’autre un cylindre \mathcal{C}. Il s’agit de montrer que ces deux objets sont identiques d’un point de vue topologique (on dit homéomorphes). Pour cela, il faut montrer qu’il existe une bijection de l’un dans l’autre qui est continue et dont l’application inverse est elle aussi continue (on parle d’homéomorphisme). On définit la fonction \widehat{f} suivante:

\begin{array}{crcl}  \widehat{f}: & X / \! \sim & \longrightarrow & \mathcal{C}\\  & [(x,y)] & \mapsto & (\cos(2 \pi x), y, \sin(2 \pi x))  \end{array}

[(x,y)] représente la classe d’équivalence de (x,y). On peut montrer que \widehat{f} est bijective et continue sans trop de difficultés. Pour montrer que \widehat{f} est bicontinue, c’est-à-dire que son inverse \widehat{f}^{-1} est aussi continue, on utilise le lemme classique suivant:

Soit g: E \longrightarrow F une application continue. Si E est un espace compact et si F est un espace séparé, alors l’image d’un fermé de E par g est un fermé de F.

Comme X/ \! \sim est compact et que \mathcal{C} est séparé, alors l’image de tout fermé par \widehat{f} est un fermé. Puisque \widehat{f} est bijective, cela veut dire que l’image réciproque d’un fermé par \widehat{f}^{-1} est encore un fermé et donc que \widehat{f}^{-1} est continue ! Ainsi, \widehat{f} est un homéomorphisme et le monde de Pac-man est bien homéomorphe à un cylindre.

Pour les lecteurs familiers avec cette si belle branche des mathématiques qu’est la topologie (les autres, laissez tomber… je vous aurai prévenus !), les détails de cette preuve sont disponibles dans le fichier suivant:

Démonstration mathématique du fait que Pac-man vit sur un cylindre

Variante

On pourrait imaginer que lorsque Pac-man traverse le bord gauche de l’écran, il soit téléporté sur le bord droit et qu’en plus il soit renversé (symétrie centrale par rapport au centre de l’écran). Voici ce qu’on aurait (j’ai ajouté un oeil à Pac-man pour mieux voir le renversement):variante_Pac-man_renversePour représenter cela schématiquement, on mettra des flèches en sens opposés sur chacun des bords :Mobius_plat_Pac-manLorsqu’on colle le bord gauche sur le bord droit de façon à ce que les flèches se superposent dans le même sens, on obtient alors un ruban de Möbius !Ruban_de_Mobius_Pac-manD’un point de vue mathématique, cela reviendrait à définir sur le carré X = [0,1] \times [0,1] la relation d’équivalence telle que pour tout y \in [0,1], (0,y) \sim (1, 1-y). On peut montrer que l’ensemble quotient obtenu est bel et bien homéomorphe à un ruban de Möbius.

Pac-man change de monde

Il y a eu de nombreuses versions de Pac-man, mais en 2007, le créateur du Pac-man originel développa une suite qui s’appelle Pac-man Championship Edition.

Pac-man_Championship_edition

La particularité de cette nouvelle version est, qu’en plus d’être téléporté sur le bord droit quand il traverse le bord gauche, Pac-man est téléporté sur le bord du haut quand il traverse le bord du bas. Voici la représentation de l’écran avec les identifications des bords de cette nouvelle version de Pac-man:

Tore_plat_Pac-manOn peut montrer que ce monde est alors équivalent (homéomorphe) à un tore:Tore_Pac-manPac-man a donc changé de monde: il ne vit désormais plus sur un cylindre, mais sur un tore !

Remarque: Pour voir géométriquement que ce monde est bien un tore, faites comme ce qu’on avait fait plus haut pour le cylindre: imaginez que le carré est une feuille de papier, collez les flèches bleues l’une sur l’autre, ce qui donne un cylindre, puis collez ensuite les flèches rouges l’une sur l’autre et vous obtenez bien un tore:

Animation extraite de l'article Wikipedia anglais sur le tore.

Animation extraite de l’article Wikipedia anglais sur le tore.

Autres variantes

On peut s’amuser à imaginer toutes les possibilités de téléportation sur l’écran. Les voici résumées ci-dessous, avec pour chaque configuration l’objet topologique qui lui est homéomorphe:

Relations_possibles_sur_le_carre_Pac-man(Je n’ai pas pu/su dessiner le plan projectif réel, ne m’en voulez pas, mais vous pouvez le visualiser ici… déjà que j’en ai chié avec le ruban de Möbius et la bouteille de Klein, même en m’inspirant d’un code déjà existant…)

Les jeux vidéo et la topologie

Il n’y a pas que Pac-man qui vit sur un cylindre ou un tore. Il y a de nombreux jeux vidéos dans lesquels les bords de l’écran communiquent entre eux. Par exemple, dans le (très ancien) jeu Asteroïds, le monde est un tore. Dans le jeu super Mario Bros 2, il y a certains tableaux verticaux où les bords gauche et droit de l’écran communiquent: ce sont donc des cylindres (regardez par exemple les 25 premières secondes de cette vidéo. On voit clairement Luigi passer de gauche à droite comme Pac-Man !).  Dans le jeu de course F-Zero GX, l’un des circuits est un ruban de Möbius !

Il y a de nombreux autres exemples de mondes cylindriques, toriques ou sphériques dans l’univers du jeu vidéo mais, à ma connaissance, il n’y a pas encore eu de jeu vidéo qui se déroule sur une bouteille de Klein…

lrWkH

A quand un jeu vidéo qui se déroule sur une bouteille de Klein ?

Pour finir, une petite anecdote: dans le jeu vidéo Minecraft, l’écran d’accueil comporte une phrase différente à chaque lancement. Voici ce qu’on peut lire parfois:

minecraftC’est amusant car d’un point de vue topologique, le monde de Minecraft n’est pas homéomorphe à une sphère puisque, par exemple, il existe des trous (cavernes, etc.) !

Publié dans Géométrie, Topologie | Tagué , , , , | 2 Commentaires

Une visualisation géométrique et une démonstration de l’irrationalité de la racine carrée de 2

Dans un repère d’origine le point O, tracez le cercle de diamètre 3 unités passant par O comme ci-dessous:

construction1_racine_de_2Placez le point H de coordonnées (1,0) puis tracez le segment partant de H, perpendiculaire à l’axe des abscisses qui rejoint le cercle. On note A le point du cercle obtenu:

construction2_racine_de_2Enfin, tracez la droite (OA) et constatez avec une certaine surprise qu’elle ne coupe aucun point de coordonnées entières (hormis (0,0) évidemment). Donc \sqrt{2} est irrationnel.

construction_droite_racine_de_2

La droite (OA) ne passe par aucun point de la grille, ce qui correspond au fait que \sqrt{2} est irrationnel. Le point (5,7) est très proche, mais comme on le voit sur le zoom, il n’est pas sur la droite (cela s’explique par le fait que le rapport 7/5 = 1,4 est proche de \sqrt{2})

Être à la hauteur

La première chose qu’il faut expliquer, c’est que le segment rouge a pour longueur \sqrt{2}.

hauteur_explication_racine_de_2En effet, le triangle OAC est inscrit dans le cercle et un de ses côtés est un diamètre de ce cercle. Il est donc rectangle et le segment rouge est la hauteur issue de l’angle droit de ce triangle. On sait alors qu’on a la relation HA^2 = HO \times HC donc HA^2 = 1 \times 2 = 2, ce qui donne HA = \sqrt{2}.

propriete_hauteur_triangle_rectangle

Dans un triangle rectangle, on peut calculer facilement la hauteur issue de l’angle droit.

Ainsi, le vecteur \overrightarrow{OA} a pour coordonnées {1 \choose \sqrt{2}} et donc une équation de la droite (OA) est y= \sqrt{2} \, x !

Pythagore et Thalès en guest stars

L’idée de la démonstration qui va suivre m’est venue du constat suivant: si on suppose que \sqrt{2} est rationnel alors il existe deux nombres entiers naturels a et b qu’on peut supposer premiers entre eux (important pour la fin !) tels que \sqrt{2} = \dfrac{b}{a}, ce qui s’écrit encore b= \sqrt{2} \, a et donc il existe un point de coordonnées entières (a,b) qui appartient à la droite d’équation y=\sqrt{2} \, x ! Si on suppose donc qu’un tel point de coordonnées entières existe sur cette droite, alors on est dans la situation géométrique suivante (la figure est fausse évidemment, elle est juste schématique):

Si_racine_de_2_etait_rationnel

D’après le théorème de Thalès, on a :

\dfrac{OA}{OM} = \dfrac{AH}{MN}

On sait que AH=\sqrt{2} et MN=b. De plus, d’après le théorème de Pythagore:

\begin{cases} OA = \sqrt{1^2 + (\sqrt{2})^2} =\sqrt{3} \\  OM = \sqrt{a^2 + b^2} \end{cases}

On en déduit donc que:

\dfrac{\sqrt{3}}{\sqrt{a^2+b^2}} = \dfrac{\sqrt{2}}{b}

ce qui s’écrit aussi \sqrt{3} \, b = \sqrt{2} \sqrt{a^2+b^2}. En prenant le carré de cette égalité, on a ainsi la relation suivante:

3 b^2 = 2(a^2+b^2)

Un peu d’arithmétique en guise de conclusion

Comme 3 est premier avec 2, et comme 3 divise 2(a^2+b^2), c’est que 3 divise a^2+b^2 (lemme de Gauss). Pour trouver une contradiction, nous allons étudier tous les restes possibles de l’expression a^2+b^2 modulo 3. Par exemple, si a \equiv 1 \mod [3] et b \equiv 2 \mod [3] alors a^2+ b^2 \equiv 1^2 + 2^2 = 5 \equiv 1 \mod [3]. Voici dans le tableau suivant toutes les possibilités de résultat pour a^2 + b^2 \mod [3]:

\begin{array} {c|c|c|c|}  a / b & 0 & 1 & 2 \\ \hline  0 & 0 & 1 & 1 \\ \hline  1 & 1 & 2 & 2 \\ \hline  2 & 1 & 2 & 2 \\ \hline  \end{array}

On se rend compte que la seule possibilité pour que a^2+b^2 \equiv 0 \mod [3] est a \equiv 0 \mod [3] et b \equiv 0 \mod [3] ce qui entraîne que a et b sont tous les deux divisibles par 3, mais cela contredit le fait qu’ils sont premiers entre eux…

Amusante cette preuve, non ?

Note: pour les plus érudits d’entre vous, vous savez que si un nombre premier p divise une somme de deux carrés et si p est congru à 3 modulo 4 alors a et b sont nécessairement divisibles par p. Ici, il est clair que p=3 est congru à 3 modulo 4…

Fignolage

Si on analyse cette preuve, on se rend compte que ce qui est important est la relation 3b^2 =2(a^2+b^2), mais en développant et réduisant cette expression, on voit qu’elle est équivalente à b^2=2 a^2. On aurait donc très bien pu montrer  l’irrationalité de \sqrt{2} de la manière plus directe suivante:



Si on suppose qu’il existe a et b premiers entre eux tels que \sqrt{2}=\frac{b}{a} alors en prenant le carré de cette expression, on obtient 2= \frac{b^2}{a^2} c’est-à-dire b^2=2 a^2. En ajoutant 2b^2 des deux côtés, on obtiendrait 3b^2=2(a^2+b^2) ce qui, comme 3 est premier avec 2, entraînerait que 3 divise a^2+b^2. Or, les restes possibles de a^2+b^2 modulo 3 sont:

\begin{array} {c|c|c|c|}  a / b & 0 & 1 & 2 \\ \hline  0 & 0 & 1 & 1 \\ \hline  1 & 1 & 2 & 2 \\ \hline  2 & 1 & 2 & 2 \\ \hline  \end{array}

et donc, on voit que si a^2+b^2 \equiv 0 \mod [3] alors nécessairement, a et b sont divisibles par 3, ce qui contredit le fait qu’ils sont premiers entre eux.



Pourquoi la géométrie ?

Alors, à quoi nous a servi la géométrie ici, puisqu’on peut faire une démonstration encore plus courte juste en ajoutant les 2b^2 ? D’un point de vue formel, à rien. Mais d’un point de vue de l’intuition, je n’aurais jamais eu l’idée d’ajouter ces 2b^2 dans b^2=2 a^2 pour avoir 3b^2=2(a^2+b^2), alors que les théorèmes de Thalès et de Pythagore faisaient apparaître naturellement cette expression.

Et en plus, la géométrie nous a permis d’avoir une belle interprétation du fait que \sqrt{2} est irrationnel: le fait qu’une certaine droite construite à la règle et au compas ne passe jamais par des points de coordonnées entières !

P.S: Je n’ai jamais vu nulle part cette démonstration utilisant le fait que 3 divise une somme de carrés, donc si vous avez une référence à ce sujet, n’hésitez pas à la poster dans les commentaires !

Publié dans Arithmétique, Géométrie, Nombres | Tagué , , , , | 6 Commentaires