Two

[Buridan]

Un petit défi qu'on ma posé...

Est-il possible de trouver un entier uniquement composé de 2 qui soit divisible par 1986 ? Si oui, quel est le plus petit de ces entiers ?

Et je n'ai pas la réponse... :hum:

[mathafou]

Bonjour,

Est-il possible de trouver un entier uniquement composé de 2 qui soit divisible par 1986 ? Si oui, quel est le plus petit de ces entiers ?

facile ...

le nombre composé de 330 chiffres 2 est divisible par 1986
il n'y en a pas de plus petit
par contre tous les nombres composés de 330n chiffres 2 le sont aussi

(la flemme de tout retaper, j'avais commencé à taper les détails quand "prévisualisation" et paf plus d'internet pendant une demi heure à part "impossible d'accèder à quoi que ce soit"...)

cherche du côté de via théorème d'Euler Fermat, ou par force brute en faisant les calculs de proche en proche (donc aucun nombre > si on est malin)

[Buridan]

Bonjour,
facile ...

le nombre composé de 330 chiffres 2 est divisible par 1986
il n'y en a pas de plus petit
par contre tous les nombres composés de 330n chiffres 2 le sont aussi

(la flemme de tout retaper, j'avais commencé à taper les détails quand "prévisualisation" et paf plus d'internet pendant une demi heure à part "impossible d'accèder à quoi que ce soit"...)

cherche du côté de via théorème d'Euler Fermat, ou par force brute en faisant les calculs de proche en proche (donc aucun nombre > si on est malin)

Merci mathafou !
D'autres trouvent-ils pareil ?

[Matt_01]

