Harmonique, nique, nique…

Ce matin, Dominique, routier de son métier, part d’une ville A et doit rejoindre une ville C. Pour cela, son itinéraire le fait passer par une ville B qui est à la même distance de la ville A que de la ville C.

L’histoire ne dit pas ce que transporte Dominique dans son camion… (Source: Wikipédia)

Lors de la première partie de son trajet allant de A à B, Dominique (nique, nique) roule doucement (sans doute était-il mal réveillé) et effectue le trajet de la ville A à la ville B à une vitesse de 60km/h. Arrivé à la ville B, Dominique (nique, nique) se rend compte qu’il est en retard et décide de rouler plus vite: bravant les limitations de vitesse et les forces de l’ordre, Dominique (nique, nique la police) effectue alors le trajet de la ville B à la ville C à une vitesse de 100 km/h.

Quelle était la vitesse moyenne de Dominique sur la totalité de son trajet, c’est-à-dire de la ville A à C ?

Si vous avez répondu que la vitesse moyenne de Dominique est de 80km/h, vous vous êtes malheureusement trompé car Dominique a roulé en moyenne à 75km/h. Pour l’anecdote, Dominique fut fier de dire au juge qu’il avait roulé seulement à 75km/h en moyenne, soit en dessous de la limite des 80km/h autorisés sur les routes nationales.

On the road again

Si vous ne saisissez toujours pas pourquoi il a roulé à 75km/h de moyenne pour aller de la ville A à la ville C (et il n’y a pas de honte à avoir car cela n’a rien d’intuitif), faisons les calculs pour comprendre. Attention, les calculs suivants demandent un tout petit peu de technique (nique, nique) mais pas de panique (niq… OK, on a compris).

Notons d la distance séparant la ville A de la ville B, qui est aussi la distance séparant la ville B de la ville C. On note respectivement t_1 et t_2 les temps mis par Dominique pour aller de la ville A à la ville B et de la ville B à la ville C.

Je suppose que vous vous souvenez parfaitement de la formule donnant la vitesse v moyenne en fonction de la distance d parcourue et du temps t pour la parcourir:

v = \dfrac{d}{t}

Puisqu’il a roulé à 60 km/h de moyenne entre la ville A et la ville B, on a donc 60 = \dfrac{d}{t_1}. De même, pour le trajet entre la ville B et la ville C, on a l’égalité 100 = \dfrac{d}{t_2}. En inversant, on a donc les relations t_1 = \dfrac{d}{60} et t_2 = \dfrac{d}{100}.

Maintenant, intéressons-nous à la totalité du trajet. La distance totale parcourue est d+d = 2d. Le temps total mis est t_1 + t_2. La vitesse moyenne v pour aller de la ville A à la ville C est

v = \dfrac{\text{distance totale}}{\text{temps total}} = \dfrac{2d}{t_1+t_2} = \dfrac{2d}{\dfrac{d}{60} + \dfrac{d}{100}} = \dfrac{2}{\dfrac{1}{60} + \dfrac{1}{100}}

Je suppose aussi que vous savez qu’un dénominateur commun à 60 et 100 est 300 (je suppose quand même pas mal de choses sur mes lecteurs !), ce qui donne

v = \dfrac{2}{\dfrac{5}{300} + \dfrac{3}{300}} = \dfrac{2}{\dfrac{8}{300}} = 300 \times \dfrac{2}{8} =  75

J’espère que cela vous convainc définitivement que la vitesse moyenne de notre zélé routier n’était pas de 80km/h mais de 75km/h.Moyenne harmonique

Dans le cas général où les vitesses v_1 et v_2 des deux trajets sont quelconques, on peut démontrer de la même manière que la vitesse moyenne v est donnée par la formule :

\boxed{ v = \dfrac{2}{\dfrac{1}{v_1} + \dfrac{1}{v_2}} }

Ce nombre s’appelle la moyenne harmonique des nombres v_1 et v_2. En général, ce nombre est différent de la moyenne simple \dfrac{v_1 + v_2}{2} qu’on appelle aussi moyenne arithmétique.

Par exemple, si au début vous avez répondu que la vitesse moyenne de Dominique est de 80km/h, c’est probablement parce que vous avez fait une moyenne arithmétique: \dfrac{60 + 100}{2} = 80.  Le cas de Dominique illustrait donc que, parfois, la moyenne arithmétique ne permet pas de calculer la valeur d’une moyenne et que, dans le cas d’une vitesse moyenne de deux vitesses sur des trajets de même longueur, il faut utiliser une moyenne harmonique.

Lien entre moyenne harmonique et moyenne arithmétique

Bien qu’elles ne soient en général par égales, les moyennes harmoniques et arithmétiques sont tout de même liées par une jolie relation que nous allons voir.

Avant cela, notons qu’on peut calculer la moyenne harmonique d’autant de nombres que l’on veut. Par définition, la moyenne harmonique H(x_1, x_2, \cdots, x_n) de n nombres x_1, x_2, \cdots, x_n est

H(x_1, x_2, \cdots, x_n) =\dfrac{n}{\dfrac{1}{x_2} + \dfrac{1}{x_2} + \cdots + \dfrac{1}{x_n}}

Par analogie, nous noterons

A(x_1,x_2, \cdots, x_n) = \dfrac{x_1+x_2+\cdots+x_n}{n}

la moyenne arithmétique de ces nombres. On voit alors immédiatement que

H(x_1, x_2, \cdots, x_n) = \dfrac{1}{A\left( \frac{1}{x_1}, \frac{1}{x_2}, \cdots, \frac{1}{x_n}\right) }

Autrement dit, la moyenne harmonique de n nombres est égale à l’inverse de la moyenne arithmétique de leurs inverses. C’est pas beau ça ?

On comprend donc un peu mieux dans quels cas utiliser la moyenne harmonique: dans des phénomènes où les grandeurs sont des quotients et qu’on souhaite déterminer un rapport moyen.

Problèmes avec des moyennes harmoniques

Maintenant qu’on sait mieux ce que représente une moyenne harmonique, j’aimerais vous présenter deux petits problèmes amusants qui la font intervenir. N’hésitez pas à essayer de les résoudre par vous-même ou bien à les proposer à votre entourage pour voir les réponses qu’on vous donne.

Le problème des peintres

Supposons qu’on ait un mur à peindre. Quatre peintres s’affairent à la tâche (d’ailleurs, un des quatre peintres est Dominique, effectuant une peine de travaux d’intérêt général, mais peu importe). Le 1er peintre pourrait peindre le mur entier tout seul en 6 heures. Le second peintre pourrait peindre tout le mur en 3 heures. Le troisième pourrait peindre tout le mur en 2 heures et le quatrième pourrait le faire en 1 heure (toujours aussi rapide ce Dominique). Si les 4 peintres peignaient ce mur en même temps, combien de temps mettraient-ils ?

Carré blanc sur fond blanc par Kasimir Malevitch (Source: Wikipédia)
Combien de temps a-t-il fallu à Kasimir Malevitch pour peindre un mur blanc en blanc ?

Tout le monde a envie de répondre \dfrac{6+3+2+1}{4} = \dfrac{12}{4} = 3 heures. Tout le monde.  Sauf vous.

D’une part, parce que vous comprenez tout de suite que s’il y a un peintre capable de peindre le mur en 1 heure, le résultat ne peut pas être supérieur à 1. D’autre part, car vous êtes érudit à présent : vous savez ce qu’est une moyenne harmonique (et je suis fier de vous !).

Si on note S la surface à peindre et v_1 = \dfrac{S}{6}, v_2 = \dfrac{S}{3}, v_3 = \dfrac{S}{2} et v_4 = \dfrac{S}{1} les vitesses de peinture des 4 peintres, alors la vitesse moyenne est:

v = \dfrac{4}{ \dfrac{1}{v_1} + \dfrac{1}{v_2} + \dfrac{1}{v_3} + \dfrac{1}{v_4}} = \dfrac{4}{\dfrac{S}{6} + \dfrac{S}{3} + \dfrac{S}{2} + \dfrac{S}{1}} = \dfrac{4}{S \times \dfrac{12}{6}} = \dfrac{2}{S}

Attention à l’interprétation: cela signifie que si ces 4 peintres peignaient chacun successivement 4 murs identiques, alors il faudrait en moyenne à un peintre seul une vitesse de v = \dfrac{2}{S} pour peindre ces 4 murs, ce qui donne un temps t = S \times v = 2 heures pour peindre ces 4 murs. Par conséquent, il faudrait \dfrac{2}{4} = 0,5 heure à ce peintre moyen pour peindre un seul mur.

Autrement dit, si les 4 peintres peignaient un seul mur tous en même temps, cela leur prendrait une demi-heure. On aurait pu trouver ce résultat directement en calculant la moyenne harmonique des temps, qu’on aurait divisée par 4:

\dfrac{1}{4} \times \dfrac{4}{\dfrac{1}{6} + \dfrac{1}{3} + \dfrac{1}{2} + \dfrac{1}{1}} =  \dfrac{1}{\dfrac{2}{12} + \dfrac{4}{12} + \dfrac{6}{12} + \dfrac{12}{12}} = \dfrac{1}{\dfrac{24}{12}} = 0,5

Ce qui est bien, c’est que ce genre de problème se multiplie à l’infini: par exemple, si une poule pond 1 œuf tous les 2 jours et une autre poule pond 1 œuf tous les 3 jours, en moyenne, combien d’œufs pondent-elle à elles deux par jour ?

Le problème des échelles qui se croisent

Voici un deuxième exemple amusant où intervient une moyenne harmonique. Deux échelles sont posées dans un couloir (devinez qui les a posées là ? Oui, c’est bien lui…). La première échelle touche le mur de gauche à une hauteur de 1,5 mètre. L’autre échelle touche le mur de droite à une hauteur de 2,5 mètre. A quelle hauteur les deux échelles se croisent-elles ?Il s’agit ici d’un problème géométrique, où donc se cache la moyenne harmonique me direz-vous ? Pour le découvrir, nous allons nous aider du théorème de Thalès et des notations suivantes: Dans le triangle ABD, on a \dfrac{NM}{AB} = \dfrac{DN}{DA} c’est-à-dire \dfrac{h}{1,5} = \dfrac{\ell_2}{\ell}. Ainsi, \ell_2 = \ell \times \dfrac{h}{1,5}.

