Help Please Congruences

[yann chriqui]

Bonsoir a tous.
Je sollicite votre aide genereuse car je n'arrive pas a comprendre la reponse a un petit exercice.
consigne :
1) trouver suivant les valeurs de lentier naturel n les restes de la division de 3^n par 11.
Je trouve : n = 5k r=1 n=5k+1 r= 3, n =5k+2 r=9, n=5k+3 r=5 n=5k+4 r=4

2) en deduire suivant les valeurs de m, les restes de la division euclidienne par 11 des nombres :

A = 1978^m
B= 421^5m + 421^4m + 421^3m + 421^2m + 421^m
on distinguera cinq cas selon les valeurs du reste de la division euclidienne de m par 5

Je connais les reponses de la seconde question mais je ne comprends pas toutes les etapes qui permettent dy arriver ... Si quelquun pouvait mexpliquer comment il arrive a la reponse, je lui en serai tres reconnaissant ...

[yann chriqui]

Ca mest venu au milieu de la nuit d'hier, merci pour votre non aide

[Skipper64]

c'est quoi l'explication ? :B

[Hayleia]

1978==9[11]
Donc 1978^m==3^2m[11]
Pour m=5q+r, où 0≤r≤4, on a donc 1978^m==3^2r[11].
Plus qu'à calculer 3^2r modulo 11 pour 0≤r≤4, probablement en refaisant une division euclidienne sur 2r. On peut peut-être simplifier plus mais c'est déjà faisable je pense (je n'ai pas essayé d'aller plus loin).

De même, 421==3[11].
Donc 421ⁿ==3ⁿ[11]
Pour m=5q+r où 0≤r≤4, on a donc 421^5m+421^4m+421^3m+421^2m+421^m==3^5r+3^4r+3^3r+3^2r+3^r[11].
Encore une fois, plus qu'à calculer pour 0≤r≤4 (suite géométrique ?).

Si quelqu'un (Bisam ?) pouvait passer compléter/corriger, ça serait sympathique, j'aimerais bien vérifier que je n'ai pas déjà tout oublié des congruences.

[Skipper64]

oh ! c'est vraiment très performant cette méthode ! je n'ai pas encore vu ce type d'exercices en cours j'avais juste jeté un oeil dans le livre et je ne savais pas qu'on pouvait simplifier à ce point (par 3^2r par exemple) moi j'aurais juste fait 3^2m=(3^m)x(3^m). En tout cas si ça marche chapeau ! Merci beaucoup

[Bisam]

Ce qu'Hayleia a écrit me paraît juste.
Pour le 1er cas, il suffit de calculer (3^r)^2 [11] dans les 5 cas possibles.

Pour le 2ème cas, la suite géométrique n'apporte pas grand chose. Il n'y a qu'à traiter les 5 cas à nouveau.