Déterminer le reste de 2^(10^n) divisé par (1+10^n)

[anthony_unac]

Bonjour,

Je dois déterminer le reste de 2^(10^n) modulo (1+10^n) et je galère alors j'ai commencé à me faire la main sur le cas n=2 :

Détermination du reste de 2^100 divisé par 101
***************************************************
J'ai commencé par établir la liste des puissance de deux : 2;4;8;16;32;64;128;256;512;1024 ...
Puis j'ai cherché un "quasi multiple" de 101 j'ai trouvé 512 = 2^9 qui est congru à 7 modulo 101
Ensuite je pose la division euclidienne : 100 / 9 et j'obtiens 100=9*11+1
Enfin je détermine le reste de 2^100 modulo101 en réécrivant :
2^100=2^(9*11+1)=(2^9)^11*2^1
2^100 = 7^11* 2 mod 101 = 1 mod 101

Détermination du reste dans le cas général de 2^(10^n) divisé par (1+10^n)
**********************************************************************************
Je tente d'appliquer la même technique mais il n'est pas toujours aisé de trouver un "quasi multiple" de (1+10^n) dans la liste des puissances de deux.
Dans l'idée il me faut trouver la puissance de deux telle que : (1+10^n)*Q approche 2^k
Etant donné que je ne travaille pas avec une égalité stricte je sors le "+1" et cherche à obtenir :
10^n * Q approche 2^k
(5^n)*(2^n)*Q approche 2^k autrement dit, Q doit être de la forme : Q=2^m/5^n avec m+n=k
Pour n fixé, j'incrémente m jusqu'à obtenir une valeur de Q proche d'un entier.

Existe t il une façon plus élégante de procéder pour le cas général ?

[anthony_unac]

Bonjour,
Personne n a d'idée pour le cas général, ou peut être n'ai je pas été suffisamment clair et précis dans la présentation du problème ?

[nodgim]

Tu as posé cette question dans la rubrique Lycée, c'est une question de cours ?

[anthony_unac]

Pas vraiment, c'est une question issue d'un travail personnel. Peut être que la rubrique Lycée n'est pas appropriée.

[GaBuZoMeu]

Vu que 101 est premier, l'ordre du groupe multiplicatif de est 100, donc par le théorème de Lagrange .
Il est sûr que ce n'est pas un argument de niveau lycée. Mais ça a l'avantage d'être expéditif.

[anthony_unac]

Effectivement, cela est vite expédié pour le cas n=2 : 2^(10^2)=1(mod 10^2+1). Une simple application du petit théorème de Fermat suffit à conclure en remarquant que 101 est premier donc a^100 = 1 (mod 101) pour tout a premier avec 101 (et donc avec a=2 notamment)
Mais le cas général "2^(10^n) mod (10^n+1)" est bien plus redoutable !

[GaBuZoMeu]

Dans le cas général, on peut déterminer le groupe multiplicatif de . Par exemple, pour , puisque , c'est le produit de groupes cycliques d'ordres 6, 10 et 12. L'ordre multiplicatif de 2 modulo 1001 est donc un diviseur de 60 (on voit d'ailleurs facilement que c'est 60). Donc est congru à modulo 1001. Tout le monde connaît , donc il suffit de calculer modulo 1001. Deux élévations au carré, et on s'en est sorti entièrement "à la main".

[anthony_unac]