De même dans le triangle ACD, on a \dfrac{NM}{CD} = \dfrac{AN}{AD} donc \dfrac{h}{2,5} = \dfrac{\ell_1}{\ell} d’où \ell_1 = \ell \times \dfrac{h}{2,5}.

Comme \ell_1 + \ell_2 = \ell, on a donc \ell \times \dfrac{h}{2,5} + \ell \times \dfrac{h}{1,5} = \ell. Par conséquent, \dfrac{h}{2,5} +  \dfrac{h}{1,5} = 1 donc

\boxed{ h = \dfrac{1}{\dfrac{1}{1,5} + \dfrac{1}{2,5}}}

Autrement dit, la hauteur à laquelle se croisent les échelles est la moitié de la moyenne harmonique des hauteurs atteintes par les échelles sur les murs du couloir. Un simple calcul donne alors h = 0,9375 mètre.

D’autres moyennes ?

Outre les moyennes harmonique et arithmétique, il existe une troisième  moyenne dont je n’ai pas parlé dans cet article, qu’on appelle moyenne géométrique. Vous ne la connaissez pas ? Ne m’obligez pas à écrire un article qui s’appellerait « Géométrique, trique, trique »…

Sources

Publicités
Publié dans Statistiques | Tagué , , , , , , , , | 5 commentaires

Galilée et les nombres impairs

Formez la somme des quatre premiers nombres impairs: 1+3+5+7=16. Faites de même avec la somme des quatre nombres impairs suivants: 9+11+13+15=48. Calculez alors la fraction obtenue en divisant la première somme par la seconde:

\dfrac{1+3+5+7}{9+11+13+15}= \dfrac{16}{48}

Le résultat est donc égal à 1/3. Magique, non ? Hum, non pas vraiment. Pas encore.

Recommencez ce que vous venez de faire avec, non pas la suite des quatre premiers entiers impairs et des quatre suivants, mais avec la suite des cinq premiers entiers impairs et des cinq suivants. Cela donne:

\dfrac{1+3+5+7+9}{11+13+15+17+19}= \dfrac{25}{75} = \dfrac{1}{3}

et on constate qu’on retrouve \dfrac{1}{3}. Vous pouvez même essayer avec autant de termes que vous souhaitez, cela marchera encore:

\dfrac{1}{3} = \dfrac{1+3}{5+7} = \dfrac{1+3+5}{7+9+11} = \dfrac{1+3+5+7}{9+11+13+15} =\cdots

Autrement dit, il semblerait que la somme des n premiers entiers impairs soit toujours trois fois inférieure à la somme des n premiers entiers impairs suivants.

« L’important, c’est pas la chute… »

Ce résultat amusant, que vous venez peut-être de découvrir, est connu depuis au moins 400 ans (!) car il a été découvert par Galilée en 1615, alors qu’il travaillait sur la chute des corps.

Exprimée mathématiquement, voici ce que dit le la propriété trouvée par Galilée:

Pour tout entier naturel n \geqslant 1,

\dfrac{1+3+\cdots + (2n-1) }{(2n+1) + (2n+3) + \cdots + ( 2(2n-1)+1)} = \dfrac{1}{3}

Il existe une jolie preuve visuelle de ce résultat, que je ne vais pas commenter (puisqu’elle est visuelle !) et que voici:

Source: Nelsen, Roger B., Proof without Words: On a Property of the Sequence of Odd Integers (Galileo, 1615).

Une autre démonstration, plus calculatoire, est basée sur un résultat bien connu, à savoir que la somme des n premiers entiers impairs est égale à n^2 (voir un très vieil article de ce blog à ce sujet… ah, nostalgie) c’est-à-dire:

1+3+\cdots+(2n-1)=n^2

D’autre part, pour trouver la somme des n nombres impairs suivants, il suffit de faire la somme des 2n premiers nombres impairs moins la somme des n premiers nombres impairs:

(2n+1) + \cdots + (2(2n-1)+1) = \left[ 1+3+\cdots + (2(2n-1)+1) \right] - \left[ 1+3+ \cdots + (2n-1)\right]

c’est-à-dire

\begin{array}{rcl} (2n+1) + (2n+3) + \cdots + (2(2n-1)+1) &=& (2n)^2 - n^2 \\ &=& 4n^2 - n^2 \\ &=& 3n^2 \end{array}

On en déduit alors que:

\dfrac{1+3+\cdots + (2n-1) }{(2n+1) + (2n+3) + \cdots +  ( 2(2n-1)+1)} = \dfrac{n^2}{3n^2} = \dfrac{1}{3}

Faites comme Galilée

Après avoir lu le résultat de Galilée, vous vous êtes peut-être demandé si cela marchait aussi avec les entiers pairs. Malheureusement, cela ne fonctionne pas du tout, car, par exemple,

\dfrac{0}{2} = 0       \dfrac{0+2}{4+6} = \dfrac{1}{5}       \dfrac{0+2+4}{6+8+10} = \dfrac{1}{4}

Nous allons donc nous poser une question un peu plus générale: quelles sont les suites arithmétiques dont la somme des n premiers termes divisée par la somme des n termes suivants est constante ? Pour cela, considérons une suite arithmétique (u_n) de raison r telle que la somme des n premiers termes divisée par la somme des n termes suivants soit toujours constante c’est-à-dire telle que pour tout entier n,

\dfrac{u_0+u_1+\cdots+u_{n-1}}{u_n + u_{n+1} \cdots + u_{2n-1}} = k

Avant de continuer, rappelons un petit résultat utile sur la somme des termes d’une suite arithmétique:

Si (u_n) est une suite arithmétique, la somme de n termes consécutifs de cette suite est égale à n fois la moyenne du premier et du dernier terme.

Autrement dit, u_p + u_{p+1} + \cdots + u_{p+n-1} = n \times \dfrac{u_p + u_{p+n-1}}{2}.

Grâce à ce résultat, on peut donc écrire que

\begin{array}{rcl} \dfrac{u_0+u_1+\cdots+u_{n-1}}{u_n + u_{n+1} + \cdots + u_{2n-1}} &=& \dfrac{n \times \dfrac{u_0+u_{n-1}}{2}}{ n \times \dfrac{u_n + u_{2n-1}}{2}} \\[20pt] &=& \dfrac{u_0 + u_{n-1}}{u_{n}+u_{2n-1}} \end{array}

Comme la suite (u_n) est arithmétique de raison r, on sait alors que u_n = u_0 + n \times r. Ainsi,

\begin{array}{rcl} \dfrac{u_0+u_1+\cdots+u_{n-1}}{u_n + u_{n+1} + \cdots + u_{2n-1}} &=& \dfrac{u_0 + u_{n-1}}{u_{n}+u_{2n-1}} \\[20pt] &=& \dfrac{u_0 + u_{0}+ (n-1) \times r }{u_{0} + n \times r + u_{0} + (2n-1) \times r}\\[20pt] &=& \dfrac{2u_0 + (n-1) r}{ 2u_0 + (3n-1) r} \end{array}

A partir de là, on voit que le quotient de la somme des n premiers termes par  la somme des n termes suivants sera constant s’il existe un nombre k tel que pour tout n,

\dfrac{2u_0 + (n-1) r}{ 2u_0 + (3n-1) r} = k

Cette relation est équivalente à

2u_0 + (n-1)r = k(2u_0 + (3n-1)r) \iff 2u_0 (1-k) =r ( (3k-1)n + 1 - k)

Autrement dit, si le quotient est toujours constant, alors la raison de la suite (u_n) doit être égal à r = \dfrac{2u_0 (1-k)}{(3k-1)n - k + 1}.

Comme la raison de cette suite est une constante, elle ne dépend donc pas de n, ce qui impose la condition 3k-1 = 0 c’est-à-dire k = \dfrac{1}{3}.

A ce stade, on peut donc affirmer que si la somme des n premiers termes d’une suite arithmétique divisée par la somme des n termes suivants est constante, alors cette constante est nécessairement \dfrac{1}{3}, comme dans la relation de Galilée !

D’autre part, comme k = 1/3, la raison de cette suite doit alors être

r = \dfrac{2u_0 (1- 1/3) }{ (3 \times (1/3) - 1) n + 1 - 1/3 } = \dfrac{2 u_0 \times 2/3}{0 \times n + 2/3} = 2u_0

Autrement dit, la raison d’une telle suite doit être égale au double du premier terme. Cela était bien le cas avec la suite des nombres impairs car le premier terme est u_0=1 et la raison de la suite des nombres impairs est r=2 = 2 \times 1.

Réciproquement, si une suite (u_n) est arithmétique de raison r= 2 \times u_0 alors, en reprenant une égalité vue plus haut, on a

\dfrac{u_0+u_1+\cdots+u_{n-1}}{u_n + u_{n+1} + \cdots + u_{2n-1}} = \dfrac{2u_0 + (n-1) r}{ 2u_0 + (3n-1) r} = \dfrac{2u_0 + (n-1) \times 2u_0}{2u_0 + (3n-1)\times 2u_0 }

En simplifiant par 2u_0 au numérateur et au dénominateur, on obtient alors

\dfrac{u_0+u_1+\cdots+u_{n-1}}{u_n + u_{n+1} + \cdots + u_{2n-1}} = \dfrac{1 + (n-1) }{ 1 + (3n-1)} = \dfrac{n}{3n} = \dfrac{1}{3}

Voici résumé ce que nous avons prouvé:

Soit (u_n) est une suite arithmétique de raison r.

Le quotient de la somme des n premiers termes par la somme des n termes suivants est constant si, et seulement si, r= 2 u_0. Cette constante est alors \dfrac{1}{3}.

Avec cela, vous êtes maintenant capables de construire autant de suites « à la Galilée » que vous le souhaitez (si, si !). Par exemple, prenons la suite arithmétique de premier terme u_0 = 4 et de raison r= 2 \times u_0 = 8 (c’est-à-dire la suite dont les premiers termes sont 4, 12, 20, 28, 36, 44, \cdots). Vous pouvez vérifier qu’on a bien

\dfrac{4}{12} = \dfrac{4+ 12}{20 + 28} = \dfrac{4+12+20}{28+36+44} = \cdots = \dfrac{1}{3}

Magie !

