on calcule les congruences de 3x [8]

pour x = 0
pour x = 1
pour x = 2
etc...

jusqu'à trouver une répétition
du reste de 3x dans la division euclidienne par 8

salut



...

j'avais vu avant le procédé que me propose "Pgeod" mais je l'avais trouver trop simple et assez basique ce qui m'a fais douté (d'où ma question), mais maintenant j'en suis convaincu alors merci pour le coup de main.
quant a Carpediem je comprend l'étape ou 9x21[8] mais comme on ne peux pas rediviser par 9 on passe par l'étape 9x5[8] mais je ne comprend pas la conclusion finale c'est comme si 21/9=5 :?

il n'est pas question de diviser par 9 (bien qu'on puisse) il est juste besoin de savoir que 9 = 8 + 1 !!!!

tout comme 21 = 2*8 + 5 ....

Bonjour,

la question est plutôt d'où peut bien sortir cette multiplication par 3 (le 3 sort d'un chapeau ou d'une boule de cristal ?)
ici c'est assez simple, car il sort de l'observation et de la connaissance des tables de multiplications :

le plus petit multiple de 3 (le 3 de 3x) qui dépasse de 1 un multiple de 8 est 9 d'où là multiplication par 3

de façon générale pour résoudre ax b [m] on cherche donc le plus petit multiple (ou "un multiple" suffirait) de a qui dépasse de 1 un multiple de m

c'est à dire au = mv + 1
ce qui ressemble tellement à une relation de Bézout au - bm = 1 que c'est comme ça qu'on le trouve !

ensuite c'est de la réduction modulo m
la relation de Bézout s'écrit "avec des congruences au 1 [m]
et donc aux x [m]
et la solution de l'équation s'obtient en multipliant tout par u :
de ax b [m]
on tire
aux bu [m]
et donc x bu [m]

plus généralement (car ce n'est pas tant une question de multiple dans une certaine mesure)


pour résoudre l'équation ax = b il suffit que a possède un inverse u puisqu'alors ::

    (cours de collège)


tout le problème est donc la recherche de l'inverse s'il existe

et dans Z/nZ  (ou modulo n) l'existence de l'inverse de a est équivalente à :: a et n sont premiers entre eux

ou encore :: il existe des entiers u et v tels que ua + vn = 1

égalité qui devient modulo n :: ua = 1

Dans les exercices que je voyais c'était toujours la partie droite qui changeait pour pouvoir arriver au résultat escompter ,a force j'en ai oublier que le modulo était applicable sur les deux cotés, merci c'est une méthode qui simplifiera les chose dans les cas ou on peux l'utiliser et je prend note de toutes vos suggestion
                                   MERCI