exercixe spe : Congruence et division euclidienne

[invite319b46d2]

Bonsoir,
cet exercice me pose certain problèmes:
1) Déterminer le reste dans la division euclidienne de 5^16 par 17.
2) Déterminer le reste dans la division euclidienne de 5^207 par 17.
3) le nombre 1101 x 5^207+5^12x7 est - il divisible par 17 ?

Pour la 1, J'ai cru comprendre que pour parvenir à une "congruence finale", je devais plus ou moins effectuer 5 par 17, ce qui me donnerait 5= 17x0+5

Comment, à partir de là, puis-je trouver le reste ?
-----

[VegeTal]

Bonsoir,

commence par étudiez le reste de la division des puissances de 5 par 17





....

jusqu'à ce que tu trouves une valeur intéressante.
Pense à appliquer équivalent à

question 3) juste une application :

équivalent à :



poste tes réponses.

[invite360be44f]

jai le meme exo et moi je trouve:
5^2 est congru a 8 mod 17
8^2 est congru à -4 mod 17
4^2 est congru à -1 mod 17
ainsi (5^2)^2 est congru à -4 mod 17
donc ((5^2)^2)^2 est congru à -1 mod 17
et 5^16 est congru à 1 mod 17

[VegeTal]

jai le meme exo et moi je trouve:
5^2 est congru a 8 mod 17
8^2 est congru à -4 mod 17
4^2 est congru à -1 mod 17
ainsi (5^2)^2 est congru à -4 mod 17
donc ((5^2)^2)^2 est congru à -1 mod 17
et 5^16 est congru à 1 mod 17

très flou : moi j'ai fais comme ça :





or n = 8

et p = 3

d'où

après pour tu fais juste "tourner" la boucle.

[A voir en vidéo sur Futura]

[invite360be44f]

je ne comprends pas trés bien votre methode
pouvez vous me l'expliquer?

[invite360be44f]

il vient d'ou le 2^8p

[VegeTal]

bien sur j'ai fais des essais pour trouver.

[invite360be44f]

pour le 2 pouvez vous me l'expliquer en profondeur?

[invite93845cf6]

Bonsoir, jevais essayer de répondre à ton problème en posant un tableau, pour la première question:
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
5^n 5 8 6 14 2 10 8 16 12 9 11 4 3 15 7 1
congru a ...
modulo 17

16=16*1+0
On se réfère au tableau et on en déduit:
5^16 est congru à 1 modulo 17. De ce fait le reste de la division de
5^16 par 17 est 1.

[VegeTal]

pour le 2 pouvez vous me l'expliquer en profondeur?

De quoi parles tu ?

[invite360be44f]

pour determiner le reste de 5^207 par 17

[invite360be44f]

je comprends mieux la methode de sebmc12 car on l'a apprise en classe

[invite360be44f]

cependant pour 5^207 le tableau n'est pas faisable je ne peux aller jusqu'à 207?

[VegeTal]

pour n = 103

or

et comme



par conséquent

[invite93845cf6]

cependant pour 5^207 le tableau n'est pas faisable je ne peux aller jusqu'à 207?

tu vasjusqu'à 17 puisque c'est 17 ton diviseur.
ensuite tu divises 207 par 16:
207=12*16+15
d'où, 5^207=5^(12*16+15)
Tu utilises ensuites les congruences:
5^207congru à (5^16)^12 * 5^15 (17)
ce qui équivaut à 5^207congru à 1^12 * 7 (17)
soit 5^207congru à 7(17)
le reste de la division euclidienne de 5^207 par 17 est 7.

[invite93845cf6]

euh non c'est jusqu'en 16 qu'il faut aller pas jusqu'en 17 même de toute façon le résultat est le même puisque 5^16congru à 1 (17).

[VegeTal]

attention j'ai fais une petite erreur et non pas 4 comme je l'ai marqué.

à rectifier dans la suite de mon raisonnement.

[invite360be44f]

seb comment passe tu de 5^207congru à 1^12 * 7 (17)
à 5^207congru à 7(17)