Un multiple de 2017

[pascal16]

ça dit juste que l'algo de "multiplicative_order" est bien mieux optimisé, pas qu'il faut se limiter à des petits chiffres.

l'algo de multiplicativ order est peut-être celui-ci : https://rosettacode.org/wiki/Multiplicative_order

donc si m-1 est premier, il n'est pas optimisé.

[GaBuZoMeu]

donc si m-1 est premier, il n'est pas optimisé.

Il y a beaucoup de nombres premiers p tels que p-1 soit premier !
J'aimerais bien aussi une explication du "donc" ....

Mais on peut raconter tout ce qu'on veut, l'étude de complexité tranche sans ambiguïté : l'algorithme que j'ai esquissé dans mon deuxième encadré "code", et qui est donné plus en détails et analysé dans le lien donné par pascal16, fonctionne en O( (log p)^4), il est polynomial en la taille (nombre de chiffres) de p. L'algorithme qui consiste à calculer les puissances 2, 3, 4, 5, etc. est en 0(p), c.-à-d. exponentiel en la taille de p. Il n'y a pas photo.

[pascal16]

(p-1)/2 premier est le pire cas ?

[GaBuZoMeu]

Qu'appelles-tu "pire" ?
Peux-tu être plus explicite ? Merci .

[aviateur]

@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. Ce n'est pas grave si tu ne sais pas faire les calculs à la main, mais ça ne veut pas dire que c'est infaisable et il n'y a pas pléthore de calculs. On peut très bien répondre à ma question sans faire l'usage d'un algorithme. Le nombre de calculs est assez minime.

J'ai travaillé dans Z/2017 Z et non pas dans Z/103 Z. Je ne comprends pas la comparaison. Je
n'affirme pas avoir obtenu un résultat dans n'importe quel Z/pZ avec p premier.

Ci dessous la preuve dont je laisse les détails assez faciles à vérifier en exercice.
Remarque Les égalités sont ds Z/2017Z

1) et je pose

On a et avec

2) On montre que

3) On montre qui implique que donc

4) avec on montre que 2016 est le plus petit entier p tel que 10^p=1.
********************
Pour les calculs par exemple pour montrer 2)
5^5=3125=1108
1108^2=1 227 664=1328
1108^3=1328*1108=1471424=1031
1031^2=1062961=2
Donc . C'est pas vraiment fastidieux.
Pour finir . D'où

Pour le 3) de mémoire c'est pas plus que pour 2)
et pour 4) c'est quasi direct avec très peu de calcul.

[GaBuZoMeu]

@aviateur : ce n'est pas grave de se tromper, ça m'arrive souvent. C'est plus grave de s'obstiner et de ne pas comprendre son erreur.
Une nouvelle fois, ton erreur est de penser qu'il suffit de vérifier que pour en déduire que 2016 est le plus petit entier tel que . Peux-tu m'expliquer comment tu fais cette déduction ?
Tu t'obstines aussi à ne pas comprendre pourquoi je parle de 103. J'en parle parce que mais que pourtant 102 n'est pas le plus petit entier tel que . Vraiment, tu ne vois pas le rapport avec ta prétendue déduction ?
Si tu utilises un autre argument caché qui ne s'appliquerait pas dans le cas 103, quel est-il ?

[aymanemaysae]

Bonjour ;



Si on prend a = 10 et n = 2017 , l'affirmation d'Aviateur est juste .

[GaBuZoMeu]

@aymanemaysae, peux-tu argumenter ?

Bien sûr . Par ailleurs , on est bien d'accord là-dessus. Comment pourrait-on en déduire que l'ordre multiplicatif de 10 modulo 2017 est 2016 ????

[aviateur]

Rebonjour
@aneymase, là je n'ai pas trop le temps de regarder ton texte mais j'ai seulement utilisé, le petit th de Fermat et le reste que des arguments élémentaires.
@Gabozumeu Il n'y pas pas d'arguments (compliqués) qui serait cachés pour la question 4) excepté un petit calcul qu'il faut que je refasse . Là je dois m'absenter, je reviendrai dessus plus tard.

[aymanemaysae]

J'utilise seulement le théorème de Carmichael .

[GaBuZoMeu]

@aymanemaysae : et comment utilises-tu le théorème de Carmichael ? Désolé, mais je ne vois toujours aucun argument de ta part.

@aviateur. Je peux te rappeler le seul argument que tu aies écrit à l'appui de ton affirmation, au début de ce fil :

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'ai mis en rouge ce que je conteste.

[aymanemaysae]

est un nombre premier donc .

Supposons qu'il existe tel que , alors on a est un multiple de , donc est le plus petit entier qui vérifie .

[GaBuZoMeu]

