Semaine 1 CONGRUENCES DANS Z, ANNEAUX Z=nZ 1 Congruences dans Z 1.1 Rappels de Sup De…nition 1 On dit que m est un multiple de n ou que n divise m ssi m 2 nZ . Proposition 2 Soit n 2 Z et b 2 N � ;alors il existe un et un seul couple (q; r) 2 Z � N tel que n = qb + r et 0 � r < b: De…nition 3 Dans la dé…nition précédente q est dit quotient et r reste de la division euclidienne de n par b: Proposition 4 Soit b un entier � 2: Pour tout entier n � 1; il existe un et un seul entier N tel que bN � n < bN+1 et une unique suite (�0; ; �N) tels que n = �NbN + :::: + �0 et ���� 8k = 0; 1; :::; N; 0 � �k < b �N 6= 0 : De…nition 5 Dans la dé…nition précédente, on dit que �N:::�0 est l’écrure en base b ou écriture b� adique de n: Si b = 2 ou 3 on parle d’écriture dyadique ou tryadique. 1.2 Congruences modulo n De…nition 6 Soit n 2 N et x; y 2 Z . On dit que x et y sont congrus modulo n; ssi, x � y est un multiple de n et on note x � y [n] : 1.2.1 Propriétés Proposition 7 Propriétés de la congruence � La congruence modulo n est une relation d’équivalence sur Z . Cela signi…e qu’elle véri…e les propriétés suivantes Re‡exivité: 8x 2 Z x � x [n] Symétrie: 8x; y 2 Z x � y [n] ) y � x [n] Transitivité: 8x; y; z 2 Z x � y [n] et y � z [n] ) x � z [n] 1