Ce qui est bien avec tout ce qu’on vient de voir, c’est qu’on peut faire un petit tour de magie très facile car il ne vous demandera que de mémoriser un nombre: 3 (ça ne devrait pas être trop dur… sinon, c’est que la magie n’est vraiment pas faite pour vous). Voici le tour:

  • Demandez à une personne de choisir un nombre entier u_0 au hasard mais sans vous le dire.
  • Demandez-lui d’écrire sur une feuille la suite des nombres obtenus en partant du nombre u_0 choisi au départ et en ajoutant 2 \times u_0 à chaque étape. Dites à cette personne qu’elle peut écrire autant de termes qu’elle souhaite de cette suite, du moment qu’il y en a un nombre pair 2n.
  • Demandez-lui ensuite de couper la liste en deux parts égales, de calculer la somme des n plus grands nombres et de la diviser par la somme des n plus petits nombres de la liste, sans jamais vous donner le résultat (éventuellement à l’aide d’une calculatrice).
  • Comme dans tout tour de magie qui se respecte, faites semblant de réfléchir et de calculer dans votre tête, tout en rigolant intérieurement.
  • Annoncez-lui que le nombre obtenu est 3.
  • Ne répondez surtout pas à la question « Mais comment t’as fait, quoi ?« .

Par exemple, la personne choisit secrètement le nombre 3. Elle écrit sur sa feuille les 10 (nombre pair) premiers termes de la suite de nombres obtenue en partant de 3 et en ajoutant 3 \times 2 = 6 à chaque fois:

3, 9, 15, 21, 27, 33, 39, 45, 51, 57

La personne coupe alors sa liste en deux au milieu et fait la somme de chaque morceau:

3 + 9 +  15 +  21 + 27=75 et 33 + 39 + 45 + 51 + 57 = 225

Elle divise enfin la somme des cinq derniers termes par la somme des cinq premiers:

\dfrac{225}{75} = 3

et vous lui annoncez alors qu’elle a trouvé 3 !

Heureusement quand même qu’il y a des gens très sérieux qui ont utilisé les résultats de Galilée pour approfondir notre connaissance des lois de la Physique parce que si Galilée avait su que, 400 ans après, on utiliserait un de ses résultats mathématiques pour en faire un tour de magie foireux, pas sûr qu’il ait eu envie de continuer sa belle carrière de scientifique !

Notes et références:

Publié dans Algèbre | Tagué , , , , , | 8 commentaires

Conway et la réciproque du théorème des valeurs intermédiaires

Le 26 Décembre dernier, le génialissime mathématicien John Horton Conway fêtait ses 80 ans. Pour célébrer cela, pourquoi ne pas faire un article sur une de ses (nombreuses) découvertes ? Bien entendu, on pourrait parler de sa plus célèbre création, à savoir le fameux Jeu de la vie. On pourrait aussi évoquer la non moins célèbre suite de Conway aussi appelée « Regarde et dis » (« Look and say » dans la langue de Britney Spears).  Bref, les contributions de Conway aux mathématiques sont très nombreuses et toutes superbes.

Nous allons nous intéresser à une découverte un peu moins connue de Conway: il s’agit d’une fonction portant son nom qui est en lien avec le théorème des valeurs intermédiaires. Avant de poursuivre, j’espère que vous n’êtes pas superstitieux car elle fera intervenir le nombre 13…

Le théorème des valeurs intermédiaires

Rappelons, si besoin est, le fameux théorème des valeurs intermédiaires. Ce théorème affirme que si une fonction est continue alors elle prend toutes les valeurs intermédiaires entre deux images données (d’où son nom très original).

Intuitivement, cela se comprend ainsi: si on trace le graphe d’une fonction f sans lever le stylo (c’est-à-dire si la fonction est continue), alors on passera forcément par toutes les valeurs intermédiaires k entre deux images f(a) et f(b).

Toutes les valeurs entre f(a) et f(b) sont atteintes si f est continue.

La question qu’on peut alors se poser est: si on passe par toutes les valeurs entre deux images données, le graphe a-t-il forcément été tracé sans lever le stylo ? Mathématiquement, cela revient à s’intéresser à la réciproque du théorème des valeurs intermédiaires: est-il vrai que si une fonction passe par toutes les valeurs intermédiaires de deux images données, elle est nécessairement continue ? On a très envie de le penser en tout cas… On ne peut pas ne pas le croire !

Pourtant, cette question (qui pourrait très bien être un sujet de philosophie) possède une réponse mathématique impitoyable: c’est non. Une fonction qui passe par toutes les valeurs intermédiaires entre deux images quelconques n’est pas forcément continue et cela est connu depuis 1875 et le théorème de Darboux .

Et Conway dans tout cela ? Il imagina une fonction plutôt simple et très concrète qui contredit la réciproque du théorème des valeurs intermédiaires et qui porte son nom: la fonction base 13 de Conway.

Triskaïdékaphobiques, s’abstenir

Avant de parler de la fonction de Conway, rappelons ce qu’est la décomposition en base 13 d’un nombre.

Tout nombre réel possède une écriture décimale « avec une virgule », ce qui veut dire qu’on peut écrire n’importe quel nombre à l’aide des chiffres allant de 0 à 9 et de puissances de 10.

Par exemple, le nombre « un quart » s’écrit 0,25 =  \frac{2}{10} + \frac{5}{10^2} et le nombre « trente-sept tiers » s’écrit 12,333 \cdots = 1 \times 10^1 + 2 \times 10^0 +  \frac{3}{10} + \frac{3}{10^2} + \frac{3}{10^3} + \cdots

Il se trouve que pour des raisons historiques nous utilisons la base 10 pour représenter les nombres mais rien n’empêche d’utiliser d’autres bases de numération. Conway a, comme nous le verrons, choisi très astucieusement d’utiliser la base 13 pour sa fonction.

Pour écrire un nombre en base 13, on utilise… 13 chiffres (qui a dit 12 exprès ?). Ce sont les chiffres

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C

où les chiffres A, B et C ne sont rien d’autre que les nombres dix, onze et douze. Par exemple, en base treize, le nombre « quinze » s’écrit 12 (une « treizaine » et deux unités) et le nombre « Vingt-trois » s’écrit 1A (une « treizaine » et dix unités).

Les écritures en base 10 et en base 13 partagent dix chiffres en commun (les chiffres de 0 à 9) donc, pour distinguer l’écriture en base 10 de celle en base 13, nous noterons cette dernière à l’aide d’une barre. Par exemple, le nombre « vingt-trois » se notera 23 en base dix et \overline{1A} en base treize.

Enfin, on peut aussi très bien parler de nombres « à virgules » en base treize. Par exemple, le nombre écrit en base treize \overline{B3C,1A9C} représentera, en base dix, le nombre

11 \times 13^2 + 3 \times 13^1 + 12 \times 13^0 + \dfrac{1}{13} + \dfrac{10}{13^2} + \dfrac{9}{13^3} + \dfrac{12}{13^4}

Le nombre \pi, quant à lui, s’écrira \pi = 3,1AC1049052A2C7 \cdots en base 13 (et on se demande alors, à quand un record du monde de récitation du plus grand nombre de décimales de \pi en base 13 ?).

Dernière chose: tout comme en base 10 où on n’autorise pas qu’une écriture décimale finisse par une infinité de 9, on n’autorise pas non plus qu’une écriture en base 13 finisse par une infinité de C. Cette condition permet de prouver que tout nombre réel possède une unique écriture « à virgule » en base treize.

La fonction base 13 de Conway

Comme nous l’avons dit, tout nombre réel possède une écriture essentiellement unique en base 13. A partir de cela, Conway va définir une fonction, que nous noterons f, en distinguant trois cas:

1) Si un nombre x possède une écriture en base 13 de la forme

x= \overline{n_1 n_2 \cdots n_p \, \text{\Large\bfseries ,} \, x_1 x_2 \cdots x_q \mathbf{A} y_1 y_2 \dots y_r \mathbf{C} z_1 z_2 z_3\dots }

où les n_i et les x_i représentent des chiffres quelconques et où les y_i et les z_i sont uniquement des chiffres compris entre 0 et 9, alors l’image f(x) sera le nombre écrit en base 10 par

f(x) =  y_1y_2 \cdots y_r \, \text{\Large\bfseries ,} \, z_1 z_2 z_3\cdots

Par exemple, si x=\overline{3AB12 \, \text{\Large\bfseries ,} \, A2A24BC3\mathbf{A} 789\mathbf{C} 1239} alors f(x) est le nombre défini en base dix par f(x) = 789 \, \text{\Large\bfseries ,} \, 1239.

En gros, le tout dernier C de l’écriture en base 13 (s’il y en a un !) devient une virgule en base 10; tous les chiffres entre 0 et 9 situés avant C deviennent la partie entière et tous les chiffres situés après C deviennent la partie décimale de l’image.

2) Si x possède une écriture en base 13 de la forme

x= \overline{n_1 n_2 \cdots n_p \, \text{\Large\bfseries ,} \, x_1 x_2 \cdots x_q \mathbf{B} y_1 y_2 \dots y_r \mathbf{C} z_1 z_2 z_3\dots }

où les n_i et les x_i représentent des chiffres quelconques et où les y_i et les z_i sont uniquement des chiffres compris entre 0 et 9, alors f(x) est le nombre écrit en base 10 par

f(x) = - y_1y_2 \cdots y_r  \, \text{\Large\bfseries ,} \, z_1 z_2 z_3 \cdots

Par exemple, si x= \overline{BC19A81 \, \text{\Large\bfseries ,} \, AB4BC127\mathbf{B}479103\mathbf{C} 47621} alors on a f(x) = - 479103 \, \text{\Large\bfseries ,} \, 47621 (en base 10).

3) Dans tous les autres cas (et Dieu sait s’ils sont nombreux !), on pose f(x)=0.

Si cela vous amuse, voici un petit script en Python pour calculer l’image d’un nombre écrit en base 13 par la fonction de Conway:

Calculateur d’image par la fonction de Conway

La fonction de Conway vérifie la propriété des valeurs intermédiaires… et même plus !

Nous allons montrer que la fonction de Conway vérifie la propriété des valeurs intérmédiaires, à savoir que si a et b sont deux réels avec a<b alors, quelque soit le réel k compris entre f(a) et f(b), il existe un réel x compris entre a et b tel que k = f(x).

En fait, nous allons même montrer mieux: non seulement ce sera vrai pour tout nombre k compris entre f(a) et f(b) mais ce sera aussi vrai pour n’importe quel nombre k quelconque !