Ben le nombre avec n fois le nombre 2 est égal à 2*(10^n-1)/9.
Sachant que 1986 = 2*331*3 et que 2*331 est premier avec 3, il suffit que 2*(10^n-1) soit divisible par 2*331 et donc 10^n-1 divisible par 331.
Il suffit donc de chercher l'ordre de 10 dans Z/331Z.
On doit chercher dans les diviseurs de 330 = 2*3*5*10 (car l'ordre de 10 divise 330 par Fermat).
Et on se rend compte que le plus petit qui convient est 330 et donc n est multiple de 330.

[mathafou]

Merci mathafou !
D'autres trouvent-ils pareil ?

la démonstration et la méthode :
un nombre composé uniquement de n chiffres 2 est le double du nombre composé du même nombre n de chiffres 1
en d'autres termes on cherche un nombre composé uniquement de n chiffres 1 (dit "repunit") qui soit multiple de 1986/2 = 993
ce nombre est 1/9 de celui composé de n chiffres 9 qui est 1 de moins que 1 suivi de n zéros

on cherche donc finalement un n tel que 10^n - 1 soit multiple de 9x993 = 8937,
et plus particulièrement le plus petit d'entre eux.

Le théorème d'Euler-Fermat affirme que si 10 et 8937 sont premiers entre eux, ce qui est le cas, alors
10^phi(8937) - 1 est divisible par 8937
phi(8937) est "l'indicateur d'Euler" de 8937 c'est à dire le nombre de nombres premiers avec 8937 et < 8937 (1 compris)
On décompose 8937 en nombres premiers 3^3×331 et l'indicateur d'Euler est 3^3×331(1-1/3)(1-1/331) = 18x330 = 5940

le plus petit n cherché sera un diviseur de 5940, au pire (le théorème) 5940 lui-même.
on les essaye tous (il y en a 48, 1 et 5940 compris) pour trouver le plus petit de ces diviseurs tel que 10^n - 1 soit multiple de 8937

(= on fait un programme, parce que les 48 diviseurs un par un à la main .. bof)
en fait foin de ces complications, on essaye brutalement tous les entiers n <= 5940 (c'est plus "direct" par programme que de se limiter aux seuls diviseurs de 5940 !)


bien en entendu on ne calcule absolument pas les valeurs de ces nombres astronomiques
juste leur reste dans la division par 8937
10^1 reste 10
10^2 reste 100
A0^3 reste 1000 (jusqu'ici sans aucun "calcul")
10^4 reste 1063
10^5 a même reste que 10x1063 = 10630, c'est à dire 1693
10^6 même reste que 10x1693 c'est à dire 7993
...
10^330 a pour reste 1 et c'est fini.

et donc (10^330)^k = 1^k = 1 modulo 8937 donne que tous les nombres composés de 330k chiffres 2 répondent au problème, le plus petit étant pour k = 1

on peut chercher une méthode un peu plus rapide que calculer tous les diviseurs successifs de 5940 mais bof ... la complication n'est pas franchement rentable pour "si peu" de diviseurs.
Surtout que c'est le programme de deux lignes qui fait le calcul ! en effectuant juste 330 boucles avant de s'arrêter, donc solution "instantanément", au pire on sait qu'il aurait fait au plus 5940 boucles, une broutille, et les nombres les plus grands qu'il a à manipuler sont 10x5940)

[Buridan]

la démonstration et la méthode :
un nombre composé uniquement de n chiffres 2 est le double du nombre composé du même nombre n de chiffres 1
en d'autres termes on cherche un nombre composé uniquement de n chiffres 1 (dit "repunit") qui soit multiple de 1986/2 = 993
ce nombre est 1/9 de celui composé de n chiffres 9 qui est 1 de moins que 1 suivi de n zéros

on cherche donc finalement un n tel que 10^n - 1 soit multiple de 9x993 = 8937,
et plus particulièrement le plus petit d'entre eux.

Le théorème d'Euler-Fermat affirme que si 10 et 8937 sont premiers entre eux, ce qui est le cas, alors
10^phi(8937) - 1 est divisible par 8937
phi(8937) est "l'indicateur d'Euler" de 8937 c'est à dire le nombre de nombres premiers avec 8937 et < 8937 (1 compris)
On décompose 8937 en nombres premiers 3^3×331 et l'indicateur d'Euler est 3^3×331(1-1/3)(1-1/331) = 18x330 = 5940

le plus petit n cherché sera un diviseur de 5940, au pire (le théorème) 5940 lui-même.
on les essaye tous (il y en a 48, 1 et 5940 compris) pour trouver le plus petit de ces diviseurs tel que 10^n - 1 soit multiple de 8937

(= on fait un programme, parce que les 48 diviseurs un par un à la main .. bof)
en fait foin de ces complications, on essaye brutalement tous les entiers n <= 5940 (c'est plus "direct" par programme que de se limiter aux seuls diviseurs de 5940 !)


bien en entendu on ne calcule absolument pas les valeurs de ces nombres astronomiques
juste leur reste dans la division par 8937
10^1 reste 10
10^2 reste 100
A0^3 reste 1000 (jusqu'ici sans aucun "calcul")
10^4 reste 1063
10^5 a même reste que 10x1063 = 10630, c'est à dire 1693
10^6 même reste que 10x1693 c'est à dire 7993
...
10^330 a pour reste 1 et c'est fini.

et donc (10^330)^k = 1^k = 1 modulo 8937 donne que tous les nombres composés de 330k chiffres 2 répondent au problème, le plus petit étant pour k = 1

on peut chercher une méthode un peu plus rapide que calculer tous les diviseurs successifs de 5940 mais bof ... la complication n'est pas franchement rentable pour "si peu" de diviseurs.
Surtout que c'est le programme de deux lignes qui fait le calcul ! en effectuant juste 330 boucles avant de s'arrêter, donc solution "instantanément", au pire on sait qu'il aurait fait au plus 5940 boucles, une broutille, et les nombres les plus grands qu'il a à manipuler sont 10x5940)

Ouf, merci. L'énoncé me paraissait simple mais finalement ça l'est un peu moins...

[Matt_01]

mathafou se complique un peu la vie en évaluant dans Z/8937Z (on complique rapidement les calculs par rapport à Z/331Z)

[beagle]

Bonjour les fortiches, enfin les mateux aux pseudos matquelquechose (et non matquelqu'un),

pouvez me mettre comment vous faites sur un cas plus simple:
nombre avec que des 1, divisible par 7, quel est le plus petit?
je sais j'abaisse un peu le niveau, mais je peux pas baigner non plus là où j'ai pas pieds,...

[Ben314]

Bonjour les fortiches, enfin les mateux aux pseudos matquelquechose (et non matquelqu'un),

pouvez me mettre comment vous faites sur un cas plus simple:
nombre avec que des 1, divisible par 7, quel est le plus petit?
je sais j'abaisse un peu le niveau, mais je peux pas baigner non plus là où j'ai pas pieds,...

Tu écrit que donc le problème consiste à trouver n tel que soit divisible par 7, c'est à dire que soit divisible par .
Comme 7 et 9 sont premiers entre eux, pour que N soit divisible par , il faut et il suffit que N soit divisible par 7 et qu'il soit divisible par 9.
Or il est forcément divisible par 9 (vu que est entier) donc il suffit qu'il soit divisible par 7, c'est à dire que (10 puissance n congru à 1 modulo 7)
Arrivé à ce point, on peut y aller "en tatonant", c'est à dire en essayant n=1, n=2, etc (pour passer d'un n au suivant, on multiplie par 10 puis on considère le reste de la division par 7) jusqu'à ce qu'on tombe sur le plus petit n qui marche. Les "autres" n qui marchent seron alors clairement les multiples de ce n là (car )
On peut aussi faire un peu plus de théorie en utilisant la fait que l'ensemble des éléments inversibles de Z/7Z est un groupe de cardinal (indicatrice d'euler) ce qui permet d'être sûr que et cela montre que le plus petit n tel que est un diviseur de 6, c'est à dire 1,2,3 ou 6. Cela permet clairement de gagner du temps, vu que, si , et ne sont pas congrus à 1 modulo7, alors c'est réglè, c'est que le plus petit n tel que est n=6.

[beagle]

OK, Ben314 , merci, avec les messages précédents cela s'éclaire bien.
Je ne connaissais pas l'indicatrice d'Euler, (et mème modulo jamais bossé cela au lycée, mais vu ça sur ce forum).

j'imagine qu'il y a un lien entre l'indicatrice d'Euler, et la séquence répétitive je sais pas comment cela s'appelle des puissances n de 10 divisées par k.
Lorsque l'on divise de la puissance de 10 par k =7, on retombe en reste sur :
1,3,2,6,4,5 et cela se répète 1,3,2,6,4,5...
comme on a avec les 6 de la séquences les compléments 1+6,2+5,3+4,
ben arrivé à 5 c'est ok pour zéro modulo 7,
donc les 6 fois le 1, 111111 sera bon et le premier.
6 qui est l'indicatrice d'Euler pour 7

Pour k=13, indicatrice d'Euler est 12, un diviseur de 12 attendu,
et que voit-on
la répétition de diviser puissance de 10 par 13 c'est:
1,10,9,12,3,4 et on recommence 1,10,9,12,3,4
là encore on a dans la répétition des compléments à 13, donc arrivé à 4, bingo zéro modulo 13
Donc indicatrice d'Euler 12 et là le diviseur 6 marche.

Pour 331, nombre premier, l'indicatrice d'Euler est donc 330,
c'est un diviseur de 330 attendu,
sauf que là faut aller jusqu'à les 330 pour gagner.

L'indicatrice d'Euler joue bien comme cela sur les séquences répétitives de la division des puissances de 10 par un k, en ce qui concerne le problème de ce fil?C'est un peu ça qui se joue?

one shoot again:
pour 31, indicatrice d'Euler est 30, attendu cela doit marcher avec du multiple des 2,3,5
ben la répétion des restes de la division puissances 10 par 31, survient après 15 restes, la somme de ces 15 restes est 186 qui est 6x31, donc zéro modulo.
et 15 fois du 1 est bien divisible par 31.

[Ben314]

...mème modulo jamais bossé cela au lycée, mais vu ça sur ce forum...

La notion de modulo, ç'est on ne peut plus simple :
- Il y a la définition : " est congru à modulo " qui signifie que est un multiple de :
- Il y des façons équivalentes (et à peine différentes) de voir la définition, par exemple " divise " ou bien " et ont le même reste de division par "
- Et il y a surtout les propriétés de compatibilités de la relation "est congru à" qui disent que, si et alors forcément et (trés façile à démontrer en revenant à la définition).

Jusque là, cela permet de faire des calculs avec le symbole "est congru à" à peu prés de la même manière qu'avec le symbole "égal" : ajouter, retrancher ou multiplier une congruence des deux cotés pour "faire passer" certains termes d'un coté à l'autre, par exemple passer de à .
Par contre, il y a de grosses différences lorsque l'on commence à parler de "division". Peut on par exemple résoudre l'équation (d'inconnue x) ?
Dans R, pour résoudre une telle équation, on divise par 3 des 2 cotés, c'est à dire, pour être plus précis, on multiplie par 1/3 des deux cotés ou 1/3 est l'inverse de 3, c'est à dire le réel tel que .
Ici, 3 a-t'il un "inverse modulo 10", c'est à dire existe t'il un entier tel que ?
Si on revient à la définition, cela signifie qu'on cherche deux entiers et tels que c'est à dire tels que . Arrivé à ce point, on reconnait une Identité de Bézout et on sait qu'il y a des solutions du fait que 3 et 10 sont premiers entre eux (et l'algorithme d'Euclide étendu permet même de trouver lesquelles).
Ici, par exemple (et ) est une solution.
Donc 7 est un inverse de 3 modulo 10 et, pour résoudre , il suffit de multiplier par 7 des deux cotés : , c'est à dire (car et )

Aprés, le problème, c'est que tout les entiers ne sont pas inversibles modulo 10 (seuls ceux qui sont premiers avec 10 le sont) donc par exemple l'équation ne peut pas se résoudre en multipliant par l'inverse de 4 des deux cotés (vu que 4 n'a pas d'inverse...). Mais si on revient à la définition, l'équation se ramène à et on voit clairement qu'il n'y a pas de solutions vu que 4x-10k, étant forcément pair, ne peut pas être égal à 7.

[Ben314]

Jj'imagine qu'il y a un lien entre l'indicatrice d'Euler, et la séquence répétitive je sais pas comment cela s'appelle des puissances n de 10 divisées par k.

Oui : l'indicatrice d'Euler d'un entier naturel donné, c'est le nombre d'entiers qui sont premiers avec (i.e. qui n'ont pas de diviseurs communs). Par exemple :
car, entre 1 et 10, les seuls nombres premiers avec 10 sont 1,3,7,9
car, entre 1 et 15, les seuls nombres premiers avec 15 sont 1,2,4,7,8,11,13,14
Si est un nombre premier alors, clairement, .
Si on s'interesse au puissance d'un nombre donné par exemple modulo un autre nombre donné, par exemple en supposant que et sont premiers entre eux (ce qui est le cas de 7 et 15), alors, il est clair que tout les seront eux aussi premiers avec .
Par exemple, avec , cela signifie que les différentes puissances de feront parti de l'ensemble à 8 éléments {1,2,4,7,8,11,13,14}.
En fait, modulo 15, on a
Donc en fait, en calculant les puissances de 7, on n'a pas obtenu les 8 valeurs possibles {1,2,4,7,8,11,13,14} mais seulement 4 d'entres elles, à savoir {1,4,7,13} et on a, par exemple, jamais obtenu la valeur 2.
Sauf que, si on regarde l'ensemble on obtient trés précisément l'ensemble des 4 éléments de {1,2,4,7,8,11,13,14} que l'on avait pas obtenu comme étant des puisssances de 7.
Je te laisse réfléchir au "pourquoi" un tel résultat est "logique" ainsi qu'au "pourquoi" cela explique que la plus petite puisance de 7 donnant 1 modulo 15 (puissance qui s'avère être 4) devait forcément etre un diviseur de

[beagle]

Merci Ben314 pour ces deux superbes cours, à garder en ref pour renvoyer sur d'autres personnes.

Sur modulo, a priori jamais vu au lycée à l'époque.
Donc j'ai bien vu ce qu'il en était sur le forum lycée,
et j'arrive à faire des trucs basiques, mais qui n'exploitent pas le sujet.
Je ne sais pas me reporter sur des équivalences qui permettent de limiter le problème posé.
j'avais bien vu que 4 ne pouvait marcher, mais sans comprendre la signification de inversibles...

Pour l'indicatrice d'Euler, intuitivement tu me fais comprendre pourquoi on va se limiter à un diviseur,
mais bon il y aencore du boulot de manipulation pour que je m'empare du truc.

Mais je suis très content d'avoir ramené le problème sur de plus petits nombres facilement manipulables,
parce que d'une part 331 était un peu grand, et qui plus est lui il lui faut le 330 entier et non un des diviseurs, donc 331 était bien pour l'exo initial, mais pas très pédagogique pour la comprenette.

Et bien merci encore pour ce cours.Je ferais mumuse avec quand j'aurais un peu de temps.

[Ben314]

...j'arrive à faire des trucs basiques, mais qui n'exploitent pas le sujet...

C'est en forgeant qu'on...