Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Propriétés de Z/nZ Louis Nebout Le but de ce cours est de présenter le point du

Propriétés de Z/nZ Louis Nebout Le but de ce cours est de présenter le point du vue moderne sur l’arithmétique, issu de l’algèbre. Rien de ceci n’est ofﬁciellement au programme des olympiades et une partie des résultats vous est certainement déjà connue sous une formulation différente, mais une bonne connaissance de cette théorie permet de mieux comprendre ce qui se passe, et de prouver quelques résultats très puissants. 1 L’anneau Z/nZ Soit n ⩾2 un entier naturel. Quelle est précisement la nature de la formule a ≡b [n] ? Ce n’est pas une vraie égalité : cela veut dire qu’il existe une certaine relation d’équivalence, la relation de congruence, pour laquelle a et b sont en relation. Maintenant, si a ≡b [n] et c ≡d [n], on sait bien que a + c ≡b + d [n], et de même avec la multiplication. Ainsi, cette relation possède en fait des propriétés tout à fait similaires à l’égalité, et on aimerait bien dire que « on peut additionner et multiplier les modulo », mais cette phrase n’a aucun sens mathématique. Pour lui donner du sens, on aimerait bien la « transformer » en une véritable égalité, en « faisant de deux entiers congrus modulo n un seul et même nombre ». Si x est un entier, on appelle classe d’équivalence de x modulo n l’ensemble des entiers congrus à x modulo n. On note x la classe de x. Attention, si x ≡y (mod n), alors x et y sont deux notations pour un seul et même objet. On obtient exactement n classes d’équivalence : 0, 1, . . . , n −1, et on note Z/nZ l’ensemble de ces classes d’équivalence. On munit Z/nZ de deux opérations + et × en posant x + y = x + y et x × y = x × y. Il y a une subtilité : il faut prouver que ces opérations sont bien déﬁnies, c’est-à-dire que les résultats de ces opérations ne dépendent pas des choix des représentants x et y de x et y, par exemple pour +, que si x = x′ at y = y′, alors x + y = x′ + y′ : c’est une simple reformulation du fait que la relation de congruence est compatible avec les opérations. La construction de Z/nZ peut paraître conceptuellement difﬁcile la première fois qu’on la voit, mais en fait, la manipulation de cet ensemble est très simple en pratique : écrire x+y = z est rigoureusement équivalent à écrire x+y ≡z mod n, par exemple. Pour passer d’une écri- ture à l’autre, on enlève les barres et on remplace l’égalité par une relation de congruence. Mais l’énorme avantage conceptuel de l’utilisation de Z/nZ est, dans le cas de Z/5Z par exemple, le fait que 2 et 7 sont un seul et même nombre, et non plus simplement congrus. De plus, Z/nZ possède une certaine structure algébrique, qui nous permet de réaliser toutes nos opérations en restant à l’intérieur de Z/nZ, et donc sans avoir à repasser par les entiers. L’ensemble Z/nZ est donc muni de deux opérations, une addition et une multiplication, toutes deux commutatives et associatives, et telles que 1 — La loi + admet un élément neutre, 0, tel que pour tout x ∈Z/nZ, x + 0 = x ; — Tout élément x de Z/nZ admet un opposé noté −x, tel que x + (−x) = 0 (celui-ci est unique). — × est distributive sur + ((x + y) × z = x × z + y × z), — La loi × admet un élément neutre, 1, tel que pour tout x ∈Z/nZ \ {0}, x × 1 = x. En algèbre, on appelle un tel ensemble un anneau (commutatif). Les anneaux sont fondamen- taux, car ils apparaissent dans bien des domaines, et les mathématiciens ont donc développé une théorie générale traitant de ce type d’objets. Je n’en dirai pas plus pour l’instant. 2 Inversibilité Proposition 1. On dit que a ∈Z/nZ est inversible s’il existe b ∈Z/nZ, appelé l’inverse de a et noté a−1, tel que a × b = 1. Les inversibles de Z/nZ sont exactement les k, où k est un entier premier avec n. Démonstration. C’est une reformulation du théorème de Bézout, en effet on a les équivalences suivantes. Il existe b ∈Z tel que ab ≡1 mod n ⇔il existe b ∈Z et k ∈Z tels que ab = kn + 1 ⇔a est premier avec n. Remarque 2. Si on sait que ab = ac dans Z/nZ, on peut donc conclure b = c dans le cas où a est premier avec n : il sufﬁt de multiplier des deux côtés par l’inverse de a. C’est faux en général. Par exemple, 2 × 1 = 2 × 3 = 2 dans Z/4Z mais il est faux que 1 = 3. Si p désigne un nombre premier, on a ainsi que tous les éléments de Z/pZ autres que 0 sont inversibles. On appelle corps un anneau vériﬁant cette propriété. Dans un corps, on dispose donc d’une opération fondamentale qui n’existe pas dans les anneaux : la division. Ainsi, les corps sont des objets algébriques beaucoup plus riches. Par exemple, la théorie des polynômes fonctionne très bien sur les corps, et nous allons donc étudier les polynômes à coefﬁcients dans Z/pZ. Noter que de tels polynômes seraient délicats à déﬁnir sans l’introduction de Z/pZ : 3 Polynômes sur Z/pZ Déﬁnition 3. Un polynôme sur Z/pZ est une expression de la forme : a0 + a1X + a2X2 + ... + adXd avec les ai dans Z/pZ. On note Z/pZ[X] l’ensemble de ces polynômes. Remarque 4. Sur R, on peut assimiler un polynôme et la fonction de R dans R qui lui corres- pond. Sur Z/pZ il faut être plus prudent. Par exemple, ap −a = 0 pour tout a donc la fonction correspondant au polynôme Xp −X est la fonction nul. En revanche, ce n’est pas le polynôme nulle : un polynôme est déﬁni par ses coefﬁcients. Lemme 5. Soient a et b dans Z/pZ \ {0}, alors a × b est dans Z/pZ \ {0}. 2 Remarque 6. On dit que Z/pZ est intègre. Démonstration. Si on avait a × b = 0, en multipliant par a−1 et b−1 on obtiendrait 1 = 0, c’est absurde. Ce lemme facile nous permet de déﬁnir une notion satisfaisante de degré sur Z/pZ [X], l’ensemble des polynômes à coefﬁcients dans Z/pZ. En effet, si P et Q ont pour termes domi- nants a · Xk et b · Xl, alors ab · Xk+l sera non nul, et sera le terme dominant de P · Q. Nous sommes maintenant en mesure de prouver : Proposition 7. Il y a une notion de division euclidienne sur Z/pZ [X] : soient A et B dans Z/pZ [X] avec B non nul, alors il existe un unique couple (Q, R) de polynômes de Z/pZ [X] tels que A = Q · B + R, avec deg(R) < deg(B). Démonstration. La preuve est la même que dans R [X]. Pour l’unicité, soit (Q′, R′) un deuxième tel couple, alors B · (Q −Q′) = R′ −R, puis Q = Q′ en examinant les degrés. Pour l’existence, on vériﬁe que l’algorithme usuel fonctionne, car le coefﬁcient dominant de B est inversible. Par exemple, pour diviser A = 5 · X3 + 2 · X2 + 5 · X par B = 3 · X2 + 6 · X + 2 dans Z/7Z, on commence par retrancher 5 · 3 −1 · X · B à A, le coefﬁcient dominant de Q doit donc être 5 · 3 −1 · X = 5 · 5 · X = 4 · X. Il reste A −4 · X · B = 6 · X2 + 4 · X. On retranche donc 6 · 3 −1 · B. Au ﬁnal, on obtient A = Q · B + R avec Q = 4 · X + 2 et R = 6 · X + 3. Corollaire 8. Soit P dans Z/pZ [X], et a une racine de P. Alors P est divisible par (X −a), i.e. il existe Q dans Z/pZ [X] tel que P = (X −a) · Q. Démonstration. Soit P = (X −a) · Q + R la division euclidienne de P par (X −a). Alors R est de degré inférieur strictement à 1, donc constant, et l’évaluation de l’expression précédente en a nous donne R = 0. Corollaire 9. Un polynôme de degré n dans Z/pZ [X] a au plus n racines. Démonstration. Soit P de degré n dans Z/pZ [X]. Supposons qu’il admette n racines a1, a2, ..., an. D’après le corollaire précédent, il existe une constante c non nulle tel que P = c · Πn i=1(X −ai). Soit alors a une racine de P. On a 0 = c · Πn i=1(a −ai), et, d’après le lemme, un des (a −ai) est nul, donc a est l’un uploads/Philosophie/ arith-zn-pdf.pdf