Le graphe de la fonction de Conway est représenté en bleu. Si avec ce schéma vous ne voyez pas qu’elle vérifie la propriété des valeurs intermédiaires…

Commençons d’abord par donner un exemple très concret. On considère deux réels a<b et on prend, disons, k = 2 \, \text{\Large\bfseries ,} \,  718281 \cdots en base 10 (vous aurez bien entendu reconnu le nombre \text{e} !). Voyons pourquoi il existe un antécédent de k compris entre a et b.

Si on pose x = \overline{ 0 \, \text{\Large\bfseries ,} \,  A 2 C  718281 \cdots } alors, par définition de la fonction f, on voit bien que f(x)=k. Il se peut cependant que x ne soit pas compris entre a et b mais, comme on va le voir, on peut toujours s’arranger pour que ce soit le cas.

En effet, gardons à l’esprit qu’on dispose d’une certaine marge de manœuvre: si on remplace la partie entière de x par n’importe quoi, f(x) sera toujours égal à k. Dans notre exemple, les nombres

  • x = \overline{ 0 \, \text{\Large\bfseries ,} \,  A 2 C  718281 \cdots }
  • x = \overline{ 27A \, \text{\Large\bfseries ,} \,  A 2 C  718281 \cdots }
  • x = \overline{ 1A1B1C1ABC \, \text{\Large\bfseries ,} \,  A 2 C  718281 \cdots }

ont tous pour image k = 2, 718281 \dots

De même, si on insère n’importe quelle suite finie de chiffres entre la virgule et A, on aura encore f(x)=k. Par exemple,

  • x = \overline{ 0 \,  \text{\Large\bfseries ,} \, 1234  A 2 C  718281 \cdots},
  • x = \overline{ 0 \, \text{\Large\bfseries ,} \, A1B2C34 A 2 C  718281 \cdots }
  • x = \overline{ 0 \, \text{\Large\bfseries ,} \,  103040B101A 2 C  718281 \cdots }

ont eux aussi tous pour image k.

Fort de tout cela, nous pouvons toujours trouver un réel x dont l’image par f est k et qui est situé entre a et b: puisque a<b, il existe un réel m tel que a<m<b et tel que m possède une écriture « à virgule » finie du type m = \overline{x_1 x_2 \cdots x_n \, \text{\Large\bfseries ,} \,  y_1 y_2 \cdots y_p} (pourquoi ? [1]). Il suffit alors de poser

x =  \overline{ x_1 x_2 \cdots x_n \, \text{\Large\bfseries ,} \,  y_1 y_2 \cdots y_p 000 \cdots 000 A 2 C 718281 \cdots }

avec autant de zéros qu’il faut entre y_p et A pour que x soit bien situé entre a et b (comme a<b, cela est bien possible car, plus on ajoute de 0 et plus x se rapproche de m). On a alors bien trouvé un x tel que f(x)=k et tel que a<x<b.

Dans le cas général où k est un réel positif quelconque, l’idée est la même: on trouve un antécédent x puis on ajuste sa partie entière et les chiffres situés entre la virgule et A pour que x soit bien situé entre a et b. Je ne vais pas en faire la démonstration car les notations seraient trop lourdes et le tout serait fastidieux… J’espère simplement que l’exemple ci-dessus vous aura convaincu.

Enfin, une dernière remarque: si k était négatif, il suffirait simplement de remplacer le dernier chiffre A par B et le raisonnement serait similaire.

La fonction de Conway n’est pas continue

Pour finir, nous allons montrer que la fonction de Conway n’est continue nulle part, bien que nous avons montré qu’elle vérifie la propriété des valeurs intermédiaires !

