Un multiple de 2017

[Dacu]

Bonjour tout le monde,

Montrez que nombre a un multiple formé seulement avec des chiffres de .

Cordialement,

Dacu

[aviateur]

Bonjour
2017 est premier donc est un multiple de 2017 mais aussi un multiple de 9.
Donc (écriture avec 2016 chiffres "1") est un multiple de 2017
(et c'est le plus petit qui répond à la question.)

[chan79]

(et c'est le plus petit qui répond à la question.)

Salut
oui, mais comment le démontrer ?
Avec p=:
est un multiple de 1999 mais aussi.

[GaBuZoMeu]

En demandant, par exemple à Sage :

Code: Tout sélectionner

multiplicative_order(mod(10,2017))

et la réponse est bien 2016.
Par contre, à la question

Code: Tout sélectionner

multiplicative_order(mod(10,1999))

Sage répond effectivement 999.

[aviateur]

Rebonjour
Un entier k tel que 10^k=1 mod 2017 divise de 2016. Soit k le plus petit entier qui répond à la question. Alors 2016- k divise aussi 2016, la seule possibilité est donc k=1008. Mais un calcul rapide donne 10^1008=-1. J'entends par calcul rapide un calcul avec le moins d'opérations possibles, i, e faisable à la main,
Dans ton cas 10^999=1 mod 1999.

[Dacu]

Bonjour tout le monde,

Mon raisonnement:

En appliquant le petit théorème de Fermat , nous pouvons écrire que où et *.C'est vrai?
Merci très beaucoup!

Cordialement,

Dacu

[GaBuZoMeu]

@Dacu : oui.
@aviateur : ton raisonnement pour montrer que 2016 est le plus petit entier k>0 tel que 10^k=1 mod 2017 est incorrect. Je te laisse trouver ton erreur et la réparer.
Un indice : on a 10^51 = -1 mod 103, mais 102 n'est pas le plus petit entier k>0 tel que 10^k=1 mod 103.
Par ailleurs, je suis convaincu que tu n'as pas vérifié "à la main" que 10^1008 = -1 mod 2017. Une bonne dizaine de multiplications modulo 2017, ça calme. Et pour faire une vérification correcte, il faudra en faire à vue de nez le double !

[GaBuZoMeu]

Bon, je reviens sur la vérification du fait que 2016 est le plus petit entier k>0 tel que 10^k=1 mod 2017.
Il ne suffit pas de montrer que 10^1008 n'est pas 1 mod 2017. Comme
2016 = 2^5 x 3^2 x 7,
il faut aussi montrer que 10^672 et 10^288 sont aussi différents de 1 mod 2017. (672=2016/3 et 288=2016/7)

[aviateur]

Bonsoir
@Gabuzomeu. Oui, j'ai un peu écrit trop vite mon raisonnement où il manque une explication et avec une incorrection en plus plus ça semble faux.
Mais tu as bien deviné comment j'ai procédé et le calcul que j'ai fait suffit pour arriver au résultat. Alors faire "un calcul à la main" veux dire que c'est faisable avec un stylo mais rien n'interdit d'utiliser l'ordinateur.
C'est clair que ça veut surtout dire que je n'ai pas utilisé un logiciel tel que "Sage". Encore que ce n'est pas interdit de résoudre le pb avec un algo mais c'est pas le même travail.
Alors je te laisse le soin de corriger cette erreur.
Remarque: Ton exemple (103) ne s'applique pas à la question posée (i.e 2017) on n'est pas dans la même situation.

[GaBuZoMeu]

Désolé, mais je ne comprends pas ce que tu écris, et je ne vois pas pourquoi mon exemple ne montrerait pas que ton raisonnement est faux. Pour mettre les points sur les i, ton erreur est d'affirmer "Soit k le plus petit entier qui répond à la question. Alors 2016- k divise aussi 2016, la seule possibilité est donc k=1008."
Pourquoi, si c'était correct, ne pourrait-on pas affirmer de même, pour 103 au lieu de 2017 :
"Soit k le plus petit entier qui répond à la question. Alors 102- k divise aussi 102, la seule possibilité est donc k=51." ??

[chan79]

salut
Si est le plus petit entier non nul tel que modulo 2017, alors divise 2016.
Avec un simple tableur, c'est plus vite fait d'essayer tous les nombres de 1 à 2016.
Un autre exemple:
Le plus petit entier non nul tel que modulo 2287 est 762.
Pour le trouver à la main .... ?

[GaBuZoMeu]

Avec un simple tableur, c'est vite fait d'essayer tous les nombres de 1 à 2016.

Que veux-tu dire par "essayer " ? Pourquoi est-ce que ça serait incomparablement plus long d' "essayer" tous les nombres de 1 à 2286 ?

2287 est premier et 2286 = 2 x 3^2 x 127. On essaie 10^18, 10^762 et 10^1143 modulo 2287. On voit que seul 10^762 = 1 mod 2287. On essaie 10^257 et on voit qu'il n'est pas égal à 1 modulo 2287. Donc 762 est le plus petit entier k>0 tel que 10^k = 1 mod 2287, autrement dit 762 est l'ordre multiplicatif de 10 modulo 2287.

Mais puisqu'on a des logiciels libres et gratuits de calcul formel (Sage ou Xcas, utilisés pour l'épreuve de modélisation à l'agreg), pourquoi s'en priver ? La commande

Code: Tout sélectionner

multiplicative_order(mod(10,2287))

donne instantanément la réponse 762.

[GaBuZoMeu]

"On essaie 10^257" coquille : lire "On essaie 10^254"

[chan79]

Que veux-tu dire par "essayer " ? Pourquoi est-ce que ça serait incomparablement plus long d' "essayer" tous les nombres de 1 à 2286 ?

Que ce soit avec 2017 ou 2287, c'est tout aussi rapide avec un tableur( ou autre), de tester tous les entiers inférieurs à 2017 ou 2287 plutôt que simplement les diviseurs de 2016 ou 2286.

[GaBuZoMeu]

Tu n'as pas explicité ce que tu fais. J'essaie de deviner. Tu prends une colonne à 2287 cellules, dans la cellule du haut tu mets 1 et dans chaque cellule suivante tu mets =MOD(précédente*10;2287). C'est ça ?

OK. Et maintenant, on remplace 2287 par 1048583. Ton tableur est toujours partant ?

[pascal16]

vu qu'un processeur fait plus de 10 000 000 000 d'opérations par seconde, on eut monter bcp plus haut sans problème. La limitation est purement logiciel où c'est la partie affichage qui rame et non calcul.

[GaBuZoMeu]

Faut quand même pas pousser pépé dans les orties !
Procéder comme ça pour trouver le plus petit k>0 tel que 10^k = 1 mod 1048583, ça fait tout de même plus d'un million de multiplications modulo 1048583 et des problèmes d'affichage insurmontables pour le tableur.
Ce n'est pas la même chose que d'en calculer moins d'une centaine (en utilisant 1048582 = 2 * 29 * 101 * 179 et l'exponentiation rapide) pour avoir la même réponse.
Et encore, 1048583 c'est petit !

[pascal16]

en c# :

Code: Tout sélectionner

long t = 10;
            long n = 1;
            while (t!=1)
            {
                t = (t * 10) % 1048583;
                n += 1;
            }
            Console.Write(n.ToString());

réponse : n=1048582, quasi instantané, sans parallélisme

[GaBuZoMeu]

Comparons :

Code: Tout sélectionner

t=10 ; n=1
%time while t != 1 : t=10*t % 1048583 ; n+=1
n

CPU times: user 620 ms, sys: 7.57 ms, total: 627 ms
Wall time: 615 ms
1048582

Code: Tout sélectionner

p=1048583
%time L=[(p-1)/c[0] for c in list((p-1).factor())] ;\
      V=all(mod(10,p)^e !=1 for e in L)
print 'ordre multiplicatif = 1048582 :', V

CPU times: user 570 µs, sys: 56 µs, total: 626 µs
Wall time: 600 µs
ordre multiplicatif = 1048582 : True

Code: Tout sélectionner

%time multiplicative_order(mod(10,1048583))

CPU times: user 594 µs, sys: 59 µs, total: 653 µs
Wall time: 638 µs
1048582

Un facteur 1000. Une paille, quoi.

[chan79]

En choisissant des nombres assez grands, on peut mettre en difficulté n'importe quel logiciel.
Pour p=1062979, on a un résultat quasi instantané avec Python.