Reste division euclidienne

[invite69d45bb4]

bonjour à tous

trouver le reste de la division de 17^17 par 7

17=7x2+3
donc 17=3[7]
17^17=3^17=(3^2)^(7) x 3=3[7]


je n'arrive pas a avancer pourriez vous m'aider svp

merci d'avance

cordialement
-----

[invite473b98a4]

jusqu'à 17^17=3^17[7] je suis d'accord, si = veut dire congru. mais (3^2)^7= 3^14 et3^14x3=3^15...donc éventuellement (3^2)^(8)x3[7]=9^8x3[7] et je me demande si ça ne serait pas congru à 2^8x3[7] = 16^2x3[7]=2^2x3[7]=12[7]=5

[danyvio]

Commence par faire une jolie liste : (ci dessous = signifie congru à)

17^0=1[7]
17^1=3[7]
17^2=9[7]=2[7]


etc. Tu vas trouver une périodicité intéressante.

T'en dire plus = faire le devoir à ta place....

[invite69d45bb4]

je ne comprend pas le passage de (3^2)^(8)x3[7]=9^8x3[7] à congrus à 2^8 x 3|7]

[A voir en vidéo sur Futura]

[gg0]

Ben .... 9 est congru à 2 modulo 7.

[invite473b98a4]

la méthode de danyvio est plus propre.
17^0=1[7]
17^1=3[7]
17^2=17^1*17^1=3*3=9=2[7]
du coup
17^3=17^2*17^1=2*3=6[7]
17^4=17^2*17^2=2*2=4[7]
17^5=17^3*17^2=6*2=12=5[7]
17^6=5*3[7]=1[7]
et le cycle recommence
17^7=3[7]
17^8=2[7]
etc...
donc on peut décomposer 17^17 en 17^17= 17^(6*2+5)=17^0*17^5[7]=17^5[7]=5[7]

[Mikiisa]

En calculant pas a pas les reste des puissance de 17, essai de trouver k tel que 17^k = 1 (mod 7)

Exemple :
7^4 = 1 (mod 5)
Que vaut le reste de 7^2015 (mod 5) ?