Si f était continue en un point x_0, il existerait un intervalle ouvert ]a ; b[ contenant x_0 sur lequel f serait bornée. Autrement dit, il existerait deux réels  m et M tels que pour tout x\in]a;b[,

m \leqslant f(x) \leqslant M

Cependant, nous avons prouvé que n’importe quel réel k possède un antécédent x dans l’intervalle ]a;b[, donc en choisissant k>M (ou k<m), cela montrerait qu’il existe un x \in ]a;b[ tel que f(x)=k>M (ou f(x)=k<m) ce qui est, convenons-en, une belle contradiction. Cela prouve que la fonction de Conway n’est donc continue nulle part !

Il ne nous reste plus qu’à souhaiter, très en retard, un joyeux anniversaire à John Conway et à lui dire merci pour toutes ses merveilleuses contributions aux mathématiques !

Notes et références:

Publié dans Analyse | Tagué , , , , , | 4 commentaires

En 2018, le facteur ne passera pas deux fois

Vous trépignez à l’idée de savoir ce que renfermera l’année 2018 du point de vue mathématique ? Vous n’en pouvez plus d’attendre de savoir ce que 2018 va nous réserver ? Je ne vous fais pas attendre plus longtemps: cette année 2018 sera exceptionnelle car 2018 est un nombre pair ! Cela faisait un an que cela n’était plus arrivé ! Génial ! Bonne année !

Si vous tournez la tête à 90°, vous pourrez voir que 2018 contient l’infini !

2018, une année banale ?

Trêve de plaisanterie, et voyons quelles propriétés le nombre 2018 possède. Malheureusement, il n’en a pas tant que cela qui fasse de lui un nombre à part mais vous allez voir que, malgré tout, 2018 arrivera quand même à se distinguer…

Tout d’abord, citons une propriété du nombre 2018 que je trouve particulièrement jolie: il peut s’écrire comme la somme des carrés de deux nombres premiers, et, plus précisément,

2018 = 13^2 + 43^2

Autre propriété intéressante de 2018: ce n’est pas un nombre premier, certes, mais c’est un nombre composé (non premier) sans facteur carré, c’est-à-dire qu’il s’écrit comme le produit de plusieurs nombres premiers distincts

2018 = 2 \times 1009

Cependant, cela était déjà le cas en 2014 et en 2015 qu’une année soit sans facteur carré (2014 = 2 \times 19 \times 53 et 2015 = 5 \times 13 \times 31; vous pouvez d’ailleurs lire l’article que j’avais consacré en 2014 sur les nombres sans facteurs carrés si le sujet vous intéresse). Mais chaque année a sa particularité et 2018 se distingue des années précédentes car, en plus d’être un nombre composé sans facteur carré, la somme des ses diviseurs est aussi un nombre sans facteur carré ! Et ça, vraiment, c’est remarquable ! Pour dire, avant 2018, il n’y a eu que 32 années depuis l’an I qui étaient des nombres composés sans facteur carré dont la somme des diviseurs était aussi un nombre sans facteur carré !

Qu’est-ce que cela veut dire ?

Si cette propriété que vérifie 2018 vous semble encore floue, voyons voir ce qu’elle signifie. Les diviseurs (positifs) de 2018 sont 1, 2, 1009 et 2018 donc la somme de ces diviseurs est

1 + 2 + 1009 + 2018 = 3030

et cette somme est aussi un nombre sans facteur carré car, comme vous pouvez le constater ci-dessous, elle s’écrit comme le produit de plusieurs nombres premiers distincts:

3030 = 2 \times 3 \times 5 \times 101

C’est bien cela qui est remarquable ! La dernière fois qu’une année vérifiait cette propriété, c’était en 1994 (il y a 24 ans !). En effet, 1994 est bien un nombre composé sans facteur carré:

1994 =2 \times 997

Ses diviseurs sont 1, 2, 997 et 1994 donc la somme de ses diviseurs est

1+2+997+1994 = 2994

Cette somme des diviseurs est bien elle-même un nombre sans facteur carré car

2994 = 2 \times 3 \times 499

Si vous observez bien, vous pouvez trouver un point commun à 2018 et 1994: ces deux nombres sont de la forme 2 \times pp est un nombre premier. Cela n’est pas un hasard et nous allons voir que si une année est comme 2018 (c’est-à-dire que c’est un nombre composé sans facteur dont la somme est aussi un nombre sans facteur carré) alors nécessairement elle est de la forme 2 \times p (avec p premier).

Interlude: somme des diviseurs

Avant de poursuivre, intéressons-nous un peu plus à la notion de somme des diviseurs d’un nombre. Une première remarque: si un nombre p est premier, il ne possède que deux diviseurs positifs, à savoir 1 et lui-même. Dans ce cas, la somme des diviseurs de p (que l’on note traditionnellement \sigma(p)) est

\sigma(p) = 1+p

Par exemple, la somme des diviseurs de 5 est \sigma(5) = 1+5= 6 et la somme des diviseurs de 7 est \sigma(7)=1+7=8.

Une deuxième remarque : la somme des diviseurs est multiplicative. Cela signifie que si deux nombres n et m sont premiers entre eux, alors \sigma( n \times m) = \sigma(n) \times \sigma(n). Nous admettrons cette propriété (qui n’a rien d’évident, je vous rassure !) mais voyons un exemple d’application: pour trouver la somme des diviseurs du nombre 35, il suffit de remarquer que 35 est le produit des deux nombres premiers 5 et 7. Ainsi, puisque 5 et 7 sont premiers entre eux, alors

\sigma(35)=\sigma(5 \times 7) = \sigma(5) \times \sigma(7) = 6 \times 8 = 48.

Vous pouvez aussi le vérifier directement car les diviseurs de 35 sont 1, 5, 7 et 35 et leur somme est 1+5+7+35=48.

Une petite démonstration pour commencer 2018

Nous sommes à présent en mesure de prouver pourquoi 2018 était forcément de la forme 2 \times p. ATTENTION: si vous n’avez toujours pas décuvé de votre réveillon et que vos yeux ont du mal à rejoindre leurs orbites, n’hésitez pas à passer au paragraphe suivant !

Si un nombre N est un nombre composé sans facteur carré, alors il peut s’écrire

N= p_1 \times p_2 \times \cdots \times p_n

où les p_i sont des nombres premiers distincts. D’après ce qu’on a dit, comme les p_i sont premiers entre eux deux à deux, la somme des diviseurs de N est

\sigma(N) = \sigma(p_1) \times \sigma(p_2) \times \cdots \times \sigma(p_n)

c’est-à-dire

\sigma(N) = (1+p_1) \times (1+p_2) \times \cdots \times (1+p_n)

S’il y avait au moins deux nombres premiers impairs p_i et p_j alors 1+p_i serait divisible par 2 et, de même, 1+p_j serait divisible par 2 ce qui fait que \sigma(N) serait divisible par 2\times 2 = 2^2. Autrement dit, la somme des diviseurs de N ne pourrait pas être sans facteur carré !

Nous avons donc prouvé que si N est un nombre composé sans facteur carré dont la somme des diviseurs est aussi un nombre sans facteur carré, alors il possède strictement moins de deux diviseurs premiers impairs. Mais comme N est composé, il possède au moins deux diviseurs premiers. La seule possibilité est donc que N possède exactement deux diviseurs premiers: l’un pair et l’autre impair, c’est-à-dire que N est de la forme N=2 \times pp est un nombre premier impair.

Quand Jeanne Calment avait failli manqué cela…

Nous avons donc vu que si une année est un nombre composé sans facteur carré et que la somme de ses diviseurs est aussi un nombre sans facteur carré, alors forcément elle est de la forme 2\times p (où p est premier impair). C’est le cas de 2018 et de 1994 mais il faut faire attention cependant: ce n’est pas parce qu’une année est de la forme 2 \times p que la somme de ses diviseurs est sans facteur carré. Par exemple, l’année 1982 était bien de la forme 2 \times p (1983 = 2 \times 991) mais la somme de ses diviseurs, à savoir le nombre 2976, n’est pas sans facteur carré car 2976 =2^5 \times 3 \times 31.

Le fait que N soit de la forme 2 \times p est donc une condition nécessaire, mais non suffisante. On peut affiner cette condition nécessaire en démontrant que si un nombre composé N est sans facteur carré et que la somme de ses diviseurs est elle aussi sans facteur carré, alors non seulement N=2\times p avec p premier impair, mais en plus on doit avoir p \equiv 1 \mod[12], c’est-à-dire que p doit être de la forme p=12k + 1 (voir en fin d’article pour une démonstration). Cela implique alors que N= 2 \times p = 2 \times (12k  +1) et donc une année qui vérifie cette propriété est nécessairement de la forme 24k + 2.

Cette condition ne sera sera toujours pas suffisante (un contre-exemple serait l’année 1154=2 \times 577 avec 577 qui est bien congru à 1 modulo 12 mais \sigma(1154) = 1734 = 2 \times 3 \times 17^2 n’est pas sans facteur carré), mais elle a le mérite de nous informer que des années comme 2018 ne se produisent au minimum que tous les 24 ans… Cet intervalle de 24 ans est un seuil minimal mais il se peut qu’il se passe beaucoup plus de temps. Par exemple, aucune année n’a vérifié cette propriété entre 1874 et 1994. Pour dire, Jeanne Calment (1875-1997) a dû attendre de fêter ses 119 ans pour pouvoir vivre une année qui vérifie cette propriété !

Tout le monde n’est donc pas 2018 et pour retrouver une année qui possède cette propriété étonnante, il faudra attendre 2042. Alors, en attendant, profitons bien de cette année 2018…

Bonne année à tous !

Notes:

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

Fonctions égales à leur dérivée

Il y a quelques temps de cela, j’avais posté sur Twitter l’animation suivante:Cette animation était accompagnée du (bref) commentaire suivant :

« Les fonctions exponentielles f(x) = k \times \text{e}^{x} sont les seules fonctions égales à leur dérivée »

C’est une affirmation bien téméraire que j’avais fait là ! Comme le disait Euclide, « ce qui est affirmé sans preuve peut être réfuté sans preuve », donc nous n’allons surtout pas contrarier Euclide et nous allons prouver cette affirmation.

Explication de l’animation

Avant même de démontrer cette propriété, il est peut-être utile d’expliquer en quoi cette animation illustre le fait que les fonctions x \mapsto k \times \text{e}^{x} sont égales à leur dérivée.

Si on se donne la courbe d’une fonction, il est facile de lire l’image d’un point x: il suffit de « monter » jusque la courbe et de lire l’ordonnée:Pour lire graphiquement la dérivée, il faut se souvenir que le nombre dérivé en un point n’est rien d’autre que le coefficient directeur de la tangente en ce point. Vous vous souvenez aussi sans doute de comment lire graphiquement le coefficient directeur d’une droite: on part de n’importe quel point de cette droite, on se décale d’une unité vers la droite et le coefficient directeur est le nombre d’unités qu’il faut parcourir verticalement pour retourner sur la droite.Dans l’animation, nous voyons que les deux segments représentant les distances f(x) et f'(x) sont de même longueur, quelque soit l’abscisse x à laquelle on se trouve: cela veut bien dire que la fonction x \mapsto k \times \text{e}^{x} qui est tracée est égale à sa dérivée.Cette animation illustre donc bien le fait que les fonctions de la forme x \mapsto k \times \text{e}^{x} sont égales à leur dérivée, mais elle n’explique ni pourquoi c’est le cas, ni pourquoi il ne peut y avoir d’autres fonctions qui vérifient cela.

Heuristique

Avant de faire une vraie démonstration mathématique de l’affirmation donnée au début de l’article, à savoir que les seules fonctions égales à leur dérivée sont les fonctions de la forme x \mapsto k \times \text{e}^{x}, essayons de comprendre pourquoi si une fonction est égale à sa dérivée, alors c’est forcément une fonction exponentielle. Pour cela, nous allons commettre l’irréparable: nous allons faire un raisonnement « à la physicienne » (je sens que je ne vais pas me faire que des amis…)

On considère une fonction f. Si cette fonction est égale à sa dérivée alors f'(x) = f(x) donc, en divisant par f(x),

\dfrac{f'(x)}{f(x)} = 1 \quad (\star)

D’une part, nous savons qu’une primitive de \dfrac{f'(x)}{f(x)} est \ln(f(x)). D’autre part, nous savons qu’une primitive de x\mapsto 1 est x \mapsto x + CC est une constante. Ainsi, en « primitivant » l’égalité (\star), on obtient

\ln(f(x)) = x + C

En prenant l’exponentielle des deux côtés, on a alors

f(x) = \text{e}^{x + C} \iff  f(x) = \text{e}^C \times \text{e}^x

En posant k=\text{e}^C, on voit donc que f est de la forme f(x) = k \times\text{e}^x.

J’entends déjà certains hurler que ce raisonnement n’est pas du tout rigoureux (« Je pensais qu’on faisait des maths sur Blogdemaths ! C’est inadmissible ! ») et ils auraient raison. Voyez-vous pourquoi ? Il y a deux raisons à cela:

  1. Tout d’abord, une primitive de \dfrac{f'(x)}{f(x)} est \ln(|f(x)|) et non \ln(f(x)).
  2. Ensuite, on a divisé par f(x) dès le départ, mais rien ne nous dit que f ne s’annule pas !

Nous avons donc commis deux pêchés capitaux en mathématiques: prendre le logarithme d’un nombre qui peut être négatif et diviser par zéro ! Pour nous repentir, nous allons donner une vraie démonstration mais vous allons voir qu’il faut peu de choses pour rendre notre explication précédente rigoureuse. A commencer par utiliser des produits plutôt que des quotients.

Une démonstration plus rigoureuse

Soit f une fonction définie sur \mathbb{R}.

a) Si f est de la forme x \mapsto k \times \text{e}^{x} alors il est aisé de calculer sa fonction dérivée: f'(x) = k \times \text{e}^{x} donc f est bien égale à sa dérivée. Facile.

b) Réciproquement, si f est égale à sa dérivée, il s’agit de montrer qu’elle est de la forme f(x) = k \times \text{e}^x. Comme pour tout x, f(x) = f'(x) alors

f'(x) - f(x) = 0 \quad \quad (\star \star)

Jusque-là, rien de bien folichon. L’idée va être d’interpréter cette égalité comme étant de la forme u' \times v + u \times v' de façon à pouvoir en prendre une primitive à l’aide de la formule de dérivation (u \times v)' = u' \times v + u \times v'. Pour cela, on multiplie la relation (\star \star) par \text{e}^{-x} ce qui va justement faire marcher les choses. Plus précisément, cela donne:

f'(x)  \times \text{e}^{-x} - f(x) \times \text{e}^{-x} =0

On réécrit cette égalité sous la forme suivante:

f'(x) \times \text{e}^{-x} + f(x) \times \left(- \text{e}^{-x} \right) = 0 \quad \quad (\star \star \star )

On reconnaît alors à gauche une expression de la forme u'  \times v + u \times v' avec

u= f(x) et v = \text{e}^{-x}

Comme u'  \times v + u \times v' est la dérivée de (u \times v) ', en primitivant des deux côtés la relation (\star \star \star), on a

f(x) \times \text{e}^{-x} = kk est une constante

En faisant passer l’exponentielle de l’autre côté, on obtient finalement que

\boxed{ f(x) = k \times \text{e}^{x} }

Fonctions proportionnelles à leur dérivée

L’idée précédente de faire apparaître la forme u'  \times v + u \times v' en multipliant par la bonne fonction peut se généraliser au cas où on cherche les fonctions qui sont, non pas égales à leur dérivée, mais proportionnelles à leur dérivée.

Par exemple, si on souhaite déterminer toutes les fonctions égales à deux fois leur dérivée, cela revient à chercher les fonctions f telles que f(x) = 2 f'(x). Ainsi,

2 f'(x) - f(x) =  0 \iff f'(x) + f(x) \times \left(-\dfrac{1}{2} \right) = 0

En multipliant des deux côtés par \text{e}^{\frac{-1}{2} x} (dont la dérivée est \frac{-1}{2} \text{e}^{\frac{-1}{2} x}), on a :

f'(x) \times \text{e}^{\frac{-1}{2} x} +  f(x) \times \left(\dfrac{-1}{2} \right)\text{e}^{\frac{-1}{2}} = 0

c’est-à-dire u' \times v + u \times v' = 0 avec u = f(x) et v' = \text{e}^{-\frac{1}{2} x}. En primitivant cette relation, on obtient alors que le produit u \times v est constant, c’est-à-dire:

\exists k \in \mathbb{R},  f(x) \times \text{e}^{-\frac{1}{2} x} = k

et en passant l’exponentielle de l’autre côté, on voit donc qu’une fonction qui est égale à deux fois sa dérivée est nécessairement de la forme \boxed{ f(x) = k \times \text{e}^{\frac{1}{2} x} }

Vers les équations différentielles linéaires du 1er ordre

Sur ce principe, on peut résoudre n’importe quelle équation différentielle linéaire du premier ordre c’est-à-dire une équation de la forme:

f'(x) + a(x) \times f(x) = 0

où la fonction f est l’inconnue et où la fonction a est une fonction continue donnée (par exemple, pour les fonctions égales à leur dérivée, on avait a(x) = -1 qui était donc une fonction constante). En suivant ce que nous avons dit précédemment, on va multiplier l’égalité précédente par une fonction du type \text{e}^{G(x)} (où G est une fonction à déterminer) afin de faire apparaître la forme u' v + u v':

f'(x) \times \text{e}^{G(x)} + f(x) \times \left(a(x) \times \text{e}^{G(x)}\right) = 0 \quad \quad (\clubsuit)

Toujours comme précédemment, on pose u= f(x) et v = \text{e}^{G(x)}. Comme la dérivée de \text{e}^{G(x)} est G'(x) \times \text{e}^{G(x)}, il suffit donc que  la fonction G soit une primitive de la fonction a (dont on sait qu’elle existe car toute fonction continue sur un intervalle possède une primitive sur cet intervalle) pour qu’on ait bien v' = a(x) \times \text{e}^{G(x)}. En supposant cela, si on primitive la relation (\clubsuit), on obtient

\exists k \in \mathbb{R},  f(x) \times \text{e}^{G(x)} = k \iff f(x) = k \times \text{e}^{-G(x)}.

Voici donc ce que nous avons prouvé:

Soit a une fonction continue sur un intervalle I. Les fonctions définies sur I solutions de l’équation différentielle f'(x) + a(x) \times f(x) =0 sont les fonctions f de la forme

f(x) = k \times \text{e}^{-G(x)}

G est une primitive de la fonction a sur I.

Je pense qu’avec tout ça, Euclide devrait être satisfait !

Publié dans Analyse | Tagué , , , , , | 4 commentaires

Un trop plein de vaches

Dans le célèbre jeu vidéo Minecraft, il existe tout un monde d’être vivants dont des animaux. Il est possible d’interagir avec ces bêtes car on peut les nourrir (ou les tuer, selon votre degré de psychopathie) mais aussi les faire se reproduire.

« T’as de beaux meuh tu sais »

Par exemple, pour faire se reproduire deux vaches dans ce jeu, il suffit de donner du blé à chacune d’entre elles… et paf, ça fait un bébé vache !

Il n’est pas trop à croquer ce bébé vache ? (dans un bon hamburger).

Précisons tout de même que les êtres vivants n’ont pas de genre dans Minecraft et il n’y a ainsi pas de mâle ou de femelle. On peut donc faire se reproduire deux vaches quelconques, à condition qu’elles soient toutes deux adultes (mais pas forcément consentantes…). Une fois que deux vaches ont donné naissance à un bébé, il faut ensuite attendre 20 minutes pour qu’elles puissent à nouveau se reproduire. Vingt minutes, c’est aussi le temps qu’il faut à un bébé vache pour devenir adulte et pouvoir procréer.

Si jamais vous avez l’âme d’un éleveur de bêtes, vous pouvez donc vous constituer un beau petit troupeau… mais de quelle taille ? Par exemple, en jouant 24 heures en continu, combien pourrait-on avoir de vaches au maximum ?

L’amour est dans le pré

Imaginons qu’on parte d’un troupeau de deux vaches et voyons comment agrandir ce troupeau. A l’étape n°0, nous sommes donc en possession de deux bêtes:A la première étape, on fait se reproduire ces deux vaches, ce qui donne trois vaches dont un bébé:Vingt minutes plus tard, lorsque les deux adultes peuvent à nouveau se reproduire, le bébé est devenu adulte. A la fin de l’étape n°1, nous sommes donc en possession de 3 vaches adultes:A la deuxième étape, on choisit deux vaches parmi les 3 et on les fait se reproduire. La 3ème vache ne servira à rien (si ce n’est à tenir la chandelle et à dormir sur la béquille):A la fin de la deuxième étape, quand le bébé a grandi et que les vaches adultes peuvent à nouveau se reproduire, nous avons donc 4 vaches au total:Vous pouvez facilement vérifier qu’à la fin de la troisième étape, nous serons en présence de 6 vaches et vous commencez sans doute à comprendre le principe. Nous allons donc tenter de généraliser tout cela.

Modélisation du nombre de vaches

Notons C(n) le nombre de vaches à la n-ème étape. Par exemple, nous avons vu que C(0)=2, C(1)=3, C(2)=4 et C(3)=6. Essayons de voir comment passer d’une étape à la suivante.

Supposons donc qu’on se situe à la fin de la n-ème étape (à ce moment-là, les C(n) vaches en notre possession sont adultes). Pour connaître le nombre de vaches à la fin de l’étape n+1, on forme autant de couples de vaches que possible, chaque couple donnant naissance à un bébé.  Comme il y aura autant de bébés que de couples possibles, il faut diviser le nombre de vaches C(n) par 2 pour obtenir le nombre de progénitures engendrées. Cependant, s’il y a un nombre impair de vaches au départ, il y en a une qui restera seule ce qui fait que le nombre de couples de vaches, donc de bébés, sera \left\lfloor \dfrac{C(n)}{2} \right\rfloor\left\lfloor x \right\rfloor désigne la partie entière de x (par exemple, si à l’étape n on a 13 vaches, comme la partie entière de 13/2 = 6,5  est 6, on aura donc 6 couples et une vache qui ne s’accouple pas, ce qui donnera 6 bébés).

A ces \left\lfloor \dfrac{C(n)}{2} \right\rfloor bébés, il faut ajouter les C(n) vaches qu’on avait déjà en notre possession, ce qui donne finalement la formule de récurrence suivante:

\boxed{ \vphantom{\dfrac{X}{X}} C(n+1) = C(n) + \left\lfloor \dfrac{C(n)}{2} \right\rfloor }

Grâce à cette formule, on peut calculer le nombre de vaches qu’on aura au bout de 24 heures. Comme il y a 1 440 minutes dans une journée et que 1440/20 = 72, nous pourrons donc effectuer 73 étapes de reproduction (les étapes 0 et 1 se déroulant au même instant):La formule de récurrence précédente et un petit programme informatique (ou même une calculatrice) nous permettent alors de voir que

C(73) = 11 \, 608 \, 742 \, 626 \, 668

Autrement dit, en 24 heures, vous pourrez obtenir un élevage de plus de dix mille milliards de vaches… de quoi bien remplir votre champ !

Une formule explicite ?

Comme souvent avec les suites, il est toujours plus commode d’avoir une formule explicite plutôt que d’avoir simplement une formule par récurrence. Malheureusement, il est difficile (mais possible, voir en fin d’article) de trouver une formule explicite pour le nombre de vaches C(n). Qu’à cela ne tienne, nous allons encadrer cette suite par deux autres suites, afin d’estimer à quelle vitesse le nombre de vaches croît (et il croît très vite comme on l’a vu !). Pour cela, nous allons utiliser le résultat suivant:

Si k est un nombre entier, alors

\dfrac{k-1}{2} \leqslant \left\lfloor \dfrac{k}{2} \right\rfloor \leqslant \dfrac{k}{2}.

Pour prouver ce résultat, il suffit de distinguer deux cas:

• Si k est pair, alors k = 2mm est un entier. Ainsi,

\left\lfloor \dfrac{k}{2} \right\rfloor = \left\lfloor \dfrac{2m}{2} \right\rfloor = \left\lfloor m \right\rfloor = m c’est-à-dire \left\lfloor \dfrac{k}{2} \right\rfloor = \dfrac{k}{2}.

• Si k est impair, alors k = 2m+1m est un entier. Par suite,

\left\lfloor \dfrac{k}{2} \right\rfloor = \left\lfloor \dfrac{2m+1}{2} \right\rfloor = \left\lfloor m + \dfrac{1}{2} \right\rfloor = m = \dfrac{(2m+1)-1}{2} c’est-à-dire \left\lfloor \dfrac{k}{2} \right\rfloor = \dfrac{k -1}{2}

Voyons  alors comment cela nous permet d’étudier la suite C(n).

Prise en sandwich (au boeuf)

En appliquant le résultat précédent à k= C(n)/2, on a les inégalités:

\dfrac{C(n)-1}{2} \leqslant \left\lfloor \dfrac{C(n)}{2} \right\rfloor \leqslant \dfrac{C(n)}{2}

En ajoutant C(n) dans chaque membre, on obtient

C(n) + \dfrac{C(n)-1}{2} \leqslant C(n) + \left \lfloor \dfrac{C(n)}{2} \right\rfloor \leqslant C(n) + \dfrac{C(n)}{2}

Autrement dit,   \dfrac{3}{2}C(n) - \dfrac{1}{2} \leqslant C(n+1) \leqslant \dfrac{3}{2}C(n).

Ce raisonnement nous incite donc à considérer les deux suites (u_n) et (v_n) définies de la manière suivante:

\begin{cases} u_0 = 2 \\ u_{n+1} = \dfrac{3}{2} u_n - \dfrac{1}{2} \end{cases}     et      \begin{cases} v_0 = 2 \\ v_{n+1} = \dfrac{3}{2} v_n \end{cases}

et nous allons montrer par récurrence que pour tout entier naturel n, u_n \leqslant C(n) \leqslant v_n.

• Si n=0 alors il est clair que u_0 \leqslant C(0) \leqslant v_0.

• Supposons que u_n \leqslant C(n) \leqslant v_n. Nous avions vu que \dfrac{C(n)-1}{2} \leqslant \left\lfloor \dfrac{C(n)}{2} \right\rfloor \leqslant \dfrac{C(n)}{2} donc en ajoutant membre à membre ces deux relations, on obtient

u_n + \dfrac{C(n)-1}{2} \leqslant C(n) + \left\lfloor \dfrac{C(n)}{2} \right\rfloor \leqslant v_n + \dfrac{C(n)}{2}

Or, par hypothèse de récurrence, u_n \leqslant C(n) donc \dfrac{u_n - 1}{2} \leqslant \dfrac{C(n) - 1}{2}. De même, C(n) \leqslant v(n) entraîne que \dfrac{C(n)}{2} \leqslant \dfrac{v(n)}{2}. Ainsi,

u_n + \dfrac{u_n - 1}{2} \leqslant u_n + \dfrac{C(n)-1}{2} \leqslant C(n) + \left\lfloor \dfrac{C(n)}{2} \right\rfloor \leqslant v_n + \dfrac{C(n)}{2} \leqslant v_n + \dfrac{v_n}{2}

En ne gardant que les inégalités les plus extrêmes, on a

u_n + \dfrac{u_n - 1}{2} \leqslant C(n) + \left\lfloor \dfrac{C(n)}{2} \right\rfloor  \leqslant v_n + \dfrac{v_n}{2}

c’est-à-dire \dfrac{3}{2} u_n - \dfrac{1}{2}  \leqslant C(n) + \left\lfloor \dfrac{C(n)}{2} \right\rfloor   \leqslant \dfrac{3}{2}v_n et donc u_{n+1} \leqslant C(n+1) \leqslant v_{n+1}. CQFD.

Encadrement du nombre de vaches

Autant il n’est pas simple de trouver une forme explicite à la suite C(n), autant les suites (u_n) et (v_n) sont faciles à étudier. En effet, la suite (u_n) étant une suite arithmético-géométrique (u_{n+1} = \dfrac{3}{2}u_n - \dfrac{1}{2}), nous savons alors que :

u_n = \left( \dfrac{3}{2}\right)^n \times \left( u_0 - \dfrac{-\frac{1}{2}}{1- \frac{3}{2}} \right) + \dfrac{-\frac{1}{2}}{1- \frac{3}{2}}

c’est-à-dire u_n = \left( \dfrac{3}{2}\right)^n \times \left( 2 - \dfrac{-\frac{1}{2}}{- \frac{1}{2}} \right) + \dfrac{-\frac{1}{2}}{- \frac{1}{2}} donc u_n = \left( \dfrac{3}{2}\right)^n + 1

D’autre part, la suite (v_n) étant géométrique (v_{n+1} = \dfrac{3}{2}v_n), on a donc

v_n = v_0 \times \left( \dfrac{3}{2}\right)^n = 2 \times \left( \dfrac{3}{2}\right)^n

Nous en déduisons l’encadrement suivant du nombre de vaches qu’il est possible de générer au bout de la n-ème étape:

\boxed{ \vphantom{\dfrac{\frac{X}{X}}{\frac{X}{X}}}  \left( \dfrac{3}{2}\right)^n + 1 \leqslant C(n) \leqslant 2 \times \left( \dfrac{3}{2}\right)^n  }

Autrement dit, la croissance du nombre de vaches est de l’ordre de \left(\dfrac{3}{2}\right)^n c’est-à-dire que c’est une croissance exponentielle !

Par exemple, si vous voulez générer 10^{80} vaches, c’est-à-dire autant que le nombre d’atomes dans l’univers observable, il suffit que n vérifie

10^{80} \leqslant  \left( \dfrac{3}{2} \right)^n \leqslant C(n) \iff \dfrac{\ln(10^{80})}{\ln(3/2)} \leqslant n

Ainsi, il suffit de n = 455 étapes pour obtenir 10^{80} vaches, ce qui représente 454 \times 20 \text{mn} = 9080\text{mn}, soit 6 jours, 7 heures et 20 minutes de jeu, donc moins d’une semaine… la vache !

Notes:

  • La suite du nombre de vaches que nous avons étudiée dans cet article est référencée sur la très sérieuse Encyclopédie en ligne des suites de nombres entiers: https://oeis.org/A061418 . On y apprend d’ailleurs qu’il existe une formule explicite pour cette suite: C(n) = \left\lceil K \times \left( 3/2 \right)^n \right\rceil\left\lceil x \right\rceil désigne la partie entière par excès de x et où K\approx 1,08151366859... est une constante.
  • Pour ceux qui connaissent la notation grand thêta, nous avons en fait démontré dans cet article que C(n) = \Theta( \left( 3/2 \right)^n ).
Publié dans Nombres | Tagué , , , , , , | 1 commentaire

GaBuZoMeu…GaBuZoMeu

Dans la numération Shadok, il n’y a que quatre chiffres: Ga (zéro), Bu (un), Zo (deux) et Meu (trois). Tous les nombres sont alors fabriqués à partir de ces quatre chiffres selon un système de numération par position: autrement dit, les Shadoks comptent en base 4. Par exemple, le nombre ZoBuMeu vaut 2 \times 4^2 + 1 \times 4^1 + 3 \times 4^0 = 39.

Tout cela est beaucoup mieux expliqué (et surtout de manière beaucoup plus drôle) par les Shadoks eux-mêmes dans la (courte) vidéo ci-dessous:

Ce que nous allons voir dans cet article, c’est que les nombres:

  • GaBuZoMeu
  • GaBuZoMeuGaBuZoMeu
  • GaBuZoMeuGaBuZoMeuGaBuZoMeu
  • etc.
  • GaBuZoMeuGaBuZoMeuGaBuZoMeu…GaBuZoMeu (où GaBuZoMeu est répété n fois)

renferment quelques propriétés insoupçonnées !

Ga) Des exemples pour commencer

Le nombre GaBuZoMeu signifie dans notre système décimal

0 \times 4^3 + 1 \times 4^2 + 2 \times 4^1 + 3 \times 4^0 = 27

La décomposition de GaBuZoMeu en produit de facteurs premiers est donc GaBuZoMeu = 3^3. De même, GaBuZoMeuGaBuZoMeu vaut

0 \times 4^7 + 1 \times 4^6 + 3 \times 4^5 + 4 \times 4^4 + 0 \times 4^3 + 1 \times 4^2 + 3 \times 4^1 + 4 \times 4^0 = 6939

et sa décomposition en produit de facteurs premiers est 3^3 \times 257.

Vous avez sans doute deviné le principe: on va décomposer  les nombres GaBuZoMeuGaBuZoMeu…GaBuZoMeu (où GaBuZoMeu est répété n fois) en produit de facteurs premiers puis voir ce qui se passe…

Bu) Une conjecture

