Un défi par semaine

Septembre 2019, 4e défi

Le 27 septembre 2019  - Ecrit par  Ana Rechtman Voir les commentaires (5)
Lire l'article en  

Nous vous proposons un défi du calendrier mathématique chaque vendredi et sa solution la semaine suivante. Le calendrier 2020 est en vente !

Semaine 39

On construit la suite de nombres $X_n$ de la
manière suivante : $X_1=19$, $X_2=95$ et
\[X_{n+2} = \left[X_{n+1},X_n\right]+X_n,\]
où $[a,b]$ dénote le plus petit commun multiple de $a$ et $b$.

Trouver le plus grand commun diviseur de $X_{2018}$ et $X_{2019}$.

Solution du 3e défi de septembre :

Enoncé

La solution est $99$.

Ecrivons le nombre initial $n$ à deux chiffres sous la forme
$n=10t+u$ avec $t$ et $u$ ses chiffres. Distinguons alors deux cas :

  • Si $u\neq9$, le nombre obtenu en ajoutant 1 puis en inversant
    les chiffres est $10(u+1)+t$. Remarquons que $10(u+1)+t\neq 10t+u$ (car sinon on aurait $u=t=u+1$, ce qui est impossible !). Donc pour que $10(u+1)+t$ soit un diviseur de $n$, il faut nécessairement qu’il soit inférieur ou égal à $\frac{n}{2}$. On a donc $2(u+1)\leq t$.

Si $u=0$, on obtient $t\geq 2$ et on a les possibilités $20, 30, 40, 50, 60$, $70$, $80$ ou $90$.

Si $u=1$, alors $t\geq 4$ et on a les possibilités $ 41, 51, 61, 71, 81$ ou $91$.
Si $u=2$, alors $t\geq 6$ et on a les possibilités $62, 72, 82$ ou $92$.

Si $u=3$, alors $t\geq 8$ et on a les possibilités $83$ ou $93$.

Si $u\geq 4$, alors $t\geq 10$, ce qui est impossible.

On vérifie un à un qu’aucun des nombres listés plus haut ne fonctionne. Par conséquent, $u$ doit être égal à 9.

  • Si $u=9$, alors $n=10t+9$ et donc si de plus $t<9$, on a $n+1 = 10 \times (t+1)$. Dans ce cas, en inversant les chiffres, on obtient $t+1$ qui ne peut pas être un diviseur de $n= 10(t+1)-1$. On doit donc avoir également $t=9$, c’est-à-dire $n=99$. Dans ce cas le nombre obtenu en ajoutant 1 puis en inversant les chiffres est $001$ qui est bien un diviseur de $99$.
Post-scriptum :

Calendrier mathématique 2019 - Sous la direction d’Ana Rechtman, avec la contribution de Nicolas Hussenot - Textes : Claire Coiffard-Marre et Ségolen Geffray. 2018, Presses universitaires de Grenoble. Tous droits réservés.

Disponible en librairie et sur www.pug.fr

Partager cet article

Pour citer cet article :

Ana Rechtman — «Septembre 2019, 4e défi» — Images des Mathématiques, CNRS, 2019

Crédits image :

Image à la une - REDPIXEL.PL / SHUTTERSTOCK

Commentaire sur l'article

  • Septembre 2019, 4e défi

    le 27 septembre à 10:22, par François

    La solution est 19.
    En effet si $d$ est un diviseur de $X_{n+2}$ et de $X_{n+1}$, il divise aussi $X_{n}$. Il divise donc $X_{1} = 19$ et $ d = 1$ ou $19$. Comme $X_{2} = 95 = 19*5$, $19$ divise tous les $X_{n}$, $X_{n} = 19k_{n}$ avec la suite $k_{n}$ croissante et vérifiant $k_{1} = 1 ,\ k_{2} = 5$ et $k_{n+2} = k_{n+1} + k_{n}$.

    Répondre à ce message
    • Septembre 2019, 4e défi

      le 27 septembre à 10:37, par François

      errata sur la formule de récurrence des $k_{n}$ : $k_{n+2} =$[$k_{n+1}$,$k_{n}$] + $k_{n}$.

      Répondre à ce message
    • Septembre 2019, 4e défi

      le 27 septembre à 16:43, par Niak

      Sauf erreur, vous démontrez que $19$ est un diviseur commun mais pas forcément le plus grand. Pour cela, il suffirait par exemple démontrer que $k_n$ et $k_{n+1}$ sont toujours premiers entre-eux. Cela se vérifie aisément par récurrence : $k_1 = 1$, $k_2 = 5$ et l’on a $k_{n+2}=[k_{n+1},k_n]+k_n = k_{n+1}\times k_n + k_n$ car $k_{n+1}$ et $k_n$ sont premiers entre-eux par hypothèse de récurrence.
      D’où $\text{PGCD}(k_{n+2},k_{n+1})=\text{PGCD}(k_{n+1}k_n+k_n,k_{n+1})=\text{PGCD}(k_n,k_{n+1}) = 1$ par hypothèse de récurrence.

      Répondre à ce message
      • Septembre 2019, 4e défi

        le 27 septembre à 17:49, par François

        Je pensais qu’il était clair que tout diviseur de $X_{n+2}$ et de $X_{n+1}$ était aussi diviseur de $X_{1} = 19$, donc que le pgcd était soit $1$ ou $19$.
        Ceci dit on a bien $k_{n+2} = k_{n}(k_{n+1}+1)$. En passant au log cela donne :
        $\ln(k_{n+2}) = \ln(k_{n+1}) +\ln(k_{n}) +\ln(1+ \frac {1} {k_{n+1}})$. Comme $\lim k_n = \infty$, cela implique que la suite $\ln(k_{n})$ est très proche d’une suite de Fibonacci. Effectivement à partir de $n = 10$ le rapport entre $\ln(k_{n})$ et la suite de Fibonacci $F_{n}$ vérifiant $F_{10} = \ln(k_{10})$ et $F_{11}=\ln(k_{11})$ vaut $1$ à $10^{-30}$ près.

        Répondre à ce message
        • Septembre 2019, 4e défi

          le 27 septembre à 23:55, par Niak

          En effet, vous avez raison, c’était très clair ! J’ai dû lire votre premier message un peu trop vite...

          Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?