16 janvier 2009
Enigme pour amateurs de programmation
Combien faut-il mettre de 9 pour que le nombre "99...99" (composé uniquement de 9) soit divisible par 2009 ?
Calculatrice programmable autorisée
Libellés : Enigme
Comments:
Links to this post:
<< Home
J'essaye "à la main" :
Posons u(n)=999...9 (avec n chiffres 9).
Donc u(n)=10^n-1.
u(n) est divisible par 2009 ssi 10^n est congru à 1 modulo 2009.
D'après un théorème d'Euler, n=phi(2009) convient (j'ai noté phi l'indicatrice d'Euler). Bien noter que ce n convient mais que ce n'est pas forcément le plus petit.
Calculons :
phi(2009)=phi(7^2*41)
=phi(7^2)*phi(41)
=(7^2-7)*40
=42*40
=1680
Donc le nombre 999...9 avec 1680 chiffres 9 est divisible par 2009.
En fait, avec une machine, j'ai trouvé que 999...9 avec 210 chiffres 9 convient et que c'est le plus petit qui convient.
Merci pour les jolies questions :-)
Enregistrer un commentaire
Posons u(n)=999...9 (avec n chiffres 9).
Donc u(n)=10^n-1.
u(n) est divisible par 2009 ssi 10^n est congru à 1 modulo 2009.
D'après un théorème d'Euler, n=phi(2009) convient (j'ai noté phi l'indicatrice d'Euler). Bien noter que ce n convient mais que ce n'est pas forcément le plus petit.
Calculons :
phi(2009)=phi(7^2*41)
=phi(7^2)*phi(41)
=(7^2-7)*40
=42*40
=1680
Donc le nombre 999...9 avec 1680 chiffres 9 est divisible par 2009.
En fait, avec une machine, j'ai trouvé que 999...9 avec 210 chiffres 9 convient et que c'est le plus petit qui convient.
Merci pour les jolies questions :-)
Links to this post:
<< Home
