Défis du calendrier mathématique Retour à la rubrique

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

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.

Connexion | s’inscrire | mot de passe oublié ?

L'auteur

Ana Rechtman

Un défi par semaine

Septembre 2019, 4e défi

Solution du 3e défi de septembre :

Commentaire sur l'article