Voici donc les résultats obtenus pour les premières valeurs de n:

\begin{array}{|r|r|r|}  \hline  n & \text{ GaBuZoMeu...GaBuZoMeu en base 10} & \text{ D\'ecomposition en facteurs premiers} \\ \hline  1 & 27 & 3^3 \\  2 & 6 \, 939 & 3^3 \times 257 \\  3 & 1 \, 776 \, 411 & 3^4 \times 7 \times 13 \times 241\\  4 & 454 \, 761 \, 243 & 3^3 \times 257 \times 65537\\  5 & 116 \, 418 \, 878 \, 235 & 3^3 \times 5 \times 11 \times 31 \times 41 \times 61681 \\  6 & 29 \, 803 \, 232 \, 828 \, 187 & 3^4 \times 7 \times 13 \times 97 \times 241 \times 257 \times 673 \\  7 & 7 \, 629 \, 627 \, 604 \, 015 \, 899 & 3^3 \times 29 \times 43 \times 113 \times 127 \times 15 790321 \\ \hline  \end{array}

On remarque que la décomposition en facteurs premiers des nombres GaBuzoMeu…GaBuZoMeu est assez particulière: elle semble toujours commencer par une puissance de 3 et tous les autres facteurs premiers apparaissent à la puissance 1.

Par exemple, le nombre GaBuZoMeuGaBuZoMeuGaBuZoMeu  = 3^4 \times 7 \times 13 \times 241 ne possède aucun facteur premier à une puissance supérieure ou égale à 2 (hormis 3 bien entendu) car 7, 13 et 241 apparaissent à la puissance 1. Voici donc la conjecture que l’on peut émettre:

[Conjecture]
La décomposition en produit de facteurs premiers du nombre GaBuZoMeu…GaBuZoMeu est le produit d’une puissance de 3 avec un nombre sans facteurs carrés.

Autrement dit, cette conjecture dit que si le nombre GaBuZoMeu…GaBuZoMeu est divisible par un nombre p>3 alors il n’est pas divisible par p^2.

Avant de lire la suite, vous pouvez peut-être essayer de trouver un contre-exemple à cette conjecture (mais sachez qu’elle est vérifiée au moins jusqu’à n=10…).

Zo) Expression générale du nombre GaBuZoMeu…GaBuZoMeu 

