Algebra1AdilsonGon calvesLuizManoelFigueiredo17deSetembrode2004Conte udoAula7Ideaismaximaisen umerosprimos 3Aula 8 Fatora cao unica: o Teorema Fundamental da Aritmetica 11Aula9Osinteirosm odulon: Umaprimeiraapresenta cao 23Aula10Propriedadesdecongruenciaecriteriosdedivisibi-lidade 33Aula11Oanel dosinteirosm odulon 43Aula12inversosmultiplicativosedivisoresdezeroemZn511Ideaismaximaisen umerosprimosAULA7Aula7Ideaismaximaisen umerosprimosMetasNesta aula deniremos ideais maximais e mostraremos como os n umerosprimosest aorelacionadoscomosideaismaximaisde Z.ObjetivosAonaldestaaulavocedever asercapazde:Denirideaismaximaisde Z.Mostrarqueosn umerosprimoss aoosgeradoresdosideaismaximaisem Z;Demonstrar a equivalenciade tres propriedades que denem o conceitoden umerosprimos.Introdu caoO inteiro 1 s o tem um divisor positivo, que e o pr oprio. Qualquer outrointeiropositivoa>1tempelomenosdoisdivisorespositivos: 1ea. Umn umero echamadoprimoquandotemexatamentedoisdivisorespositivos.Osgregoschamavamosn umerosprimosdeprimeirosouindecomponveis eoscompostosdesecund ariosoudecomponveis. Osromanostraduziramdogregoparaolatimusandoapalavraprimospararepresentaressesn umerosprimeiros.Deni cao1(n umeroprimo)Um n umero inteiro a = 1 e um n umero primoquando s o tem dois divisorespositivos: 1e|a|.Os n umeros inteiros a =1 que n aos aoprimos s aochamados den umeroscompostos.Porexemplo, osinteiros2, 3, 5, 7, 11, 13, 17, 19, 23, 29 s aoos10primei-rosinteirosprimos positivos. Osinteiros2, 3, 5, 7, 11, 13 s aointeirosprimosnegativos.Noteque1n aos aon umerosprimos! Osinteiroscamassimdivididosem3subconjuntos: {1},osinteirosprimoseosinteiroscompostos.Os primos s ao as unidades b asicas em rela c ao as quais podemos expres-sar todos os n umeros inteiros, no sentido de que qualquer inteiro maior que 1pode ser escrito como produto de fatores primos. Este e o chamado TeoremaFundamentaldaAritmetica,queveremosmaistarde.Nessaaula,queservedeprepara c aoparaademonstra c aodochamadoTeoremaFundamentaldaAritmetica,mostraremoscomoosinteirosprimosest aorelacionadosaosgeradoresdosideaismaximaisde Z.3CEDERJAlgebra 1Ideaismaximaisen umerosprimosIdeaismaximaisdeZVamosiniciardenindoidealmaximalde Zeent aorelacionandoestesideaiscomosinteirosprimos.Deni cao2(IdealMaximal de Z)um ideal Mde Z e chamado maximal se e ideal pr oprio de Z (isto e, M Z)e Mn ao est a contido propriamente em nenhum outro ideal pr oprio de Z, ouseja,os unicosideaisde ZcontendoMs aoMe Z.Lembre-seque{0}eZs aoideaisdeZEmoutraspalavras,umidealMde Z emaximalsei. M Z(idealpr oprio)ii. SeIeumidealde Z,M I Z,ent aoI= MouI= Z.Exemplo1Oideal Z 6n ao emaximal. Defato,temosqueZ 6Z 2Z,poisx Z 6 x = 6q, paraalgumq Zx = 2(3q) x Z 2Assim, Z 6 Z 2,mas Z 6 = Z 2(por exemplo,2 Z 2, mas2 Z 6).Atividades1. MostrequeZ 8Z 4Z 2Z .2. Mostre que o ideal Zm, onde m e um inteiro composto, n ao e maximal.Rela caoentreideaismaximaisdeZeinteirosprimosSejaM Zumidealmaximalde Zesejap M+talqueM= Z p(existetalppeloteoremadosideaisprincipais).Lembre-sequeM+= M Z+O que podemos dizer a respeito desse n umero p?A primeira observa c aoe que, como M Z e p M+, temos p 2, j a que p = 1 nos daria M= Z.Eoquemaispoderamosdizer` arespeitodessen umerop 2, geradordeM?Aprimeirarespostavemdoseguinteresultado:CEDERJ4Ideaismaximaisen umerosprimosAULA7Proposi cao1SejaM= Z p,p 2,umidealmaximaldeZ. Ent aoD(p)+= {1, p},istoe,p eprimo.Demonstra c ao:SejaM=Z p,p2umideal maximal deZesejamD(p)+umdivisorpositivodep. Vamosprovarquem = 1oum = p.Defato, mD(p)+nos dizquep=m k,k>0eportantotodom ultiplo dep e tambemm ultiplo de m,isto e, M= Z p Z m. Como Meidealmaximalde Ztemosduaspossibilidades:(a) M= Z p = Z mou(b) Z m = Z.Agora(a) Z p=Z m=mZ m=Z p=m=s p,s>0. Masp=m keda segueque: m=(sk)moqueimplicask=1, comk, s > 0. Portantos = k= 1em = p.(b) Z m = Z,m > 0 =m = 1.Assimprovamosquem=1oum=peaProposi c ao1est ademons-trada. Demonstramosent aoque todo ideal maximal e gerado por um n umeroprimo. Opr oximoteoremaarmaquetambemvalearecproca: todoidealgeradoporumn umeroprimo emaximal.Teorema1Sejap 2umdadon umerointeiroesejaM= Z poidealprincipaldeZgeradoporp. Ent aoM= Z peideal maximal deZse, esomentese, peprimo.Demonstra c ao:(=)Essapartej afoidemonstradaatravesdaproposi c ao1.(=)Sejap 2umn umeroprimodado,esejaM= Z poidealprincipalgeradoporp.VamosmostrarqueM= Z p eumidealmaximalde Z.De fato, sabemosque Z n = Z se, e somentese, n = 1. Como p 2,teremos5CEDERJAlgebra 1Ideaismaximaisen umerosprimos(i) M= Z pZ(Meoidealpr opriode Z).Agora, seja Ium ideal contendo M, isto e, Z p = M I Z. Vamosprovar a condi c ao(ii) dadeni c aode ideal maximal,a saber,que I= MouI= Z(isto e,Memaximal).PeloTeoremadoIdeal Principal, existe m>0tal que I =Z m.Estamos assumindo M=Zp I =Zm. Assim, p Mimplicap I= Z moqueimplicaqueexisteumk> 0talquep = k m. Assim,mD(p)+={1, p}(pois estamos assumindo p 2primo). Portantom {1, p}.Se m = 1 temos I= Z m = Z 1 = Z. Por outro lado, se m = p temosI= Z m = Z p = Meistocompletaademonstra c ao. Atividades1. Mostreque Z 5 eumidealmaximalde Z.2. Mostreque Z n = Z n = 1.Propriedadesdosn umerosprimosNaaula6vimosquesea, bZ+ed>0tal queZ a + Z b= Z dent aod= mdc(a, b). Emparticular, comod Z d,ent aod Z a + Z b,istoe, existemr, sZtaisqued=ra + sb. Seomdc(a, b)=1, existir aor, s Ztaisquera + sb = 1.Agoravamosdemonstrarumaproposi c aoqueser ausadanademons-tra c aodopr oximoteorema,queprovaaequivalenciadetrescondi c oesparaadeni c aoden umerosprimos.Proposi cao2Sejap2umn umeroprimoesejaaZ+. Sepn aoedivisordeaent aomdc(a, p) =1. Emparticular, nessasitua c ao, existemr, s Ztais querp + sa = 1.Demonstra c ao:Sejap 2umn umeroprimo. Assim, D(p)+={1, p}e sejad =mdc(p, a). Peladeni c aodemdctemosque:d = max(D(p)+ D(a)+) .CEDERJ6Ideaismaximaisen umerosprimosAULA7Sepn aoedivisordeaent aopD(a)+eda segue, tendoemvistaqueD(p)+= {1, p},queD(p)+ D(a)+= {1}e,portanto,d = max(D(p)+ D(a)+) = 1.Pelaobserva c aofeitaantesdoenunciadodessaproposi c ao,temosque,sep2primon aoedivisor deaZ+, ent aoexistemr, sZtaisque1 = rp + sa. Nota caopara divisibilidade: Usamos anota c aod| aquandodeumdivisordea. Casocontr ario,escrevemosd | a.Agoramostraremosaequivalenciadetrespropriedadesquecaracteri-zamn umerosprimos.Teorema2Seja p 2 umn umero inteiro dado. Ent ao as seguintes condi c oes s aoequivalentes:(i) p eprimo,isto e,D(p)+= {1, p}(ii) Paratodoa, b Z+sep|abent aop|aoup|b(iii) Sep = mkcomm, k Z+ent aom = 1ouk= 1.Demonstra c ao: (caminhocclico(i)=(ii)=(iii)=(i)).(i)=(ii)Suponhamosp2primoea, bZ+comp|ab. Vamosmostrarquep|aoup|b.Sep|aent aonadah aaprovar. Suponhaquep | a. Pelaproposi c aoanterior,temosquemdc(p, a) = 1eexistemr, s Ztaisquerp + sa = 1.Multiplicandoestaigualdade por b temos p(rb) + s(ab) =b, istoe,b =(rb)p + s(ab). Sep|abtemos ab =pm, paraalgummZ, eassimb=(rb)p + (sm)p=(rb + sm)peistonosdizquep|b. Portanto, sep | a,temosp|b.(ii)=(iii)Vamosassumiragoraqueparatodoa, bZ+sep|abent aop|aoup|b. Vamosprovar(iii).De fato, sejam m, k Z+tais que p = mk. Da segue que p e divisor dep = mk. Portanto,por(ii),temosquep|moup|k. Masp|mimplicap mep = mk mimplicap = m,isto e,k = 1.7CEDERJAlgebra 1Ideaismaximaisen umerosprimosMas p|kimplica p ke p = mk kimplica p = k, isto e, m = 1 comoqueramosdemonstrar. Logo(ii)=(iii).(iii)=(i) Vamossupor p2tal que, sep=mkcomm, kZ+ent aom = 1ouk = 1. Vamosprovarquep eprimo.SejarD(p)+. Assimp=rsparaalgumsZ+. Por(iii)temosr=1ous=1. Ses=1, r=p. Logor=1our=peistonosdizqueD(p)+= {1, p},isto e,p eprimo. Denimosanteriormenteuminteiroprimocomoaquelequesatisfazacondi c ao(i) do teoremaanterior. A equivalenciadas 3 condi c oesnos mostraque poderamos ter usadoqualquer umadelas comodeni c aode n umeroprimo.Atividades1. Deumexemplodeinteirosm, aebtaisquem| ab, masquem| aem|b. Porqueesteinteiromdevesernecessariamenteumn umerocomposto?MaissobreomdcdedoisinteirosVimosque, seaebs aodoisinteirosed=mdc(a, b), ent aoexistemxeytaisquexa + yb=d. Ovalorded=mdc(a, b)podesercalculadodemaneiraecienteusandooalgoritmodeEuclides. Aquest aoquecolocamosagora e: comocalcularestesxey,dadosaeb?A resposta e que podemos inverter os passos do algoritmo de Euclidesparaescrevermosdemtermosdeaeb. Vamoscome carcomumexemplo.Exemplo2Calcule, utilizandooalgoritmodeEuclides, omdcde300e135eeescrevaesteinteiroemtermosde135e300.Vamosl a. UsandooalgoritmodeEuclidestemos:300 = 2 135 + 30135 = 4 30 + 1530 = 2 15 + 0CEDERJ8Ideaismaximaisen umerosprimosAULA7Vemosque15=mdc(300, 135). Paraescrever15emfun c aode300e135,come camoscomapen ultimaequa c ao:135 = 4 30 + 15 15 = 135 4 30Agorasubstitumos30pelovalorquepodemosobternaprimeiraequa c ao:15 = 135 4 30 = 135 4(300 2 135) = 4 300 + 9 135Atividades1. Determineinteirosxeytaisque1 = x 198 + y 25.ResumoNestaaula abordamos os inteiros primos. Todo inteiro pode ser escritocomoprodutoden umerosprimos,oqueprovaremosnapr oximaaula.H av ariasmaneirasdedenirmosn umerosprimos. OTeorema2apre-senta tres propriedades equivalentes que caracterizamos inteiros primos.Qualquerumadelaspoderiatersidoutilizadacomodeni c ao.Osideaispr opriosdeZquen aoest aocontidosemoutroidealpr opriode Z s aoosideaismaximaisde Z. Vimosqueestess aoexatamenteos ideaisgeradosporprimos. Estaeumaoutracaracteriza c aodeprimosemZ, estamaisalgebrica. Voltaremosaelaquandoestudarmosaneisemgeral.9CEDERJAlgebra 1Ideaismaximaisen umerosprimosExerccios1. Encontreinteirosxeytaisquexa + yb = mdc(a, b),onde:(a) a = 102eb = 33.(b) a = 15ec = 50.(c) a = 20ec = 1.2. Provequeinteirosconsecutivosdevemserprimosentresi.3. Proveque2a + 1e4a2+ 1s aoprimosentresi.4. Sejama, b, c Z+inteirospositivosdados. Mostrequea mdc(b, c) = mdc(ab, ac)5. Sejama, m, n Z+inteirospositivosdados. Mostrequemdc(a, m) = mdc(a, n) = 1 =mdc(a, mn) = 1 .6. SejaI= Z n Zumdadoidealde Zonden Z. MostrequeI= Z n = Z n = 1 .7. SejaI1 I2 I3 In umacadeiadeideaisdeZ. MostrequeI=_i=1Ijeumidealde Z.8. SejamI eJdoisdadosideaisdeZ. Mostreque: seI JeJIent aoI Jn ao eumidealde Z.9. Sejap 2umdadon umeroprimo. Mostrequeos unicosm ultiplosdepn aonulosques aon umerosprimoss aopep.CEDERJ10Fatora cao unica: oTeoremaFundamental daAritmeticaAULA8Aula8Fatora cao unica: oTeoremaFundamentaldaAritmeticaMetasNestaaulaapresentaremosoconjuntodosn umerosprimoscomopilarb asiconadecomposi c aoden umerosinteiroscomoprodutodeprimos.ObjetivosDemonstrar oTeoremaFundamental daAritmetica(teoremadafa-tora c ao unica);Demonstrar,usandooteoremadafatora c ao unica, queoconjuntodosn umerosprimos einnito;ExprimirerelacionarMDCeMMC,usandoafatora c ao unica.Introdu caoNestaaula demonstraremoso teoremadafatora c ao unica, tambemco-nhecidocomooTeoremaFundamental daAritmetica. Nesse Teoremaosn umeros primos aparecem como pilar b asico, indecomponveis,e cada inteiropodesedecomporcomoprodutodefatoresprimos.C.F.Gauss,matem aticoalem aodoseculoXVIII/XIX, foioprimeiroadesenvolveraaritmeticacomociencia,demodosistem atico. OenunciadodoTeoremaFundamental daAritmetica,comoapresentamosaqui,foipublicadoem1801, nofamosolivroDisquisiotoresArithmetcal.Oconhecimentodadecomposi c aoemfatoresprimosnospermitir ade-monstrar propriedades importantes sobre n umeros inteiros. Essa decom-posi c aoe unicaamenos daordena c aodos fatores primos que entramnadecomposi c aodon umero.Observequeseconsider assemos 1comoprimo, n aoteramosdecom-posi c ao unica em fatores primos. Por exemplo, 2 = 12 = (1)22 = 132 = .ConsiderandoqueD(n)+= D(n)+,equep eprimose,esomentesep e primo,teramos, por exemplo,6 = 2 3 = (2)(3). Parasimplicaranossaabordagem, essencialmentesemperdadegeneralidade, vamostraba-lharcomprimosp2efatorar, noTeoremaFundamental daAritmetica,n umerosinteirosn 2.11CEDERJAlgebra 1Fatora cao unica: oTeoremaFundamental daAritmeticaComoaplica c aodoteoremadafatora c ao unica, vamos provar queoconjunto dos n umeros primos e innito e tambem explicitar e relacionar MDCeMMC.Umpoucodehist oriaAntes de enunciarmos o teorema fundamental vamos fazer as observa c oessobren umerosprimosdandoumaideiadequemuitasquest oesenvolvendon umerosprimosaindaest aoporserresolvidas.N os vamos provar, usando o Teorema Fundamental da Aritmetica(Teorema1, aseguir),que oconjuntodos n umeros primos e innito,usandoumbeloargumentodevidoaEuclides.Para se ter uma ideia da import ancia do tema, podemos citar que v ariosmatem aticosapresentaram,emdiferentesepocas,demonstra c oessobreain-nitudedoconjuntodosn umerosprimos.Por exemplo, Kummer(1878), P olya (1924), Bellman (1947), Washing-ton(1980),entreoutros.Umoutroaspectoasedestacareadiculdadededecidirmosseumn umero inteiro N, muito grande e ou n ao primo. H a algoritmos que indicamse um inteiro e ou n ao primo, estes algoritmos s ao conhecidos como testes deprimalidade.PierreFermat, matem aticofrancesdoseculoXVII,conjecturouqueosn umeros daformaFm=2m+ 1comm=2neramtodos primos. Os 5primeirosn umerosdeFermats ao,defato,primos:F0= 3, F1= 5, F2= 17, F3= 257e F4= 65.537 .No entanto, Euler provou que F5= 6416700417. Portanto, F5 n ao e primo.Os primos daformaFn=22n+1s aoconhecidos como primos deFermat. Omaior primodeFermat conhecidoatehojeeF4. Paraseterumamelhorcompreens aodasdiculdadesaquienvolvidasbastadizerqueon umero de Fermat F23471possui mais de (10)7000algarismos e foi provado quen aoeprimoporKeller, em1984. On umeroF31possui maisde30bilh oesdealgarismos.Uma quest ao ainda n ao resolvida e saber se existem innitos primos deFermatFn. Tambemn ao econhecidoseosn umerosF22, F24, F28s aooun aoprimos.Em aulas futuras, voltaremos a fazer mais observa c oes sobre esse tema eCEDERJ12Fatora cao unica: oTeoremaFundamental daAritmeticaAULA8falaremos dos chamados n umerosdeMersenne, que s ao os n umeros da formaMn=2n 1. S aodeespecial interesseosn umerosdaformaMp=2p 1com p primo. Um primo da forma 2p1 e chamadoum primo de Mersenne.M2=3, M3=7, M5=31, M7=127, s aoprimosmas, M11=23 89eumn umerocomposto.Muitos dos chamados primos gigantes foram obtidos testando os n umerosdeMersenne. O maior primoconhecidonestemomento e um primodeMer-senne. Trata-sedon umero2240365831Este e o 41oprimo de Mersenne conhecido e tem exatamente 7235733 dgitos!Suaprimalidadefoi provadaem 15de maiode 2004, parte de umgrande es-for co de trabalho colaborativo pela Internet chamado GIMPS (Great InternetMersennePrimeSearch).BoasreferenciassobreosprimosdeMersenne,s aohttp://www.mersenne.org/prime.htmehttp://www.utm.edu/research/primes/mersenne/MarinMersenne(1588-1648) foiummongefrances,contempor aneodeFermat. Elen aofoioprimeiroaestudarosn umerodaformaMn= 2n1,mas entrounahist oriapor armar, em1644, queos n umeros 2n 1s aoprimosparan = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 e257ecompostosparatodososoutrosinteirospositivosn < 257.Por esta arma c ao, ali as incorreta, o nome de Mersenne cou associadoaosprimosdaforma2n1.Comrela c aoaosn umerosdalistadeMersenne, ef acil ver queparan = 2, 3, 5, 7, 13 os n umeros 2n1 s ao primos. O fato de que 2171 e 2191s aoprimoseraconhecidoantesdeMersenne.Cercade 100 anos depois, em 1750, Euler mostrou que 2311 e primo.Outro seculo depois, em 1876, Lucas mostrou que 21271 e primo. Um poucomaistarde, em1883, Pervouchinemostrouque261 1eprimo. Portanto,faltavauminteironalistadeMersenne.No incio do seculo XX, Powers mostrou que os n umeros 2891 e 21071tambem s ao primos. Os inteiros 89 e 107 devem ent ao se acrescentados ` a listadeMersenne. Porvoltade1947, todososinteirosn 1.Assim,provamosqueparaqualquern,temos:Zn= {0} {a | mdc(a, n) = d > 1} {a | mdc(a, n) = 1} divisoresdezero inversveisCEDERJ56inversosmultiplicativosedivisoresdezeroem ZnAULA12AtividadesDeterminetodososdivisoresdezeroetodososelementosinversveisem Znparaosseguintesinteirosn:1. n = 8 2. n = 10 3. n = 12OcorpoZpNo caso do anel Zp, com p um primo, todos os elementos n ao-nulos s aoinversveis,isto e, n ao h a divisores de zero, como mostra o seguinte corol ariodaProposi c ao2.Corolario2Sep2eumn umeroprimo, ent aotodoelementoa=0emZppossuiinversomultiplicativo.Demonstra c ao.Sejap 2umn umeroprimoesejaa = 0. Temosquea = 0 p | a .Como p e primoe p | a ent ao mdc(a, p) = 1. PelaProposi c ao 2 segue-se queapossuiinversomultiplicativo. Encontramos aqui um anel com uma propriedade especial muito impor-tante: adequetodoelementon ao-nulopossuiinversomultiplicativo. Aneisdestetipos aochamadoscorposepossuemgrandeimport ancianaAlgebra.Deni cao3(Corpo)Umanel comutativocomunidade tal que todoelementon ao-nulopossuiinversomultiplicativoechamadoumcorpo.Portanto, oanel Zp, +, , comp2primo, eumcorpo. Esteeumcorpocomexatamentepelementos:Zp= {0, 1, , p 1} .Estee, portanto, umcorpocomumn umeronitodeelementos, ouseja,umcorponito.O anel Z n ao e um corpo. Os unicos inteiros n ao-nulos que possuem in-verso multiplicativo s ao os inteiros {+1, 1}. Os outros inteiros n ao possueminversomultiplicativo.57CEDERJAlgebra 1inversosmultiplicativosedivisoresdezeroemZnJ a oanel Q,dos n umeros racionais, e um corpo. Todon umeromn,comm, n = 0,possuiinversomultiplicativo,asaber,ointeironm,poismnnm= 1CalculandooinversomultiplicativodeaemZnSemdc(a, n)=1ent aoaclasseapossui inversamultiplicativa. Mascomocalcularestainversa?Vimosquemdc(a, n) = 1 Existemr, s Ztaisquera + sn = 1Masra + sn = 1 r a + s n = r a + 0 = 1 r a = 1Assim,reoinversomultiplicativodea.Exemplo16Calculeoinversomultiplicativode23emZ61.E f acil ver que mdc(23, 61) = 1 porque 23 e primo e 23 | 61. Usaremoso algoritmo de Euclides para determinar os inteiros r, s tais que 23r+61s = 1.Temosque61 = 2 23 + 15 = 15 = 61 2 2323 = 1 15 + 8 = 8 = 23 1 1515 = 1 8 + 7 = 7 = 15 1 88 = 1 7 + 1 = 1 = 8 1 7Invertendoospassostemos:Osn umerosemnegritos aoossubstitudosacadapassopelosvaloresobtidosnasdivis oessucessivasacima1 = 8 1 7 = 8 1 (15 1 8) = (1) 15 + 2 8= (1) 15 + 2(23 1 15) = 2 23 3 15 = 2 23 3 (61 2 23)= 8 23 3 61Portanto,8 eoinversomultiplicativode23em Z61. Escrevemostambem8 231(mod61) .CEDERJ58inversosmultiplicativosedivisoresdezeroem ZnAULA12ResumoNestaaulaestudamosduaspropriedadesrelacionadas` amultiplica c aode elementos de Zn. Estudamos os divisores de zero e os elementos inversveisem Zn. Aprendemosareconheceresteselementos: dadoa Zn,coma = 0,temosquemdc(a, n) = 1 a einvertvel em Znmdc(a, n) = d > 1 a edivisordezeroemZnPor m, aprendemos a calcular efetivamente o inverso multiplicativo deumaclassea Zn,commdc(a, n) = 1,utilizandooalgoritmodeEuclides.Atividades1. Mostrequesea=0possui inversomultiplicativoemZn, ent aoesseinversoe unico.2. Encontreoinversomultiplicativode:(a) 29em Z121(b) 15em Z67.59CEDERJ