Preuve d'une propriété avec modulo

[aymericdc]

Bonjour,

Voici un problème que nous n'arrivons pas a prouver. Si vous savez m'aider ça serait super!

Supposons que A ne divise pas B (donc NON A|B)

Supposons X dans [0..B-1] et Y dans [0..B-1] avec B tout nombre supérieur a 0

Prouver que (A*X)mod(B) = (A*Y)mod(B) si et seulement si X = Y

Voici un exemple pour illustrer ce que l'on veut prouver:

A = 5 and B = 12 alors

(Ax0) mod B = (5x0) mod 12 = 0

(5x1) mod 12 = 5

(5x2) mod 12 = 10

(5x3) mod 12 = 3

(5x4) mod 12 = 8

(5x5) mod 12 = 1

(5x6) mod 12 = 6

(5x7) mod 12 = 11

(5x8) mod 12 = 4

(5x9) mod 12 = 9

(5x10) mod 12 = 2

(5x11) mod 12 = 7

Comme vous pouvez le voir, de 0 a 11 (donc de 0 a B-1) tous les résultats sont uniques. Ca paraît logique, mais c'est pourquoi nous avons du mal a le prouver!

Merci d'avance!

[Doraki]

Tu as essayé avec A=8 ?

[nodjim]

Il faut A et B premiers entre eux, et pas seulement l'un ne divise pas l'autre.

[paquito]

C'est faux!!

Prenons A=6 et B=8; on a:

6x0=0 [8]
6x1=6 [8]
6x2=4 [8]
6x3=2 [8]
6x4=0 [8]
6x5=6 [8]
6x6=4 [8]
6x7=2 [8]; on a 6x0=0 [8] et 6x4=0[8], puis 6x1=6 [8] et 6x5=6 [8], etc...

Par contre, si d = pgcd (A, B), AX=AY [B] A(X-Y)=0 [B] dA'(X-Y)=kdB' A'(X-Y)=kB' A'(X-Y)=0 [B'] (X-Y)=0 [B'] X=Y car

[aymericdc]

Merci beaucoup ! Il me reste une question...

A'(X-Y)=0 [B'] (X-Y)=0 [B'] X=Y

Par quelle propriété tu sais que tu peux supprimer le A' ?

[Ben314]

Lemme de Gauss
Par contre, l'équivalence suivante est fausse : on n'en déduit pas (mais alors pas du tout...) que X=Y

[aymericdc]

Lemme de Gauss
Par contre, l'équivalence suivante est fausse : on n'en déduit pas (mais alors pas du tout...) que X=Y

C'est bien vrai! Si on prend A = 6 B = 12, on peut suivre tout son raisonnement avec X = 3 et Y = 1 sauf que X n'est pas égal a Y:

AX = AY (mod12) 6(3-1) = 0 (mod12) (3-1) = 0 (mod12/6) 2 = 0 (mod2) ce qui est vrai.

As-tu une idée du coup pour prouver ce que l'on cherche avec A et B premier entre eux?

[Ben314]

Si A et B sont premier entre eux, alors, dans la preuve de paquito, on a d=1, A'=A et B'=B et là effectivement on peut conclure comme il le fait à la fin : X et Y sont entre 0 et B-1 (compris) et congru modulo B (le même B) donc égaux (car X-Y est entre -(B-1) et (B-1) et doit être multiple de B or le seul multiple de B dans cet intervalle est 0)

Alors que, si A=6 et B=12 alors B'=2 et, à la fin, tout ce qu'on peut dire, c'est que X-Y est entre -11 et 11 (compris) et que c'est un multiple de 2 : c'est clairement insuffisant pour en déduire que X-Y=0 : ça pourrait être 2 ou -2 ou 4 ou -4 ou ...
Par exemple, si X=3 et Y=1 alors X-Y=2, mais ça marcherais "tout pareil" avec X=4 et Y=10 où X-Y=-6.

[aymericdc]

Si A et B sont premier entre eux, alors, dans la preuve de paquito, on a d=1, A'=A et B'=B et là effectivement on peut conclure comme il le fait à la fin : X et Y sont entre 0 et B-1 (compris) et congru modulo B (le même B) donc égaux (car X-Y est entre -(B-1) et (B-1) et doit être multiple de B or le seul multiple de B dans cet intervalle est 0)

Super je comprend bien la preuve, Paquito était parti sur la bonne voie mais il manquait des spécifications de départ.
Par contre j'ia toujours un soucis, pourquoi est-ce-que on peut passer de A(X-Y) = 0 [B] a (X-Y) = 0 [B] ?

[Ben314]

Bis et répétita : c'est le Lemme de Gauss
Il y a plusieurs méthode pour le démontrer plus ou moins de "haut niveau".
La plus basique passe par l'égalité de Bézout que l'on démontre elle même à l'aide de l'algorithme d'Euclide de calcul du pgcd.

[paquito]

Merci beaucoup ! Il me reste une question...



Par quelle propriété tu sais que tu peux supprimer le A' ?

Parce que A' est premier avec B', donc comme B' divise A'(X-Y) et est premier avec A',il divise (X-Y).