Afin de prouver ou d’infirmer notre conjecture, nous allons essayer de donner une expression du nombre N = GaBuZoMeu…GaBuZoMeu (n fois). Pour cela, nous allons devoir manipuler quelques sommes. Si cela est beaucoup trop indigeste pour vous, vous pouvez directement passer à la section suivante.

Tout d’abord, par définition même du nombre N = GaBuZoMeu…GaBuZoMeu,

\displaystyle N = \sum_{k=0}^{n-1} 0 \times 4^{3 + 4k} + 1 \times 4^{2+ 4k} + 2 \times 4^{1+ 4k} + 3 \times 4^{0+4k}

Ainsi,

\begin{array}{lcl}  N & = & \displaystyle 0 \times \sum_{k=0}^{n-1} 4^3 \times 4^{4k} + 1 \times \sum_{k=0}^{n-1} 4^2 \times 4^{4k} + 2 \times \sum_{k=0}^{n-1} 4^1 \times 4^{4k} + 3 \times \sum_{k=0}^{n-1} 4^0 \times 4^{4k}\\[10pt]  & = & \displaystyle 0 \times 4^3 \times \sum_{k=0}^{n-1} 4^{4k} + 1 \times 4^2 \times \sum_{k=0}^{n-1} 4^{4k} + 2 \times 4^1 \times \sum_{k=0}^{n-1} 4^{4k} + 3 \times 4^0 \times \sum_{k=0}^{n-1} 4^{4k}\\[10pt]  & = & \displaystyle 0 \times \sum_{k=0}^{n-1} 4^{4k} + 16 \times \sum_{k=0}^{n-1} 4^{4k} + 8 \times \sum_{k=0}^{n-1} 4^{4k} + 3 \times \sum_{k=0}^{n-1} 4^{4k} \\[10pt]  & = & \displaystyle 27 \times \sum_{k=0}^{n-1} 4^{4k} \\[10pt]  & = & \displaystyle 27 \sum_{k=0}^{n-1} {\left(2^8\right)}^{k} \\[10pt]  \end{array}

Pour finir, on applique la fameuse formule sur la somme des termes d’une suite géométrique (un classique !) pour obtenir

N = 27 \times \dfrac{ \left(2^8\right)^n - 1}{2^8 - 1} = \dfrac{27 ( 2^{8n} - 1)}{255}= \dfrac{9 (2^{8n}-1)}{85}

Finalement le nombre N = GaBuZoMeu…GaBuZoMeu (n fois) est égal à:

