Modulo 97 [Résolu/Fermé]

Le modulo de tout chiffre arrondi à une puissance de 10 (que ce soit 1000, 100000 ou, comme ici, 10.000.000) est relativement facile à calculer. Donc tout chiffre additionné à cet arrondi devra intégrer ce modulo, et tout multiple de ce chiffre aura un modulo multiplié de la même manière.

Par exemple:
1000 % 97 = 30
(1000 / 97 = 10,309278 puis 0,309278 * 97 = 30)
Donc 10.000 % 97 doit donc être 10x 30 (que l'on doit encore faire % 97 etc.).
Et ainsi 10.001 % 97 doit être (10x 30 +1) % 97.
Donc, en limitant la saisie à 4 ou 5 chiffres, tout chiffre "aaa.bbb" modulo 97 est égal à (aaa x 30 + bbb) modulo 97

Puisqu'une calculette standard n'a que 8 chiffres, on fait d'abord 10.000.000 / 97 = 103092,78 puis 0.78 x 97 = 76.
Donc tout chiffre "a.aaa.aab.bbb.bbb" modulo 97 va donner la même résultat que ("aaaaaaa" x 76 + "bbbbbbb") modulo 97.

Et pour plus de 13 chiffres, on peut continuer:
a.aaa.aab.bbb.bbc.ccc.ccc % 97 => ???
D'abord 10.000.000.000.000 % 97 = (1.000.000 x 76 + 0) % 97 = 15
Donc cela donne (aaaaaa x 15 + bbbbbbccccccc) % 97.
Le calcul aaaaaa x 15 + bbbbbbccccccc va forcément donner un résultat à 13 chiffres (ou 14 si bbbbbb = 999999, mais la suite reste gérable pour une calculette à 8 chiffres), et ensuite on refait avec 76 comme ci-dessus.
Donc oui, il faudrait découper le calcul en deux pour faire aaaaaa x 15 + bbbbbbccccccc (ou faire l'addition sur papier...) mais cela reste relativement simple à effectuer. Et on peut continuer ainsi à l'infini - à condition d'avoir le temps pour le faire - en ajoutant les mêmes étapes l'une après l'autre.

Ou, une autre manière de regarder la même question:

100 % 97 = 3
donc 1.000 % 97 = (3 * 10) % 97 = 30
donc 10.000 % 97 = (3 * 10^2) % 97 = 9
donc 100.000 % 97 = (3 * 10^3) % 97 = 90
donc 1.000.000 % 97 = (3 * 10^4) % 97 = 27
donc 10.000.000 % 97 = (3 * 10^5) % 97 = 76

d'où il est clair que:
si (x % y) = z
alors (10x % y) = (10z % y)
ou plus généralement: (nx % y) = (n(x % y) % y) = (nz % y)

Puisque ((x+p) % y) = (((x % y) + p) % y) (pour le modulo "y" de deux chiffres additionnés, on peut remplacer l'un ou l'autre ou les deux par leur modulo "y" sans changer le résultat)
donc ((nx + p) % y) = ((n(x % y) + p) % y)
et encore, si (x % y) = z,
((nx+p) % y) = (nz + p) % y

Donc pour tout très grand multiple n de x (dans ce cas, les 6 plus grands chiffres d'un nombre à 13 chiffres, qui sont donc un multiple "n" de "x" où x =10.000.000), si on connait le résultat "z" de x % y (dans ce cas, 76 si y = 97), l'equation pour un chiffre "a.aaa.aab.bbb.bbb" % 97 devient simplement (n * 76 + p) % 97
= ("aaaaaa" * 76 + bbbbbbb) % 97


Et enfin, pour un nombre à 31 chiffres "a.aaa.aab.bbb.bbc.ccc.ccd.ddd.dde.eee.eee" % y ...
= ("aaaaaa" * (10^25 % y) + bbbbbbccccccddddddeeeeeee) % y
= ("aaaaaa" * (10^25 % y) + ("bbbbbb" * (10^19 % y) + ccccccddddddeeeeeee) % y) % y
et ainsi de suite, qui finit par:
= ("aaaaaa" * (10^25 % y) + ("bbbbbb" * (10^19 % y) + ("cccccc" * (10^13 % y) + ("dddddd" * (10^7 % y) + "eeeeeee")))) % y

Pour modulo 97, on connait 10^7 % 97 = 76, donc "a.aaa.aab.bbb.bbc.ccc.ccd.ddd.dde.eee.eee" % 97
= ("aaaaaa" * (10^18 * 76 % 97) + ("bbbbbb" * (10^12 * 76 % 97) + ("cccccc" * (10^6 * 76 % 97) + ("dddddd" * 76 + "eeeeeee")))) % 97
Il est facile de calculer 10^6 * 76 % 97 = 15
= ("aaaaaa" * (10^12 * 15 % 97) + "bbbbbb" * (10^6 * 15 % 97) + "cccccc" * 15 + "dddddd" * 76 + "eeeeeee") % 97
Encore, 10^6 * 15 % 97 = 17
= ("aaaaaa" * (10^6 * 17 % 97) + "bbbbbb" * 17 + "cccccc" * 15 + "dddddd" * 76 + "eeeeeee") % 97
Et enfin, 10^6 * 17 % 97 = 71
= ("aaaaaa" * 71 + "bbbbbb" * 17 + "cccccc" * 15 + "dddddd" * 76 + "eeeeeee") % 97
Et puisque le résultat ("ffgggggg") % 97 risque fort de dépasser les limites d'une calculette de base, on refait (ff * 76 + ggggggg) % 97 pour faire tenir le tout sur 8 chiffres.