Classes residuelles

par **dikambo** » 01 Nov 2006, 13:30

bonjour,
voilà mon probleme:
pour tout n élement de N , je dois calculer toutes les classes residuelles a element de Zn, lequelles sont invertible par la muötiplication et trouver l'element inverse a^-1 mod n.
merci pour votre aide

par **yos** » 01 Nov 2006, 13:56

comme on le voit facilement avec le théorème de Bezout (qui permet aussi de trouver

).

par **dikambo** » 01 Nov 2006, 14:22

merci mais je recherche plutot l'agorithme qui fait ca.

par **Zebulon** » 01 Nov 2006, 14:39

dikambo a écrit:merci mais je recherche plutot l'agorithme qui fait ca.

Bonjour,
c'est exactement l'identité de Bezout, qui vient de la division euclidienne.

par **yos** » 01 Nov 2006, 14:40

Chercher

, revient à trouver des entiers u et v tels que au+bn=1. L'inverse de la classe de a est alors la classe de u.
L'obtention de u et de v peut se faire avec l'algorithme d'Euclide.

par **dikambo** » 01 Nov 2006, 14:45

c'est ca mon probleme.
quel est cet algo qui fait ca.
meci

par **abcd22** » 01 Nov 2006, 15:08

Tu peux chercher sur wikipedia ou lire ce message par exemple.

Classes residuelles

classes residuelles

Qui est en ligne