\boxed{N= \dfrac{ 3^2 ( 2^{8n} - 1)}{5 \times 17} }

Nous sommes encore loin d’avoir prouvé ou infirmé notre conjecture, mais, tout de même, cette formule nous montre que les nombres GaBuZoMeu…GaBuZoMeu s’expriment beaucoup plus facilement qu’on aurait pu penser !

Meu) 42 est la réponse…

D’après la formule précédente, pour trouver les diviseurs de GaBuZoMeu…GaBuZoMeu, il suffit de trouver les diviseurs de 2^{8n} - 1. Il se trouve que ce dernier est un nombre de Mersenne c’est-à-dire un nombre de la forme 2^k - 1 mais ce n’est pas cela que nous allons utiliser pour le moment.

D’après le théorème d’Euler, on sait que pour tout nombre impair m, comme 2 est premier avec m^2 alors 2^{\varphi(m^2)} \equiv 1 \mod[m^2]\varphi est la fonction indicatrice d’Euler.  En prenant la puissance 8 des deux côtés de cette relation, on obtient

2^{8\varphi(m^2)} \equiv 1 \mod[m^2]

Cela veut donc dire que m^2 divise toujours 2^{8 \varphi(m^2)}-1. Pour trouver des contre-exemples, il suffit donc de choisir un nombre impair m et de poser n=\varphi(m^2); le nombre m^2 divisera alors 2^{8n}-1.

Par exemple, si on prend m=7, cela donne n=\varphi(7^2) = 42. D’après ce qu’on vient de voir, le nombre 2^{8 \times 42}-1 est divisible par 7^2 (vous ne me croyez pas ?) donc notre conjecture est fausse car le nombre GaBuZoMeu…GaBuZoMeu (42 fois) est divisible par 7^2. Sur le même principe, on peut même construire une infinité de contre-exemples en prenant n=\varphi(m^2)m est presque n’importe quel nombre impair !

Je dis « presque » car on ne pouvait pas prendre m=5 (ce qui donnerait n = \varphi(5^2)= 20 ) car, bien que 2^{8 \times 20}-1 est divisible par 25 = 5^2, il ne faut pas oublier qu’il y avait un facteur 5 au dénominateur du nombre \dfrac{3^2 (2^{8n}-1)}{5 \times 17}, nombre qui ne serait donc pas forcément divisible par 25. De même, pour m=17, le nombre n= \varphi(17^2) = 272 n’est pas forcément un contre-exemple car il n’est pas nécessairement divisible par 17^2. Enfin, pour m=3 (et donc n=\varphi(3^2) = 6), la seule chose qu’on pourrait dire du nombre GaBuZoMeu…GaBuZoMeu (6 fois), c’est qu’il est divisible par 3^2, ce qui était autorisé dans notre conjecture. Enfin, prendre m=1 n’a aucun intérêt car cela voudrait juste dire que le nombre est divisible par 1^2 (voilà enfin la fameuse remarque à la con que l’on retrouve dans chaque article de ce blog).

Ainsi, n=42 = \varphi(7^2) était donc le plus petit contre-exemple possible avec cette méthode et voici la liste des premiers contre-exemples obtenus similairement (c’est-à-dire en prenant n = \varphi(m^2) pour m impair différent de 1, 3, 5 et 17):

n = 42, 54, 110, 156, 120, 342, 252, 506, 500, 486, 812, 930, 660, 840, 1332, \\ 936, 1640, 1806, 1080, 2162, 2058, 1632, 2756, 2200, 2052, 3422, 3660, 2268, 3120, \\ 4422, 3036, 4970, 5256, 3000, 4620, 6162, 4374, 6806, 5440, 4872, 7832, 6552, 5580,  \\ 6840, 9312, 5940,...

Vous remarquez que tous ces contre-exemples sont pairs. Sans rentrer dans les détails, cela vient du fait (pas difficile à prouver) que \varphi(a) est un nombre pair si a>1 est un nombre impair. Une question légitime que l’on pourrait alors se poser est: existe-t-il des contre-exemples avec n impair ? Pour le savoir, il va falloir étudier les choses d’un peu plus près…

BuGa) À la recherche d’autres contre-exemples

Nous allons affiner notre recherche de contre-exemples grâce à une propriété donnant une condition nécessaire pour qu’un nombre de Mersenne d’exposant un nombre premier possède un facteur carré. La voici (et vous pourrez en trouver une démonstration en fin d’article):

Si un nombre de Mersenne 2^q - 1 (avec q premier) est divisible par p^2p est un nombre premier, alors p est un nombre premier de Wieferich.

Là, c’est le moment où tout le monde se demande ce que peut bien être un nombre premier de Wieferich. Un nombre premier de Wieferich est un nombre premier p tel que p^2 divise le nombre de Mersenne 2^{p-1}-1. Par exemple, le nombre premier p=1093 est un nombre de Wieferich car son carré divise le nombre 2^{1093-1}-1 = 2^{1092}-1 (vous ne me croyez toujours pas ?).

Des nombres premiers de Wieferich, il n’y en a pas beaucoup. A vrai dire, on n’en connaît que deux à l’heure actuelle : 1093 et 3511. Cependant, vous allez voir que cela nous sera largement suffisant !

Revenons au nombre GaBuZoMeu…GaBuZoMeu (n fois) dont a vu qu’il était égal à \dfrac{3^2 \left(2^{8n}-1\right)}{5\times 17}. Pour montrer qu’il possède un facteur carré, il suffirait de faire apparaître 2^{1092}-1 dans cette expression, de sorte que 1093^2 diviserait ce nombre.

Pour faire cela, commençons par remarquer qu’on a la factorisation suivante (merci aux identités remarquables !):

X^{8n} - 1 = (X^{4n})^2 - 1^2 = (X^{4n} -1) (X^{4n}+1)

Or, X^{4n}-1 = (X^{2n})^2 - 1^2 = (X^{2n} -1) (X^{2n}+1) donc

X^{8n}-1 = (X^{2n} -1) (X^{2n}+1)(X^{4n}+1)

Comme (X^{2n} -1) = (X^n - 1) (X^n +1), on a donc

X^{8n}-1 = (X^n - 1) (X^n +1)(X^{2n}+1)(X^{4n}+1)

Nous pouvons donc à présent transformer l’expression de N = GaBuZoMeu…GaBuZoMeu en

N = \dfrac{3^2 \left(2^{8n}-1\right)}{5\times 17} = \dfrac{3^2 (2^n - 1) (2^n +1)(2^{2n}+1)(2^{4n}+1)}{5\times 17}

Nous voyons donc qu’en prenant n = 1092, le nombre GaBuZoMeu…GaBuZoMeu (où GaBuZoMeu est répété 1092 fois) s’écrira

N = \dfrac{3^2 (2^{1092} - 1) (2^{1092} +1)(2^{2184}+1)(2^{4368}+1)}{5\times 17}

et il sera bien divisible par 1093^2 car 1093 est un nombre premier de Wieferich c’est-à-dire que 1093^2 divise 2^{1092}-1. Nous voilà donc avec un autre contre-exemple à notre conjecture qui n’était pas dans notre liste !

Cependant, 1092 n’est pas un contre-exemple impair donc nous n’allons pas nous arrêter là dans notre recherche. On sait que 1093^2 divise 2^{1092}-1, mais en fait il divise des nombres de Mersenne plus petits encore. Un petit algorithme permet de voir que 1093^2 divise aussi 2^{728}-1 et même 2^{364} -1.  Ainsi, de la même façon que précédemment on voit qu’en prenant n=728 ou n=364 on obtient deux nouveaux contre-exemples à notre conjecture qui n’étaient pas dans notre liste.

Mais on peut encore faire mieux ! Il se trouve que le nombre 728 est un multiple de 8 car 728 = 8 \times 91. En reprenant la première formule que nous avions vue, à savoir N= \dfrac{3^2 \left(2^{8n}-1\right)}{5\times 17}, pour n=91, on obtient:

N= \dfrac{3^2 \left(2^{8\times 91}-1\right)}{5\times 17} = \dfrac{3^2 \left(2^{728}-1\right)}{5\times 17}

ce qui prouve que le nombre GaBuZoMeu…GaBuZoMeu où GaBuZoMeu est répété 91 fois est divisible par 1093^2 et n’est donc pas sans facteur carré ! On peut même le vérifier « directement » car ce nombre à 219 chiffres (!) est égal à

149506621343376220426717526940245004530365795333318\ \\  81013029774928096614396029874411266391346445335278\ \\  08122399381444468776653510105465030501684645752728\ \\  38323281630381313790853442080521484907833820669507\ \\  266526533960538907

et sa décomposition en produit de facteurs premiers est

3^3 \times 29 \times 43 \times 53 \times 113 \times 127 \times 157 \times 911 \times 1\,0 93^2 \times 1 \, 613 \times 2 \, 731 \times 4 \, 733 \times 8 \, 191 \times 224 \, 771 \times 858 \, 001 \times 1 \, 210 \, 483 \times 15 \, 790 \, 321 \times 112 \, 901 \, 153 \times 308 \, 761 \, 441 \times 23 \, 140 \, 471 \, 537 \times 25 \, 829 \, 691 \, 707 \times 593 \, 914 \, 915 \, 675 \, 537 \times 8 \, 861 \, 085 \, 190 \, 774 \, 909 \times 556 \, 338 \, 525 \, 912 \, 325 \, 157 \times \\ 88 \, 969 \, 9 72 \, 427 \, 0 95 \, 486 \, 8 38 \, 263 \, 4 04 \, 334 \, 1 55 \backslash \\ \, 574 \, 0 24 \, 974 \, 1 98 \, 424 \, 7 57 \, 8510 \, 445 \, 178 \, 451 \, 442 \, 481 \, 793

Vous voyez donc bien qu’il y a un facteur carré ! Cela dit, il restera une question en terminant cet article: n=91 est-il le plus petit contre-exemple impair à cette conjecture ?

Notes:

  • Les calculs de décomposition en produit de facteurs premiers ont été effectués grâce à ce site (qui utilise la méthode de factorisation par les courbes elliptiques… fallait bien ça pour factoriser des nombres de 219 chiffres !)
  • Voici une démonstration de la propriété disant que si un nombre de Mersenne d’exposant premier est divisible par un facteur carré alors il est divisible par un nombre premier de Wieferich.
Publié dans Arithmétique, Nombres | Tagué , , , , | 11 commentaires