diviseur

[invite371ae0af]

bonjour,

pouvez vous m'expliquer comment trouve-t-on le reste de la division euclidienne de par 1155

je connais le lemme chinois et le théorème de fermat mais comment les utiliser?


merci de votre aide
-----

[sylvainc2]

On connait les facteurs premiers de 1155=3*5*7*11 On crée le système suivant:
2^6754 = 1 mod 3
2^6754 = 4 mod 5
2^6754 = 2 mod 7
2^6754 = 5 mod 11
(chaque congruence est résolue grâce au petit théorème de Fermat.)

Ensuite on cherche un y tel que:
y = 1 mod 3
y = 4 mod 5
y = 2 mod 7
y = 5 mod 11
qu'on peut résoudre avec l'algorithme de Gauss pour résoudre le théorème des restes chinois:
par exemple pour la 1ère congruence on cherche un multiple de 5*7*11 = 385 qui est aussi égal à 1 mod 3. On trouve y1=385.
Pour la 2e on cherche un multiple de 3*7*11 = 231 qui est aussi égal à 4 mod 5. On voit facilement que c'est y2=4*231 = 924.
Pour les 3e et 4e congruences on trouve de la même façon y3=4*165=660, et y4=10*105=1050.
Alors la solution est y = 385+924+660+1050=3019=709 mod 1155.

Un autre méthode est d'utiliser la fonction phi (totient) d'Euler. Si a et n sont premiers entre eux alors a^phi(n)=1 mod n.
Ici, a=2 et n=1155 sont premiers entre eux, et 1155=3*5*7*11, donc phi(1155)=(3-1)(5-1)(7-1)(11-1)=480.
Donc 2^480 = 1 mod 1155.
2^6754=2^(480*14+34)=((2^480)^ 14)(2^34)=(1^14)(2^34) mod 1155
Il reste à calculer 2^34 mod 1155, et ca se fait facilement puisque que 2^10=1024.

[invite371ae0af]

comment as tu trouvé le système:
2^6754 = 1 mod 3
2^6754 = 4 mod 5
2^6754 = 2 mod 7
2^6754 = 5 mod 11

[invite57a1e779]

comment as tu trouvé le système:
2^6754 = 1 mod 3
2^6754 = 4 mod 5
2^6754 = 2 mod 7
2^6754 = 5 mod 11

On calcule les premières puissances de 2, et on obtient :

[A voir en vidéo sur Futura]

[invite371ae0af]

mais que vient faire fermat là dedans

pour 2^6754 = 1 mod 3, je suis d'accord ca marche avec fermat:
2^(2)=4=1 mod3

mais pour le reste ca ne marche pas: par exemple 2^6754=4 mod5
2^(4)=1 mod5
mais après?

[invite57a1e779]

2^(4)=1 mod5
mais après?

, donc :

[invite371ae0af]

tu trouves 6754=(4x1688)+2, au hasard ou bien quelque chose (une relation quelconque) à permis d'aboutir à cela?

d'autre pas, comment résoudre le système
y = 1 mod 3
y = 4 mod 5
y = 2 mod 7
y = 5 mod 11

de la première équation je déduit y=1+3k
j'injecte dans la deuxième équation, ca me donne k=1 mod5
donc y=4+15k'

je remplace y par 4+15k' dans la troisième équation mais ca me donne: 15k'=-2 mod 7
comment faire? je cherche un k" qui conviennent (divisible par 15)?

[invite57a1e779]

tu trouves 6754=(4x1688)+2, au hasard ou bien quelque chose (une relation quelconque) à permis d'aboutir à cela?

Ce n'est pas le hasard, mais la division euclidienne de 6754 par : le quotient est 1688 et le reste est 2.

[breukin]

au hasard ou bien quelque chose (une relation quelconque) à permis d'aboutir à cela ?

Ni l'un ni l'autre.

Soit , en
Si on sait trouver tel que , alors on fait la division euclidienne de par , soit , et alors

Ce n'est donc pas une relation qui a permis d'aboutir à celà, mais une idée (celle de faire la division euclidienne).

[invite371ae0af]

d'accord merci à vous 2

mais sinon pour le système:

y = 1 mod 3
y = 4 mod 5
y = 2 mod 7
y = 5 mod 11

de la première équation je déduit y=1+3k
j'injecte dans la deuxième équation, ca me donne k=1 mod5
donc y=4+15k'

je remplace y par 4+15k' dans la troisième équation mais ca me donne: 15k'=-2 mod 7
comment faire? je cherche un k" qui conviennent (divisible par 15)?

[invite57a1e779]

je remplace y par 4+15k' dans la troisième équation mais ca me donne: 15k'=-2 mod 7
comment faire? je cherche un k" qui conviennent (divisible par 15)?

Tu travailles successivement dans Z/3Z, Z/5Z, Z/7Z, Z/11Z qui sont des corps puisque 3, 5, 7 et 11 sont des nombres premiers.

Toute équation a pour solution où les classes de et sont inverses dans Z/Z, c'est-à-dire , et on calcule par une égalité de Bézout qui s'obtient via l'algorithme d'Euclide, donc avec des divisions euclidiennes.
Avec des petits nombres, on peut trouver « au flair » l'inverse de .

La première équation fournit effectivement , d'où : .

Comme , tu as déduit correctement : , donc : , puis : .

Mais , donc tu as immédiatement , donc : et et il te reste à recommencer le même type de calcul une dernière fois modulo 11.

[invite371ae0af]

d'accord je te remercie pour ton aide