aymanemaysae, tu lis mal le théorème de Carmichael et tu lui fais dire n'importe quoi !
Attention au quantificateur : Carmichael dit que si POUR TOUT entier a premier à n, a^m = 1 modulo n, alors lambda(n) divise m. Il ne dit certainement pas que si, pour un certain a fixé premier à n (par exemple a=10), a^m = 1 modulo n, alors lambda(n) divise m.

Ça va, tu es bien d'accord que ton "argument" ne vaut pas ?

[aviateur]

@aviateur. Je peux te rappeler le seul argument que tu aies écrit à l'appui de ton affirmation, au début de ce fil :

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'ai mis en rouge ce que je conteste.

Mais tu insistes! Je t'ai dit que j'ai fait une erreur, il manque des choses, je suis allé vite c'est clair . Alors je comprends que cela peut sembler faux et surtout si j'ai écrit "bleu" au lieu de dire "blanc".
Mais si j'ai dit que les calculs, on peut les faire à la main c'est qu'on peut les faire à la main. J'ai mis les calculs ci-dessus. Alors pourquoi as-tu mis en doute cela?


Ensuite la démonstration je l'ai donnée ci-dessus, il reste à faire les détails en exercice. Alors?

Pour le 4) qui te pose problème, c'est pourtant pas très compliqué.

Par exemple on a k=2^(4 *9 *7) (= )
On a et il faut s'assurer que par exemple on n'a pas 10^k_1=1 avec par exemple (il y a 2 cas en tout). L'autre cas doit être similaire.

Un petit raisonnement par l'absurde dit que si on a alors on a

On factorise, ce qui donne Ou encore
mais ....

@aymanemaysae Pour t'expliquer le problème ici, même si le théorème que tu cites tourne un peu autour de cela, le problème est différent. On sait que mod . C'est le petit théorème de Fermat. Ceci répond à la question de Dacu.
Une question naturelle que l'on peut se poser en plus, c'est de savoir si 2016 est le plus petit entier qui répond à la question. J'ai prétendu que oui, mais à ma connaissance il n'y a pas de théorème qui répond à la question. La question n'est pas de savoir si 2016 est bien le plus petit entier est vrai.
En effet, il suffit d'écrire une petit algorithme pour le vérifier et cela a été fait par @chan, je crois.
La question c'est, est-ce qu'on peut le démontrer avec un peu de raisonnement et un minimum de calcul? 2017 est un peu grand mais si on s'y prend bien la réponse est oui. C'est ce que je pense avoir fait.

[GaBuZoMeu]

Ah, enfin tu finis par voir ce qui manquait à ton argument. Ça fait juste deux jours que je l'écrivais :

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)

Maintenant tu viens finalement de donner un joli argument pour 10^672. Bravo, mieux vaut tard que jamais. Sauf que le calcul est complètement erroné : tu écris que 10^{2^5*3*7}=10^{2^4*3*7} * 10^2. Pas mal ! Tu t'es un peu trop précipité pour fabriquer un argument bancal.
Plus sérieusement, l'argument consisterait à écrire que 10^1018 + 10 ^672 = 10^672 * (10^336+1) et que 10^336+1 n'est pas divisible par 2017. Bon, finalement c'est assez bidon, il faut tout de même calculer 10^336 modulo 2017.

Normalement, cet argument ne marche pas pour 103. On sait que 10^51 = -1 modulo 103. Est-ce que 10^34 peut être égal à 1 modulo 103 ? On a 10^51 + 10^34 = 10^34 * (10^17 + 1), et justement 10^17 + 1 est divisible par 103 :
10^17 + 1 = 103 * 970873786407767.

[aviateur]

Non mais ça va pas?
Ici me reprocher avoir mis un exposant 2 à la place de 1 alors que ça change rien!

De plus, tu me fais perdre mon temps alors que j'aurai voulu répondre à @chan qui était interrogatif avec plus d'humilité.

Je voudrais ajouter qu'ici on n'est pas au boulot. Alors si j'ai autre chose à faire, c'est que j'ai autre chose à faire que de répondre dans l'immédiat.

[GaBuZoMeu]

Je te reproche d'avoir écrit que

Si tu n'es même pas capable de reconnaître cette erreur, je ne sais pas où on va .

[aviateur]

Mais tu corriges à la fin! ça s'arrange ce genre d'erreur. si ça fait 336 qui est un diviseur de 1008 c'est gagné
pourvu que le coeff soit pair. il doit être pair par ailleurs.
Alors pour que tu ne viennes me gonfler maintenant, finis la division toi même.
Arrête de dire qu'une démo est bidon en relevant des fautes qui n'ont pas d'importance dans le raisonnement
général.

[GaBuZoMeu]

Ça en devient assez comique.
Bon, passons, pas grave.

[aviateur]

Mais t'es con ou quoi?

Si i.e
mais aussi d'où la contradiction.

Où est-ce que c'est bidon?

Ce qui est bidon, c'est que tu dises qu'il faut calculer

ça va il n'a plus de fautes? les virgules ça va? les fautes latex sont corrigées.??