Si je comprends bien, votre raisonnement repose entièrement sur la factorisation de (10^n+1).
Hélas, il ne semble pas plus aisé de factoriser (10^n+1) dans le cas général (j'entends) que de chercher 2^(10^n+1) modulo (10^n+1).

[GaBuZoMeu]

On peut toujours employer la force brute.
Avec l'exponentiation rapide, au plus 6n multiplications à faire à faire modulo 10^n+1.

Et un logiciel de calcul formel s'en sort très bien.

Code: Tout sélectionner

n=2020
a=mod(2,10^n+1)
a^(10^n)

Code: Tout sélectionner

3490068127328296870446975896601543394962465169510956276009508627918492692909437169134365179181976755109838379632151686457333874063317628702052813415771850315521491440983895030781339518996166929239875899485304985736515540986618272522801057283102789103760292897223757394834611690090300514921944271646632736380656756203679674953892595969844259907923937634809136259571383055212169160539355048724977130884926960309084112913047415879977700439853450793835951319125272788635073471840348835969690881334714567389609278841171464187202987913694808461220151251746876516329573312064491194814388462199811572787213659563837015589329576212126979494009778778793447259598240480545355948574752497467097720875497043152408901879776351600809210618249909474051454370406623449858850219491150401667703819495963667099340505401204349891401493992207992906857774100897540075540318340492099402936159121556573020112719293508564423631319274089462344032596969243342810644267217127734779468377326751038297990420570597918138572296396463575348709690465102762389634218937267559993225231619222131272351588147423999597268709738975518379691635104256530415473246353633471489062857457262231190527938142134954676122751612403117456733029432000492190938982628844876425800024678595622911339924248776128476201436661034841478146477148784167731068730234226795512059448665496290190702494434256520385049890433170511975947408226725161772957833241033884558289083604811086224915086613678916148066588347094542449820357958469505865405660122257790607789231759397284980717390350180001296631809313552324765680315066741086556502459957457695181160880261022411973917658324668183147199508999917883945834841834571226882323707965384152021076911618261422516481274395075838965632346341627466131557883876269240464407072777246192740110215380805357279435803109214202308036351198739414693524397667153121317130689272444987011246058385798618531491812900536908154174441447278117071883347437562129267184693094706564716730776277919032974411178554123891459270614034978621349165842817637881118525381


[anthony_unac]

Ok donc le problème est inextricable sans avoir recours à "la force brute". Naïvement, je pensais qu'il existait un cheminement bien précis qui m'aurait conduit à une relation en fonction de n aisément calculable.

[GaBuZoMeu]

Comme on l'a vu, ça se traite bien "à la main" pour des n pas trop gros.

[anthony_unac]

Juste pour info, tu as codé ça avec quoi parce que tu manipules des entiers qui m'ont fait exploser les capacités de maple ou de pari/gp. Ou alors tu manipules tout ça en passant par la moulinette de l'exponentiation rapide (qui n’apparait pas dans ton code à moins que mod() soit une fonction bien précise que tu as codé à part et qui exploite l'exponentiation rapide ?!

[GaBuZoMeu]

Il ne faut bien évidemment pas prendre l'exponentielle avant de réduire modulo ce qu'on veut !! C'est le b-a-ba du calcul modulaire.
J'ai fait le calcul avec SageMath (qui utilise peut-être Pari-gp en arrière-plan, d'ailleurs). Il est sûr qu'aussi bien Maple que Pari-gp font ça, relis attentivement leurs documentations sur l'arithmétique modulaire.

[anthony_unac]

Je vais tenter d'installer SageMath qui visiblement à la bonne idée de récupérer le meilleur de Python et de Pari/GP.

[GaBuZoMeu]

Bonne façon de faire avec Maple :

Code: Tout sélectionner

> n:=2020:
> Power(2,10^n) mod(10^n+1);


Code: Tout sélectionner

3490068127328296870446975896601543394962465169510956276009508627918492692909437169134365179181976755109838379632151686457333874063317628702052813415771850315521491440983895030781339518996166929239875899485304985736515540986618272522801057283102789103760292897223757394834611690090300514921944271646632736380656756203679674953892595969844259907923937634809136259571383055212169160539355048724977130884926960309084112913047415879977700439853450793835951319125272788635073471840348835969690881334714567389609278841171464187202987913694808461220151251746876516329573312064491194814388462199811572787213659563837015589329576212126979494009778778793447259598240480545355948574752497467097720875497043152408901879776351600809210618249909474051454370406623449858850219491150401667703819495963667099340505401204349891401493992207992906857774100897540075540318340492099402936159121556573020112719293508564423631319274089462344032596969243342810644267217127734779468377326751038297990420570597918138572296396463575348709690465102762389634218937267559993225231619222131272351588147423999597268709738975518379691635104256530415473246353633471489062857457262231190527938142134954676122751612403117456733029432000492190938982628844876425800024678595622911339924248776128476201436661034841478146477148784167731068730234226795512059448665496290190702494434256520385049890433170511975947408226725161772957833241033884558289083604811086224915086613678916148066588347094542449820357958469505865405660122257790607789231759397284980717390350180001296631809313552324765680315066741086556502459957457695181160880261022411973917658324668183147199508999917883945834841834571226882323707965384152021076911618261422516481274395075838965632346341627466131557883876269240464407072777246192740110215380805357279435803109214202308036351198739414693524397667153121317130689272444987011246058385798618531491812900536908154174441447278117071883347437562129267184693094706564716730776277919032974411178554123891459270614034978621349165842817637881118525381

Bonne façon de faire avec GP Pari

Code: Tout sélectionner

? n=2020 ; lift(Mod(2,10^n+1)^(10^n))


Code: Tout sélectionner

%5 = 3490068127328296870446975896601543394962465169510956276009508627918492692909437169134365179181976755109838379632151686457333874063317628702052813415771850315521491440983895030781339518996166929239875899485304985736515540986618272522801057283102789103760292897223757394834611690090300514921944271646632736380656756203679674953892595969844259907923937634809136259571383055212169160539355048724977130884926960309084112913047415879977700439853450793835951319125272788635073471840348835969690881334714567389609278841171464187202987913694808461220151251746876516329573312064491194814388462199811572787213659563837015589329576212126979494009778778793447259598240480545355948574752497467097720875497043152408901879776351600809210618249909474051454370406623449858850219491150401667703819495963667099340505401204349891401493992207992906857774100897540075540318340492099402936159121556573020112719293508564423631319274089462344032596969243342810644267217127734779468377326751038297990420570597918138572296396463575348709690465102762389634218937267559993225231619222131272351588147423999597268709738975518379691635104256530415473246353633471489062857457262231190527938142134954676122751612403117456733029432000492190938982628844876425800024678595622911339924248776128476201436661034841478146477148784167731068730234226795512059448665496290190702494434256520385049890433170511975947408226725161772957833241033884558289083604811086224915086613678916148066588347094542449820357958469505865405660122257790607789231759397284980717390350180001296631809313552324765680315066741086556502459957457695181160880261022411973917658324668183147199508999917883945834841834571226882323707965384152021076911618261422516481274395075838965632346341627466131557883876269240464407072777246192740110215380805357279435803109214202308036351198739414693524397667153121317130689272444987011246058385798618531491812900536908154174441447278117071883347437562129267184693094706564716730776277919032974411178554123891459270614034978621349165842817637881118525381


[anthony_unac]

Eh bien, tu à l'air à l'aise avec tous les logiciels de maths.
Pour ma part, je n'ai même pas installé SageMaths car je me suis aperçu qu'il y avait une version en ligne qui fonctionne bien (quoi que peut être bridé) avec ce code :

Code: Tout sélectionner

n=2
R=Integers(10^n+1)
a=R(2)
a^(10^n)