Anneaux Z=nZ Universit e Claude Bernard{Lyon I

de h10idans Z=nZ (c) Quels sont tous les nombres dont le d evelopement d ecimal a pour p eriode 6 ? I A propos du plan 1 Sous-groupes et id eaux de Z=nZ Lemme Soit n2Z Tout sous-groupe de Z=nZ est un id eal Pour tout diviseur dde n, il existe un unique sous-groupe d’indice ddans Z=nZ, le quotient par ce sous-groupe est isomorphe a Z=dZ

Congruences - Université de Poitiers

Les ensembles nZ (n∈N) sont clairement des sous-groupes (resp idéaux) de Z Récipro-quement,soit Hunsous-groupede Z nonréduità {0},et nlepluspetitélémentnonnulde

Anneaux de polynômes II, anneaux quotients

1 Soit A un anneau principal, I un idéal de A Montrer que tous les idéaux de l’anneau quotient A=I sont principaux 2 Trouver tous les idéaux des anneaux suivants : Z=nZ, Q[x]=(f) où (f) est l’idéal principal engendré par un polynôme f 3 Trouver les idéaux maximaux de Z=nZ et de Q[x]=(f) Correction H [002288] Exercice 10

1 Anneaux Z/nZ Applications A,lecaractèreintègreassurel

1 AnneauxZ/nZ Applications 1 Rapport du jury — Dans cette leçon, l’entier n n’est pas forcément un nombre premier Il serait bon de connaître les idéaux de Z/nZ et, plus généralement, les mor-

L’ANNEAU Z ET SES QUOTIENTS - Institut de Mathématiques de

Montrez que les sous-groupes de(Z/NZ,+) sont aussi des idéaux de (Z/NZ,+,×) Montrez que ces sous-groupes sont en bijection avec les diviseurs positifs de N Un anneau A commutatif est dit intègre si le produit de deux éléments non-nuls est non-nul

34 Maximal and Prime Ideals - National University of Ireland

The following is a generalization of the statement that Z=nZ is a eld precisely when n is prime Theorem 3 4 2 Let R be a commutative ring with identity, and let M be an ideal of R Then the factor ring R=M is a eld if and only if M is a maximal ideal of R COMMENT ON PROOF: There are two things to be shown here We must show

Idéaux - univ-toulouse

Chapitre3 Idéaux 3 1 Idéauxd’unanneaucommutatif Déﬁnition3 1 1 Unidéald’unanneaucommutatifAestunsous-groupeI de (A,+)telquede plus: ∀x∈I , ∀a∈A,ax

COMPOSITION DE MATHÉMATIQUES

6: Soit un entier n 2 de décomposition en facteurs premiers n = p 1 1 p k k Montrer que N(Z=nZ) = (p 1 p k)Z=nZ 7: On suppose que I est premier Montrer que N(A) ˆI Deuxième partie II : Somme de deux idéaux 1: Montrer que I [J est un idéal de A ssi I ˆJ ou J ˆI Déﬁnition 2 : On déﬁnit la somme des idéaux I et J par I +J = fi+j

ALGÈBRE 2 ÉCOLE NORMALE SUPÉRIEURE 2012–2013

Exemple 1 8 — Si n>1, l’anneau Z=nZ est intègre si et seulement si nest premier C’est alors un corps On a nest un nombre premier ,l’idéal (n) est premier ,nest irréductible 1 Soit Iun idéal de Adistinct de A L’ensemble des idéaux de Acontenant Iet distincts de Aest inductif car si (I j) j2Jest une

Université de Poitiers

Created Date: 3/21/2012 4:36:19 PM

[PDF] anneau principal est factoriel

[PDF] anneau euclidien

[PDF] anneau factoriel non principal

[PDF] anneau principal non euclidien

[PDF] a quoi sert le sang wikipedia

[PDF] ideas association

[PDF] sinus carotidien barorécepteur

[PDF] ideas logiciel

[PDF] role du sinus carotidien sur l'activité cardiaque

[PDF] ideas economics

[PDF] ideas traduction

[PDF] ideas emulator

[PDF] ideas lego

[PDF] ideas emulateur

[PDF] ideas rms

Universite Claude Bernard{Lyon I

Agregation de Mathematiques : Algebre & geometrie

Annee 2009{2010AnneauxZ=nZ

Nous avons place nos ideaux bien plus haut que les plus hauts des ideaux. (Francis Blanche)

A ne pas rater

Zest euclidien, donc principal ;

theoreme de Bezout et lemme chinois (y compris la reciproque, voir ci-dessous) ; petit theoreme de Fermat/Euler/Lagrange (a'(n)= 1modnsia^n= 1) et Wilson. inversibles deZ=nZ, nombre et structure de groupe, (Z=pZ)est cyclique, application aux carres deZ=pZ: voir Perrin,Cours d'algebre; automorphismes deZ=nZ(comme groupe, puis comme anneau) ; voir [Perrin] ; quelques applications de la reduction modulo un nombre premier ; l'evocation de RSA semble presque obligatoire. Extraits de rapports du jury (recueillis sur le site de la preparation de Rennes)

2008 :Cette lecon classique demande toutefois une preparation minutieuse. Bien

ma^triser le lemme chinois et sa reciproque. Distinguer clairement proprietes de groupes additifs et d'anneaux. Conna^tre les automorphismes, les idempotents.

2007 :On attend la description des sous-groupes additifs deZ=nZ. Attention en general

sidjn,Z=dZn'est pas un sous-ensemble deZ=nZ. La description des elements inversibles pour la structure multiplicative doit ^etre connue. La structure des groupes abeliens de type ni doit ^etre connue, il y a deux presentations distinctes (diviseurs elementaires ou via lesp-Sylow) ; il faut savoir passer de l'une a l'autre.

2006 :Certaines identications rendent les exposes confus, voire faux :Z=nZidentie au

sous-ensemblef0;1;2;:::;n1gdeZ. Dans ces lecons, la loi de reciprocite quadratique est souvent proposee, mais les candidats ne proposent aucune application et ne savent pas calculer le symbole2p . Par ailleurs il faut faire tres attention a l'extension dans laquelle on travaille. En bref, on assiste souvent a une suite de calculs incomprehensibles. Il faudrait conna^tre les ideaux deZ=nZ. Il serait bon de ne pas donner des resultats tels que la caracterisation des nombres de Carmichael si l'on ne peut : en exhiber un et savoir (au moins) qu'il en existe une innite. A l'enonce d'un resultat, il est toujours utile de se poser la question de la reciproque. Ainsi, certains candidats ont retrouve (decouvert ?) avec l'aide du jury le plus souvent la reciproque du lemme chinois.

2005 :Pour le codage RSA, il serait utile de conna^tre la taille des nombres premiers

intervenant et une methode de calcul deakmodNecace : l'exponentiation rapide.

2004 :Le jury reste perplexe [...] quand un candidat montre l'irreductibilite des

polyn^omes cyclotomiques en passant dans le corpsZ=pZ, mais ne sait pas expliquer l'importance du choix deppremier.

2003 :Un homomorphisme d'anneaux envoie, par denition, l'element unite deAsur

celui deB. On peut alors trouver sans diculte tous les homomorphismes d'anneaux de

Z=mnZdansZ=mZZ=nZ.

1 Applications (a peu pres autant de developpements possibles) Reduction modpet application a l'irreductibilite des polyn^omes ; polyn^omes cyclotomiques et racines de l'unite : irreductibilite comme application du point precedent ; voir aussi Demazure,Cours d'algebre,x4.1 ; theoreme de Dirichlet faible ; noter que les facteurs premierspde d(10) sont les nombres dont la longueur du developpement decimal de 1=pestd(avecp^d= 1) ; algorithme RSA ; voir par exemple [Demazure],x2.4.5 ; test de primalite de Miller-Rabin : [Demazure],x2.4.7 etx.3.3.6 (utilise (Z=nZ)) ; transformation de Fourier discrete/rapide : [Demazure], chap. 4 ; peut-^etre [Peyre] ? sommes de Gauss et reciprocite quadratique : voir la lecon \Racines de l'unite" et [De- mazure],x5.2 ; ce point et le precedent ont l'inter^et d'utiliser desZ=NZavecNnon premier ; (tres joli, mais pas de source publiee) theoreme de Frobenius-Zolotarevetreciprocite quadratique : voir le court texte de J.-C. Raoult,http://agreg-maths.univ-rennes1. fr/documentation/docs/quadratique.pdf. theoreme des deux carres : pourppremier,p1 [4], il existeu;v2Ztels quep=u2+v2; attention au hors-sujet : pour coller ce theoreme a la lecon, il faut expliquer queZ[i] est principal (car euclidien), si bien que ses quotients sont des analogues desZ=nZ; on doit alors decider, pourppremier, si l'ideal (p) =pZ[i] est premier, i.e. si le quotient

Z[i]=(p)'Z[X]=(p;X2+ 1)'Fp[X]=(X2+ 1)

est integre, ce qui revient a savoir si1 a une racine dansFp; c'est le cas SSIp1 [4], et alorspn'est pas premier dansZ[i], et une factorisation depdonne une relationp=u2+v2; plus anecdotique : developpement decimal de 1=p.

Questions

1. Quels sont les ideaux deZ=nZ? les quotients deZ=nZ?

2. Quels sont les elements nilpotents deZ=nZ?

3. Quand a-t-onZ=nZ'Z=aZZ=bZ?

4. Pourp1 [4], donner une racine carree \explicite" de1 dansZ=pZ.

5. Quels sont les carres dansZ=pZ? dansZ=pZ? dansZ=nZ? Voir [Demazure],x5.1.4.

6. On donneppremier eta2(Z=pZ). Quelle est la signature deZ=pZ!Z=pZ,x7!ax?

Comme 0 est xe, la signature est la m^eme que celle de la restriction aFp. Siest la permutation def1;:::;p1ginduite par la multiplication para, la signature deest : Y x6=y(x)(y)xyY x6=yaxayxyap(p1)=2a(p1)=2modp: 2 Variante : DansFp, tous les cycles deasont de longueure, l'ordre dea, car a kx=xdonneejk. Par suite, la signature deaest : (1)p1e (e1)= (1)p1e et on conclut en remarquant que 2p1e ()ep12 ()a(p1)=2= 1()aest un carre dansFp.

7. Quels sont les automorphismes de corps deFq?

8. Quand est-ce que (Z=nZ)est cyclique ?

9. Quelle est la longueur de la periode du developpement decimal de 1/81 ? de 1/9801 ?

10. (a) Montrer que le developpement decimal de 1=nest periodique, et determiner sa

longueur. (b) Montrer que le nombre de periodes possibles dek=n, pourkpremier an, est l'indice deh10idansZ=nZ. (c) Quels sont tous les nombres dont le developement decimal a pour periode 6 ? I

A propos du plan

Sous-groupes et ideaux deZ=nZ

LemmeSoitn2Z. Tout sous-groupe deZ=nZest un ideal. Pour tout diviseurdden, il existe un unique sous-groupe d'indiceddansZ=nZ, le quotient par ce sous-groupe est isomorphe aZ=dZ. SoitHun sous-groupe deZ=nZ. Notons:Z!Z=nZla projection canonique. L'image reciproque1(H) est un sous-groupe deZ, donc il est de la formedZpourd2Zconvenable. Comme la classe de 0 appartient aH, son image reciproque Ker=nZest incluse dansdZ, si bien queddivisen. Par surjectivite de, on a :H=(1(H)) =dZ=nZ: c'est un ideal de Z=nZ. L'applicationZ!dZ=nZ,k7!dkest surjective. Son noyau estmZ, oum=n=d. Par suite, le groupeH=dZ=nZest isomorphe aZ=mZ.

Enn, on verie

1que, comme anneaux : (Z=nZ)=(dZ=nZ)'Z=dZ.

Remarque :CommeZ=nZn'est pas integre (sauf sinest premier), ce n'est pas un anneau principal bien que ses ideaux soient monogenes. 2

Aide-memoire : inversibles deZ=nZ

1. (Z=pZ)'Z=(p1)Z.

2. (1 +p)pk= 1 +lpk+1, aveclpremier ap.

3. Par suite, 1 +pest d'ordrep1dansZ=pZ.

4. La projection naturelle induit 1!Z=p1Z=h1 +pi !Z=pZ!Z=pZ!1.

5. 5

2k= 1 +l2k+2, aveclimpair, donc l'ordre de 5 dans (Z=2Z)est 22.

6. (Z=2Z)' f1g; (Z=4Z)'Z=2R; (Z=2Z)'Z=2Z=22Z(ou3) ?

7. Complement : Aut(Z=nZ)'(Z=nZ)en tant que groupes.

8. Application : groupes d'ordrepq.1

De facon generale, siJIsont deux ideaux d'un anneauR, alors (R=J)=(I=J)'A=I. Pour le montrer, verier que le morphisme naturelR!(R=J)=(I=J) a pour noyauI. 3 3

Idempotents

Confession d'un membre du jury : la preconisation \conna^tre les idempotents" est exageree. Mais il est bon d'avoir deja rencontre ce vocabulaire, you know, just in case...

Idempotents en general

SoitRun anneau unitaire, commutatif ou pas. On a principalement trois exemples en t^ete : Z=nZ,K[X]=(P) ouKest un corps etP2K[X] et les matrices carreesMn(K). Un idempotent deRest un elementetel quee2=e. Idee cle :Dans les matrices, les idempotents sont exactement les projecteurs. Ils servent a decomposer l'espace en produits d'espaces plus petits {a casser en morceaux, pourrait-on dire. On remarque une evidence : sie2=e, alors (1e)2= 1e. Les idempotents vont par paires. En termes de projecteurs, l'echange dee=pet 1e= Idpcorrespond a l'echange du noyau et de l'image ou, de facon equivalente, a l'echange des valeurs propres 0 et 1. LemmeSoitRun anneau ete=e2un idempotent central (qui commute a tous les elements deR) etf= 1e. (i)L'ensembleeR=fer; r2Rgest un ideal deRet un anneau pour la restriction des operations deR; le neutre de la multiplication este. (ii)Les applicationsR!eRfR,r7!(er;fr)eteRfR!R,(u;v)7!u+vsont des isomorphismes.

Application : lemme chinois

Le lemme chinois est un isomorphisme entre deux anneaux. Pour le demontrer, on peut denir le morphisme naturelZ=abZ!Z=aZZ=bZ(facile), montrer qu'il est injectif (ca resulte de l'identite de Bezout ou du lemme de Gauss) et en deduire qu'il est surjectif par cardinalite. Il est plus constructif d'exhiber le morphisme inverse, ce qui utilise plus ou moins explicitement des idempotents fournis par le lemme de Bezout. La remarque-cle est la suivante : soit (a;b)2Z2deux entiers premiers entre eux. Soit (u;v)2 Z

2tels queau+bv= 1. Alors (les classes de)bvetau= 1bvsont des idempotents deZ=abZ.

En eet, on a par exemple : (bv)2=bv(1au) =bvuv ab=aumodab, le reste en resulte. Examinons l'anneaueR, oueest la classe debvdansR=Z=abZ. L'applicationZ!eR, qui ax2Zassocie la classe debv xmoduloab, est un morphisme d'anneaux surjectif (verier !). Son noyau estaZcarabjbvxequivaut aajvx, ou encore aajxen remarquant queaetvsont premiers entre eux. On a donc un isomorphismeZ=aZ'eR. (Attention,Z=aZn'est pas, a proprement parler, un sous-anneau deZ=nZ.) Ainsi, siaetbsont premiers entre eux, on a en notantR=Z=abZete=bv:

Z=abZ=R'eR(1e)R'Z=aZZ=bZ:

Dans le plan, ne pas oublier la reciproque (et sa preuve). On a souvent a utiliser ce lemme de facon repetee dansZ=a1arZavec lesaipremiers entre eux deux a deux.

Analogie avec le lemme des noyaux

Placons-nous surK[X], ouKest un corps. On xe un espace vectorielEet un endomorphisme 'deE. SoitAetBdeux polyn^omes premiers entre eux. Le lemme des noyaux (version basique) s'ecrit :

KerAB(') = KerA(')KerB('):

Quitte a restreindre'a KerAB('), ce qui sut pour la preuve, on peut supposer queAB(') est nul. Choisissons deux polyn^omesUetVtels queAU+BV= 1. La cle du lemme, c'est de constater queBV(') (resp.AU(')) est le projecteur sur KerA(') parallelement a KerB(') (resp. sur KerB(') parallelement a KerA(')) {c'est tres facile a verier. 4 La version \complete" (indispensable pour la decomposition de Dunford), c'est d'ajouter que les projecteurs sur chacun des noyaux est un polyn^ome en'. Interpretons tout cela en termes de modules. On peut considererEcomme unK[X]-module, ou l'action deP2K[X] surv2Eest donnee par :Pv=P(')(v). Supposer que l'on a AB(') = 0, cela revient a dire queEest en fait unK[X]=(AB) module. Mais le lemme chinois demontre ci-dessus se demontre sans modication pourK[X] (l'ingredient essentiel, l'identite de Bezout, est disponible). Avece=BV, on a donc :

K[X]=(AB) =R'eR(1e)R'K[X]=(A)K[X]=(B):

(L'isomorphismeK[X]=(A)!eRest induit parP7!BV P.) Ainsi, la decomposition donnee par le lemme des noyaux est \la trace" de la decomposition de l'anneau donnee par le lemme chinois dans leR-moduleE, au sens ou KerA(') = ImBV(') = eRE. La decomposition en sous-espaces caracteristiques a l'interpretation suivante. On ecrit le polyn^ome caracteristiquePde'dansEcomme produit de facteurs irreductibles :P=Qr i=1Pii. Pour touti, on noteQi=P=Piiet on choisitUi;Vitels quePiUi+QiVi= 1. Par recurrence surr, on a alors une decomposition de l'unite, en notantei=QiVi:

1 =e1++ermodP:

Elle induit une decomposition comme produit d'anneaux :

R=K[X]=(P)'e1R erR;oueiR'K[X]=(Pii):

Par le theoreme de Cayley-Hamilton (P(') = 0), leK[X]-moduleEinduit une structure de K[X]=(P)-module. La decomposition precedente deR=K[X]=(P) induit une decomposition lineaire

E=e1E erE;oueiE= ImQiVi(') = KerPii('):

A ce titre, la decomposition en sous-espaces caracteristiques est une manifestation du lemme chinois.

Idempotents deZ=nZ

Soitppremier et2N. On montre que les idempotents deZ=pZsont 0 et 1.2 On procede par recurrence sur. CommeZ=pZest un corps, c'est clair pour= 1. Soit2 ete2Ztel quee2=emodp. Alorspdiviseeou (1e). Quitte a remplacerepar 1e, on peut supposer quee=pe0,e02Z. On a donce0(1pe0) = 0 modp1. Mais d'evidence,p1 et 1pe0sont premiers entre eux, si bien quep1divisee0. En d'autres termes,e= 0 modp. Soitn2Z, disonsn >0. On decomposenen produit de facteurs premiers,n=Qr i=1pii. Le lemme chinois precedent donne un isomorphisme

Z=nZ'!rY

i=1Z=piiZ; x7!(xi)i=1;:::;r deni par la famille des classes modulopiid'un element deZ=nZ. Sie=e22Z=nZ, chacun deseisatisfait aussiei=e2i2Z=piiZ, donceivaut 0 ou 1.

On a donc 2

ridempotents parametres par les partiesI f1;:::;rg, correspondant a autant de projections sur des ideaux qui sont aussi des anneaux isomorphes aZ=Q i2IpiiZ. La suite donne deux applications de l'arithmetique elementaire a la cryptographie. Merci a

Christophe Delaunay pour les infos.2

Argument heuristique : un autre idempotent donnerait une decomposition non triviale deZ=pZcomme produit d'anneau : on la conna^trait deja ! Mais, meance avec ce genre d'arguments... 5 II Cryptographie a cle publique : le protocole RSA Alice et Bob veulent echanger des messages secrets. Voici un protocole :

1. Preparatifs chez Alice :

Alice choisit deux (grands) nombres premierspetq;

Alice calcule

n=pqet'(n) = (p1)(q1) ; Alice choisit un entiere(encodage) inversible modulo'(n) ; Alice calcule, avec l'algorithme d'Euclide etendu,d(decodage) etftels que ed+f'(n) = 1 ;

Alice publie (n;e) (la cle publique).

2. Bob veut ecrire un message a Alice :

Bob transforme son message en un entiermnavec un codage entendu3;

Bob calcule

M=me[n] (le message code)

et l'envoie a Alice par telephone, sans precaution particuliere.

3. Alice recoit le message codeM: pour le traduire, elle calcule

A d= (me)d=mde=m[n]: Dans ce protocole, le seul secret est la factorisation den, c'est-a-direpetq. Ce secret est conserve par Alice : m^eme Bob n'est pas capable de decoder le message qu'il envoie. La securite de cet algorithme provient de ce que la factorisation denest un probleme repute dicile {plus precisement, de grande complexite algorithmique, i.e. qui prend un temps deraisonnable{, aussi dicile que le calcul de'(n). Mise en garde :Il peut y avoir des pieges si on choisipetqau hasard. Plus precisement, sip1 etq1 n'ont pas de \grand" facteur premiers, ils sont aisement factorisables et, par suite,nl'est egalement. (Pourquoi ?) (Je ne sais pas.) III Protocole de Die-Helman, logarithme discret et \baby steps { giant steps" 1

Protocole de Die-Helman

Alice et Bob decident de partager un secret, ce qui leur permettra d'elaborer un code pour echanger des messages.

1. Alice et Bob choisissent ensemble un grand nombre premierp, et trouvent un generateur

gdu groupe cyclique (Z=pZ); tout ceci peut ^etre public ;

2. Alice choisit un nombrenAau hasard, 1nAp1, calcule

A=nAg[p];

et envoiePAa Bob ;3

Par exemple, il traduit chacune des 26 lettres et des 6 symboles de ponctuation en un nombre compris entre

0 et 31, et il decoupe son message en mots deklettres : son message est donc une suite d'entiers ayantkchires

en base 32. 6

3. Bob choisit un nombrenBau hasard, 1nBp1, calcule

B=nBg[p];

et envoiePBa Alice ;

4. Alice calculenAPB=nAnBg[p] ;

5. Bob calculenBPA=nAnBg[p].

Au bilan, Alice et Bob partagentnAnBgcomme secret. 2

Probleme du logarithme discret

L'idee de ce protocole est la suivante :

connaissantgetn, il est tres facile de calculergn{environ log(n) multiplications ; connaissantgety, on pense qu'il est dicile de trouverntel quegn=y. C'est le probleme du logarithme discret. Pour le resoudre, on peut calculer g; g

2; g3;:::jusqu'a trouvergn=y:

Cette methode nave demandernoperations, ce qui est tres co^uteux sinest de l'ordre de grandeur dep. 3

Baby steps, giant steps

Il y a cependant une methode simple qui demande environ 2ppmultiplications, ce qui est bien mieux. Rappelons quegest un generateur de (Z=pZ); on donney2(Z=pZ)et on cherche ntel quegn=y[p] : on calculeq=pp , et on ecrit n=`q+r;avec 0r < qet 0`q; on a donc : (gq)`=ygr[p] ; on calcule et on stocke (gq)0;(gq)1;:::;(gq)q{lespas de geant; on calculeyg0;yg1;yg2;:::{lespas de bebe{ jusqu'a obtenir une collision ; on a alors : yg r= (gq)`[p] ; on a enn :n=`q+r. IV Une devinette cryptologique pour votre neveu de 8 ans Alice, qui habite a Wonderland, veut envoyer un colis a Bob, qui habite a Morane. Or, tous les facteurs de la region sont corrompus : si on envoie un colis non cadenasse, ils en prennent le contenu. Le probleme, c'est que Bob n'a pas la cle du ou des cadenas d'Alice. Comment peut-on proceder ? Reponse :Alice envoie un colis cadenasse a Bob. Bobajoute un cadenasau colis et renvoie le tout a Alice. Alice enleve son cadenas et renvoie le colis a Bob. Bob peut ouvrir le colis, qui est protege par son seul cadenas. 7quotesdbs_dbs13.pdfusesText_19

[PDF] Anneaux Z=nZ Universit e Claude Bernard{Lyon I