Introducao`aTeoriadosN umeros:AlgoritmodaDivisao,N
umerosPrimoseAritmeticaModularJoaoCoelhoFilhoDepartamentodeMatematicaeInformatica-UEMAJoaoCoelhoFilhoIntroducao`aTeoriadosNumeros:Algoritmo
daDivisaoN umeros Primos eAritmetica ModularSaoLus2011Sumario1
ConjuntoseN umeros 11.1 ConjuntosOrdenados. . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . 11.2 Indu caoFinita . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3
ConjuntosFinitoseInnitos . . . . . . . . . . . . . . . . . . . . .
. . . . . . 62 TeoriadosN umeros 112.1 AlgoritmodaDivisao. . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . 112.2
MaximoDivisorComum. . . . . . . . . . . . . . . . . . . . . . . . .
. . . . 172.3 Equa caoDiofantina. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . 202.4 N umerosPrimos . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . 223
AritmeticaModular 253.1 Congruencias . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . 253.2
CriteriosdeDivisibilidade . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 273.3 ClassesResiduais . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . 283.4 Aplica cao . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30Bibliograa 334Captulo 1ConjuntoseN
umerosNestecaptuloeapresentadooPrincpiodeIndu
caoFinita(1oe2oForma), algumasdeni
coeseresultadosclassicossobreconjuntosbemordenados, nitos,
enumeraveisenaoenumeraveisqueseraonecessariosparacursossubsequentes.1.1
ConjuntosOrdenadosDenicao1.1Umarelacao
RemumconjuntonaovazioAeumarelacaodeequivalenciaemA,seasseguintescondicoessaosatisfeitas:1-x
Rx, x A(reexiva);2-sex Ry,entaoy Rx, x, y A(simetrica);3-sex Ryey
Rz,entaox Rz(transitiva).Quando uma rela cao R em um conjunto A e
uma rela cao de equivalencia em A, em geral,e adotado a nota cao x=
yem vez de xRye diz-se x e equivalente a ymodulo R Exemplos:1.
Arela caodeigualdadesobreRtalquexRy x = yeumarela
caodeequivalencia,pois(i) x se x R =x = x;(ii) x, y se x = y =y=
x;(ii) x, y, z se x = y e y = z x = z.2. Arela
caodeparalelismo//sobreumespa coEuclidianotalquexRy x//y1Captulo1.
ConjuntoseN umeros 2eumarela caodeequivalencia,pois,sex, y,
zsaoretasdoespa co,tem-se(i)x//x;(ii)x//y=y//x;(ii)x//yey//z
=x//z.Denicao1.2Umarelacao RemumconjuntonaovazioA
eumarelacaodeordememA,seasseguintescondicoessaosatisfeitas:1-x Rx,
x A(reexiva);2-sex Ryey Rx,entaox=y(antisimetrica);3-sex Ryey
Rz,entaox Rz(transitiva).Quando uma rela cao R em um conjunto A for
uma rela cao de ordem, em geral, e adotadoanota cao emvezde
Redizemosquex emenorqueouigualay.Exemplos:1. SejaA = R. Parax, y
A,dene-sexy x y,ondeeaordemnatural emR. Entaoefacil vericar que
eumarela caodeordememA.2. SejaA = R R. Para(a, b), (c, d)
A,dene-se(a, b)(c, d) a ceb d.Entaoeumarela
caodeordememA.Solucao.(i) (a, b)(a, b),poisa aeb b;(ii) Se(a, b)(c,
d)e(c, d)(a, b),entaoa < coua = ceb d.ec < aoua = ced
b.Comoapossibilidadea < cec < anaopodeocorrer,tem-sequea =
c,b ded b.Logo,a = ceb = d. Portanto,(a, b) = (c, d).(iii) (a,
b)(c, d)e(c, d)(x, y) (a, b)(x, y).Captulo1. ConjuntoseN umeros 33.
SejaA = N. Parax, y A,dene-sexy x eumm ultiplodey.Entao
efacilvericarqueeumarela caodeordememA.4. SejamAumconjuntonaovazioe
P(A)oconjuntodaspartesdeA. ParaX, Y P(A),dene-seXY X Y.Entao
efacilvericarqueeumarela caodeordememA.Um
conjuntoparcialmenteordenado e um conjuntoA equipadocom uma rela
cao deordem,tambemdenominadadeordemparcial. SeB
eumsubconjuntodeA,entaoAinduzumaordemparcialemBdoseguintemodo:xy,
x, y B
xyemA.UmconjuntoparcialmenteordenadoAetotalmenteordenadoouumacadeiaouline-armenteordenado
sexyouyx, x, y A;istoe,quaisquerdoiselementosdeAsaocomparaveis.
Porexemplos, N, Z,
QeRsaototalmenteordenadospelaordemnatural,enquantoosexemplos3e4,acima,naosaototalmenteordenados.Seja
A conjunto parcialmente ordenado e X um subconjunto de A. O menor
(maior)elementodeXeumelementoa Xtalqueax(xa)paratodox X.
DizemosqueXelimitadoinferiormente(superiormente)seexistira
Atalqueax(xa)para todo x X. Note que o elemento a nao
necessariamente pertence a X. O elementoa
echamadodecotainferior(superior)deX. UmsubconjuntodeA
elimitadoseeleelimitadoinferioresuperiormente.Observacao1.1Paramostrar
que umelementoa Anaoe cotainferior de XAdevemosexibirumelementoxo
Xtal quexo a.Exemplo. Os Naturais N contem um menor elemento1 com
ordem natural, nao contemmaior elemento, pois a < a+1 para todo
a N, Teorema 1.1, enquanto Z nao contem menornemmaiorelemento.Um
conjuntoparcialmenteordenado A e bemordenado se todo subconjuntonao
vazio deAcontemummenorelemento.
NotequequalquerconjuntoAbemordenadoetotalmenteordenado,poissea, b
A,entaoosubconjunto{a, b} ACaptulo1. ConjuntoseN umeros
4contemummenorelementoaoub,isto e,abouba.Exemplo. OsconjuntosZ,
QeRcomaordemnaturalnaosaobemordenados, poisosubconjuntoX= {. . . ,
3, 2, 1, 0}enaovaziomasnaocontemmenorelemento. Embora,
sejamtodostotalmenteordenados.Portanto,haconjuntostotalmenteordenadosquenaosaobemordenados.Umdosaxiomasqueserausadoimplicitamentemuitasvezes,eoseguinte:Axioma1TodosubconjuntonaovaziodeNcontemummenorelemento.Exemplo.
Sejama, b N. Mostrarqueexisten Ntalquena b.Solucao.
Suponhamos,porabsurdo,quena < b, n N. SejaX= {b na : n N}.EntaoX
= . Assim, peloAxioma1, existex0=b n0a Xtalquex0 x, x X.Comob (n0 +
1)a X,poisXcontemtodososinteirosdestaforma,temosqueb (n0 + 1)a =
x0a < x0,oque eumacontradi cao.Teorema1.1Sex, y Ncomx <
y,entaox + 1 y.Exemplo.
TodosubconjuntolimitadosuperiormentedeNpossuiummaiorelemento.Solucao.
SejaXumsubconjuntolimitadosuperiormentedeN. SejaY= {a N : x a, x X}
N.EntaoY= . Assim, peloAxioma11, existey0 Y tal quey0 y, y Y .
Agora,vamosmostrarquey0 X. Suponhamos,porabsurdo,quey0 X. Entaox
< y0, x X.Assim, peloTeorema 1.1, xy0 1, xX. Logo, y0 1Y , oque
contradiz aminimalidadedey0.1.2
InducaoFinitaTeorema1.2(PrincpiodeInducao1oForma)SejaXumsubconjuntodeNcomasse-guintespropriedades:1.
1 X;2. x N, x X x + 1 X.Captulo1. ConjuntoseN umeros 5EntaoX=
NExemplo. Mostrarque1 + 2 + . . . + n =n(n + 1)2, n N.Solucao.
SejaX=_n N : 1 + 2 + . . . + n =n(n + 1)2_ N.Entao:(i) 1 X,pois1
=1(1 + 1)2.(ii) Suponhamos,comohipotesedeindu
cao,queoresultadosejavalidoparaalgumk> 1,isto e,k X.1 + 2 + . .
. + k + (k + 1) =k(k + 1)2+ (k + 1)=k(k + 1) + 2(k + 1)2=(k + 1)(k
+ 2)2.Logo, k + 1 X. Portanto,X=
N.Teorema1.3(PrincpiodeInducao2oForma)SejaXumsubconjuntodeNcomasseguintespropriedades:1.
1 X;2. x N, {1, 2, . . . , x} X x + 1 X. EntaoX= N.Exemplos.1.
Sejaasequenciaa1= 1, a2= 3ean= an1 + an2, n Ncomn 3. Mostrarquean
0. Entao unicosq, r Ztaisquea = qb + ronde0 r <
bProvadaExistencia. Suponhaquea 0, poissea 0bastasubstituirapor a
0.Quandoa = 0,tem-seq= r = 0;quandoa = b,tem-seq= 1er = 0;quandoa
b,tem-seq = 0er = a. Assim,deve-sesupora > bea 1. SejaX= {a N |
a =b +r, onde0 r < b }Entao,(i) 1 X,pois1 = 1 1 + 0;(ii)
Suponhaporhipotesedeindu caoqueoresultadoevalidoparatodok,1 k a
1,isto e, {1, 2, . . . , a 1} X. Comoa > b > 0, tem-se que0
< a b < a. Pelahipotesedeindu cao,existemq1, r Z,taisquea b
=q1b + r, onde0 r < b.Fazendo,q= q1 + r,obtem-sequea =qb + r,
onde0 r < b.11Captulo2. TeoriadosN umeros 12ProvadaUnicidade.
Suponhaqueexisteq1, q2, r1, r2 Ztaisquea =q1b + r1, onde0 r1<
bea =q2b + r2, onde0 r2< b.Assim,q1b + r1=q2b + r2 (q1q2)b
=r2r1.Alemdisso,0 r2< beb < r1 0 =0 |r2r1| <
b.Logo,|q1q2|b = |r2r1| < b =0 |q1q2| <
1.Portanto,peloTeorema?,tem-seque |q1q2| = 0,isto e,q1=
q2eassim,r1= r2.Exemplo2.1Sejama = 1998eb = 7.
Determinaradivisaodeaporb.Solucao1998 = 285 7 + 3 =1998 = 285 7 +
(3) =1998 = 286 7 + 4.Assim,q = 286er = 4.Corolario2.1Sejama, b
Zcomb = 0. Entaoexistem unicosq, r Ztaisquea =qb + r, onde0 r <
b.ProvaE suciente considerar o caso em que b < 0. Entao |b| >
0 e pelo Teorema 2.1 existem unicosq1, r Ztaisquea =q1|b| + r,
onde0 r < |b|.Como |b| = befazendoq = q1,tem-sequea =qb + r,
onde0 r < |b|.Exemplo2.2Sejama = 2466eb = 11.
Determinaradivisaodeaporb.Solucao2466 = 224 11 + 2 =224 (11) + 2.
1998 = 286 7 + 4.Assim,q = 224er = 2.Captulo2. TeoriadosN umeros
13Denicao2.1Sejama, b Zcomb =0.
Diz-sequebdivideaoubedivisordeaouqueaeumm ultiplodea,emsmbolosb |
a,seexistec Ztal quea =
bc.Casocontrario,diz-sequebnaodividea,edenota-seb a. Alemdisso,a Z
eumn umeroparse2 | ae mparse2 a.Observacao2.1Ointeiroctal quea =
bce unico,poissec Zsatisfaza = bc,entaoa a = bc bc= b(c c) =c c= 0
=c = c.Teorema2.2Sejama, b, c Z.
Entaoasseguintescondicoessaosatisfeitas:1. 1 | a,a | a;2. b | 1 b =
1;3. b | aea > 0 b a;4. b | a bc | ac;5. b | aea | c b | c;6. b
| aea | b a = b;7. c | aec | b c | (ax + by),x, y Z.ProvaSomenteos
tens2e6saomostrados,osdemaiscamcomoexerccio.2. b | 1 d Ztalquebd =
1 |bd| = |b||d| = 1.Comob, d Z,tem-se,peloTeorema?,que |b| 1e |d|
1. Assim,se |b| > 1,entao|bd| = |b||d| > |d| 1,oque
eumacontradi cao. Logo, |b| = 1. Portanto,a = b.6. Sea | beb |
a,entaoexistemd, e Z,taisquea = bdeb = ae. Assim,b =ae =bde =de
=1.Logo,d = e = 1. Portanto,a = b.Teorema2.3Sejab Zcomb>1.
Entaoparatodoa Nexistem unicosn, ri Ztaisquea = rnbn+rn1bn1+
+r1b1+r0b0= (rnrn1 r1r0)b, (2.1)onderi {0, 1, . . . , b 1}, i = 0,
1, . . . , nen = logb a.Captulo2. TeoriadosN umeros 14ProvaSejaX=
{a N | a = rnbn+rn1bn1+ +r1b1+r0b0}.Entao(i) 1 X,poisparan = 0er =
1,tem-se1 = r0b0.(ii) Suponhaqueoresultadovaleparatodokcom1 k a,
ouseja, {1, 2, , a} X.PeloTeorema2.1,existemqer0taisquea + 1 = qb +
r0, onde0 r0< b.Considerandoq>0,poisquandoq=0,tem-sen=0,r0=a
+ 1eassim, a + 1 XComoa + 1 > 0er0 0,tem-sequeq a,poissea <
q,entao1 < b a + 1 qeq 0, istoe, existemx, y Ztaisqued = ax +
by.Paramostrarqued = mdc(a,
b),utiliza-seoTeorema2.1,peloqualexistemq.r Ztaisquea = qd + r,
onde0 r < d.Entaor = a qd = a(1 qx) + b(qy) r = 0,poisser>0,
entaor X, oqueeumacontradi caonaescolhaded. Assim, a=qdoud |a.
Analogamente, mostra-sequed |b. Finalmente, sec |aec |b, entao,
peloTeorema2.2,c | (ax + by),isto e,c | d.Sejama, b Z.
Diz-sequeaebsaorelativamenteprimosouprimosentresi quandomdc(a, b) =
1.Captulo2. TeoriadosN umeros 18Teorema2.5Sejama, b Z. Entaoaeb
saorelativamenteprimos se, esomentese,existemx, y Ztaisqueax + by=
1.Provasuponhaqueexistamx, y Ztaisqueax + by=1ed=mdc(a, b). Entao,
peloTeorema2.2 tem7,d | 1. Portanto,d = 1. Arecproca
eimediata.Lema2Sejama, b, c Z. Entaomdc(ac, bc) = |c|mdc(a,
b).Exemplo2.6Sejama, b Z. Semdc(a, b) = 1,mostrarquemdc(a, b) = (a
+ b, a b) = 1ou2.SolucaoSed = mdc(a + b, a b),entaoa | (a + b)ed |
(a b). Considerex = y= 1noTeorema2.2 tem7eassim,d | 2aed | 2b.
Logo,d mdc(2a, 2b) = 2mdc(a, b) = 2.Portanto,d = 2oud = 1.ofatodec
| abnaoimplicaquec | aouc | b. Paravericar,vejaque6 | 3 4onde,6 3e6
4.Mas,valenoseguintecaso:Armacao: Sejama, b, c Z. Sec | abemdc(a,
c) = 1,entaoc | b.ProvaSemdc(a, c) = 1,entaoexistemx, y Ztaisqueax
+ cy= 1.Assim,abx + bcy= b.Comoc | abec | c,tem-sequec | (abx +
bcy),isto e,c | b.Lema3Sejama, b, c Z. Sea = qb + r,onde0 r <
b,entaomdc(a, b) = mdc(b, r).ProvaSuponhaquemdc(a, b) = d. Entaod |
aed | b =) =d | r.Sec | bec | r,entaoc | a. Assim,c | aec | b.
Logo,c | d,Portanto,d = mdc(b,
r).OTeorema2.4mostraaexistenciadomdc(a,
b)enaomostracomoencontrarovalor.ParadeterminaromaximodivisorcomumentredoisinteirosaebeutilizadooAlgoritmodeEuclides.Supondoquea
b > 0,poismdc(a, b) = mdc(|a|, |b|). Entaoexistemq1, r1
Ztaisquea = q1b + r1, onde0 r1< b.Ser1= 0,entaob | aemdc(a, b) =
b. Ser1 = 0,entaoexistemq2, r2 Ztaisqueb = q2r1 + r2, onde0 r2<
r1.Captulo2. TeoriadosN umeros 19Ser2= 0,entaor1 | bemdc(a, b) =
mdc(b, r1) = r1. Ser2 = 0,entaoexistemq3, r3 Ztaisquer1= q3r2 + r3,
onde0 r3< r2e assim por diante ate que algum resto seja nulo,
isto e, rn+1 = 0. Obtendo assim as seguintesrela coes:a =q1b + r1,
onde 0 r1< bb =q2r1 + r2, onde 0 r2< r1r1=q3r2 + r3, onde 0
r3< r2......rn2=qnrn1 + rn, onde 0 rn<
rn1rn1=qn+1rn.Portanto, mdc(a, b)=mdc(b, r1)=mdc(r1, r2)= =mdc(rn1,
rn)=rn. Estasrela coespodemserrepresentadaspelaTabela2.1.q1q2q3
qnqn+1a b r1r2 rn1rnr1r2r3 rn0Tabela2.1:
AlgoritmodeEuclidesExemplo2.7Determinaromaximodivisorcomumentre21e35.Solu
c ao1 1 235 21 14 714 7 0(2.4)Assim,mdc(35, 21) =
7.Observacao2.2OAlgoritmodeEuclidestambemeutilizadopararepresentaromdc(a,
b)naformaax + by. Observequedapen ultimaequacaotem-sern= rn1(qn) +
rn2.Substituindoorestorn1daequacaoanterior,obtem-sern= rn3(qn) +
(1qnqn1)rn2.Comesseprocedimentosaoeliminadossucessivamenteosrestosrn1,
rn2, , r2, r1ernedeterminadoemtermosdeaeb,istoe,encontra-sex, y
Ztaisquemdc(a, b) = ax + by.Captulo2. TeoriadosN umeros
20Exemplo2.8Determinarx, y Ztaisquemdc(35, 21) = 35x + 21y. Solu c
aoPelaEquacao2.4,7 = 1 21 14= (1 35 14) 14= 1 35 2 14.Assim,7 =
35(1) + 21(2). Portanto,x = 1,y= 2e35x + 21y = 7 (2.5)AEqua
caoAlgebrica2.5comcoecientesinteirosedenominadadeEqua
caoDiofantinasesuassolu coessaon umerosinteirosouracionais.2.3
EquacaoDiofantinaDiofantoviveunoseculoIIIemAlexandria,
sobodomniodeRoma. Foi o unicoma-tematico de renome na Grecia antiga
que se dedicou `a teoria dos n umeros. Diofanto tratou
al-gebricamente a teoria dos n umeros, enquanto os
predecessoresutilizaram metodos algebricosparadeduzirsuasarma
coes.Asequa coesDiofantinasdasquais ededicadoestase caosaodaformaax
+ by= n,ondea, bensaointeiros.Teorema2.6Aequacaoax + by=
nadmitesolucaose,esomentese,mdc(a, b) | n.Prova Suponhaqueaequa
caoadmitaumasolu caox0, y0,ondeax0 +by0= n. Comomdc(a,
b)divideaeb,tem-sequemdc(a, b)divideax0 + by0= n. Suponhaquemdc(a,
b) | n. Entaoexisteuminteiroctal quen=c mdc(a,
b).Comoexisteminteirosm0en0taisqueam0 + bn0= mdc(a, b),tem-sequen =
c mdc(a, b) = a(c m0) + b(c n0). Assim,osinteirosx0= c m0ey0 = c
n0saoumasolu caodaequa cao.Teorema2.7Sejax0,
y0umasolucaoparticulardaequacaoax + by=n. Entao, x,
yesolucaodaequacaose,esomentese,x = x0 + t bmdc(a, b)e y= y0t
amdc(a, b),paraalgumtemZ.Captulo2. TeoriadosN umeros
21Exemplo2.9Aequacao9x + 12y= 1naoadmitesolucao,poismdc(12, 9) =
3e3 1.Exemplo2.10Determinarasolucaodaequacao28x + 90y= 22.Solu c
aoCalculandoomdc(90, 28):3 4 1 290 28 6 4 26 4 2 0Assim,mdc(90, 28)
= 2. Como2 | 22,aequacaotemsolucoes. Alemdisso,2 = 1 6 4= 1 6 (28 4
6)= 28 +5 6)= 28 + 5 (90 3 28)= 16 28 + 5 90Assim,(16) 28 + 5 90 =
2. Paraobtern = 22,bastamultiplicaraequacaopor11elogo28 (176) + 90
(55) = 22Portanto,umasolucaoparticulare(x0, y0) = (176,
55)eumasolucaogeralex = 176 + t 45 e y= 55 t 14, t
Z.Exemplo2.11EmumalojadoisprodutoscustamR$71, 00eR$83,
00,respectivamente.QualquantidadeinteiradeambospodemsercompradascomR$1670,
00?SolucaoResolveroproblema eencontrarsolu caopositivaparaequa
caoDiofantina71x + 83y = 1670.1 5 183 71 12 11 112 11 1
0Assim,mdc(83, 71) = 1eaequa caotemsolu coes.1 = 1 12 11= 1 12 (71
5 12)= 6 12 71)= 6(83 71) 71)= 6 83 7 71.Logo,71 (7) + 83 6 = 1.
Multiplicandoaequa caopor1670, tem-se71 (11690) + 83 (10020) =
1670e(x, y) = (11690, 10020).Comoassolu coesprocuradassaointeiras.
Considereasolu caogeralx = 11690 + t 83 > 0 e y= 10020 t 71.0 t
> 140, 84 e t < 141, 13.Logo, t = 141 fornece as solu coes
(x, y) = (13, 9) que sao inteiras. Portanto, pode-se
comprar13e9decadaproduto,respectivamente.Captulo2. TeoriadosN
umeros 222.4 N umerosPrimosUmn umeroP Z
edenominadoprimoseasseguintesarma coessaosatisfeitas:1.
pnaoinversvel (p = 1);2. Sep = ab,ondea, b Z,entaoa = 1oub = 1.Umn
umeron Z edenominadocompostoseasseguintescondi
coessaosatisfeitas:1. n enaoinversvel (p = 1);2. Sep = ab,ondea, b
Z,entaoa = 1oub = 1.Como p eprimose,esomentese,p eprimo,asinvestiga
coesseraorestritasaosprimospositivos. Porexemplo, 2, 3, 5, 7, 11,
13e17saoosprimeirosn umerosprimos,enquanto4, 6, 8, 9, 10, 12,
14e15saoosprimeiroscompostos.Teorema2.8Sea Z,com |a| >
1,entaoexisteumn umeroprimopquedividea.Prova. Supondoquea >
1,poissea < 1,entao a > 1. SejaX= {a N | a > 1eq a,qprimo
}.EntaoX= , nocasocontrario, Xcontemummenorelementod>0. Comod
|d, tem-sequednaopodeserumn umeroprimo. Logo, d=bccom1 1umn
umerocomposto. Entaoacontemumdivisorprimoptal quep
_|a|.Teorema2.11(Teoremafundamental daAritmetica) Dado um inteiro
positivo n > 1pode-seseescrever,demodo
unico,amenosdaordemdosfatores,naforman =
pe11pe22...pekk,ondeospisaoprimos distintosepositivos p1 p2 ...
pkeoseisaointeirose1, e2, ..., ek.Captulo2. TeoriadosN umeros
23Lema4Se p e um n umero primo e p|p1p2...pn, onde p1, p2, ...,
pnsao n umeros primos, entaop = piparaalgumi = 1, 2, ...,
n.Ademonstra caoaseguirtemduaspartes:
aprimeiramostraqueexistefatora caoemn
umerosprimos,easegundamostraaunicidadedafatora c ao.Prova:(1)
Existencia: Suponhaa nega cao da tese,ou seja, que existepelomenos
um inteiromaiordoque1quenaopossaser representadopor fatoresprimos.
SejaAoconjuntodetodosessesn umeros. ComoAeumsubconjuntodosinteiros,
peloPrincpiodaBoaOrdena caoexisteumelementomnimo.
Sejaxesseelemento. Comox emaiordoque2(jaque2eprimo, etemfatora
caoemfatoresprimos), tem-sequeexistemaeb,taisquex=ab,
coma1eexisteumn umeroptal quep|b. Claramente,p b 2,existeumn
umeroptalquep > a. Portanto,p = pi, = 1, 2, ..., m,oque
eumacontradi cao.Captulo 3AritmeticaModularNeste captulo sao
estudadasum instrumentorelacionado ao restona divisao
Euclidiana,ascongruencias.
AteoriadaAritmeticaModularouCongruenciasforamextensivamenteestudadas
por Gauss napublica cao: Disquisitiones Arithmeticae, 1801. As no
coes e asnota coesutilizadasporGaussna
epocaaindasaoasmesmasutilizadasatualmente.3.1 CongruenciasSejama, b
Zen N.
Diz-sequeaebsaocongruentesmodulonseosrestosdeaebquandodivididopornforemiguais.
Seaebsaocongruentesmodulon,escreve-sea b modn.Exemplo3.112 37 mod5.
Pois,12 = 2 5 + 2e37 = 7 5 + 2.Exemplo3.215 1 mod4. Pois,15 = 3 4 +
3e 1 = 1 4 + 3.Exemplo3.3Noteque94 1 mod5. Pois,sea 0 modn,entaoa =
n ke941 = (921)(92+ 1) = 80 82 = 5 16 82.Teorema3.1Sejama, b Zen N.
Entao, a b modnse, esomentese, ndividea b.Prova. () Se a, b Z,
entao existem r, q1e q2tais que a = n q1+r e b = n q2+r. Assim,(a
b) =n(q1q2). Logo,n | (a b).()Supondoquen | (a b).
PeladivisaoEuclidiana,tem-sequea = n q1 + r1eb = n q2 + r2, com0 r1
ne0 r2 n.25Captulo3. AritmeticaModular 26Assim,(a b) =n(q1q2) +
(r1r2).Comon |n(q1 q2), tem-sequen |(r1 r2). Logo, r1=r2, pois |r1
r2| 1ek 1. Entaoas condicoes seguintes saosatisfeitas:1. a a
modn;2. a b modn b a modn;3. a b modneb c modn a c modn;4. a b
modnec d modn (a + c) (b + d) modn;5. a b modnec d modn a c b d
modn;6. a b modn ak bkmodn.Prova. 1. Comom | 0 = a a,tem-sequea a
modn;2. Sea b modn,entaom | (a b) = (b a). Assim,m | (b a)eb a
modn;3. Sea b modneb c modn,entaom | (a b)em | (b c). Assim,m | (a
b + b c) = (a c).Logoa c modn;4. Sea b modnec d modn,entaom | (a
b)em | (c d). Assim,m | (a b + c d) = [(a + c) (b + d)].Logo(a + c)
(b + d) modn;5. Sea b modnec d modn,entaom | (a b)em | (c d).
Comoac bd = ac ad + da bd = d(a b) + a(c d),tem-sequem | ac bd.
Logoac bd modn;6. Ficaparaoleitormostrar!Exemplo3.4Determinar
orestodadivisaode230por 17utilizandoas propriedades decongruencia.
Observeque24 1 mod17.Elevandoambososmembrosdaigualdadea7,temse228 1
mod17Captulo3. AritmeticaModular 27emultiplicandopor4,obtem-se230 4
mod17.Como 4 13 mod17,tem-se,peloTeorema3.2,230 13
mod17.Logo,orestodadivisaode230por17e13.3.2
CriteriosdeDivisibilidadeNesta sao utilizados os conceitos e
propriedades das congruencias para denir os
principaiscriteriosdedivisibilidadeemostrarummodeloparadenirosdemaiscriterios.DivisibilidadePor2,5e10.
Observeque10 0 mod2 =10i 0 mod2 i N.Alemdisso,umn umeronabase10
erepresentadopora = a0 + a1 10 + a2 102+ . . . + an1 10n1+ an
10n.Assim,a edivisvel por2se,esomentese,a a0mod2,pois1 1 mod2 a0
a0mod210 0 mod2 a1 10 a1mod2102 0 mod2 a2 102 a2mod2.........10n 0
mod2 an 10n anmod2a = a0 + . . . + an 10n a0 + +
an.DivisibilidadePor3e9. Observeque10 1 mod3 =10i 1 mod3 i
N.Assim,1 1 mod3 a0 a0mod310 1 mod3 a1 10 a1mod3102 1 mod3 a2 102
a3mod2.........10n 1 mod3 an 10n anmod3a = a0 + . . . + an 10n a0 +
+ an.Analogamentepara9.Comoexercciofa capara7e11.Captulo3.
AritmeticaModular 283.3 ClassesResiduaisUm inteiro n > 1
determina uma Classe Residual modulo n do elemento a em Z e a
classedoa eoconjuntoa = {x Z | x a modn}.Exemplo3.5Sen = 3,entao0 =
{3 | Z}1 = {3 + 1 | Z}2 = {3 + 2 | Z}ea =___0, seaem ultiplode31,
seatemresto1quandodivididopor32,
seatemresto2quandodivididopor3Observealgumaspropriedadesdasclassesresiduais:Proposicao1Sejan
> 1uminteiro. Entao1. a = bse,esomentese,a b modn;2. Sea
b = ,entaoa = b;3._aZa =Z.Uminteiroqualquerbtalqueb = a
edenominadorepresentantedaclasseresiduala.Exemplo3.6 1. Sen=2,
entaouminteiroparerepresentantedaclassedo0euminteiro
mparerepresentantedaclassedo1;2. Se n =3, entaoos m ultiplos de 3
sao representante da classe do0. Os inteiros. . . , 11, 8, 5, 2, 1,
4, 7, 10, . . . saorepresentantedaclassedo1eos in-teiros. . .
,10,7,4,1, 2, 5, 8, 11, . . .saorepresentantedaclassedo2.3. Sen =
4,entaoexistemquatroclasses. Asaber:___0 = {. . . , 8, 4, 0, 4, 8,
. . .}1 = {. . . , 7, 3, 1, 5, 9, . . .}2 = {. . . , 6, 2, 2, 6,
10, . . .}3 = {. . . , 5, 1, 3, 7, 11, . . .}.Proposicao2Para cada
a Z existe um e somente um r Z com 0 r < n tal que a =
r.Captulo3. AritmeticaModular 29Prova. Sejaa Z.
peladivisaoEuclidianaexisteum unicointeirorcom0 r < ntal quea =
n q + rparaalgumq Z. Portanto,reo unicointeirotalque0 r< nea r
modn,ouseja,a = rCorolario3.1Existem exatamente n classes residuais
modulo n distintas, a saber 0, 1, . . . , m1.Umconjunto {a1, a2, .
. . , am}echamadodesistemacompletoderesduomodulonseparatodoa
Zexistirumicomi = 0, 1, . . . , mtalquea = aimodn.O conjunto de
todas as classes residuais modulo n e representado por Zn, onde
Znpossuinelementos representados por0, 1, . . . , m1.
naclasseresidual acongruenciaa bmodn esubstitudapelaigualdadea =
b.Asopera coesemZnsaodenidaspor:Adicao: a + b = a +
b;Multiplicacao: a b = a b.PropriedadesOperatorias:Paratodosa, b, c
Zn,tem-seA1(Associativa)(a + b) + c = a + (b + c);A2(Comutativa)a +
b = b + a;A3(ElementoNeutro)a + 0 = 0 + a = aparatodo a
Zn;A3(ElementoSimetrico)a + (a) = (a) + a = 0paratodoa
Zn;M1(Associativa)(a b) c = a (b c);M2(Comutativa)a b = b
a;M3(Unidade)a 1 = 1 a = a;AM(Distributiva)a (b + c) = a b + a
c.Exemplo3.7 1. AstabelasdaadicaoemultiplicacaoemZ2= {0, 1}sao:+ 0
10 0 11 1 0 0 10 0 01 0 12. AstabelasdaadicaoemultiplicacaoemZ3=
{0, 1, 2}sao:+ 0 1 20 0 1 21 1 2 02 2 0 1 0 1 20 0 0 01 0 1 22 0 2
1Captulo3. AritmeticaModular 303. Astabelasdaadicaoemultiplica
caoemZ4= {0, 1, 2, 3}sao:+ 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 3 0
1 2 0 1 2 30 0 0 0 01 0 1 2 32 0 2 1 23 0 3 2
1Proposicao3Umelementoa Zeinversvelse,esomentese,mdc(a, n) =
1.Prova. Sea einversvel, entaoexisteb Ztalque1 = a b = a + b.
Assim, a b = 1modn,istoe,existeuminteirottalquea b + t n = 1.
Logo,mdc(a, n) = 1. Semdc(a, n) = 1,entaoexisteminteirosbettaisquea
b + n t = 1eassim1 = a b + n t = a b + n t = a b + 0 = a
b.Portanto,a einversvel.3.4
AplicacaoCriptossistemasUmcriptossistemaeumabije
caodePemCcomaestruturaf f1P C POProcessodecodica cao edenidopelafun
caof: P Ctalquef(u) = c;OProcessodedecodica caoedenidoporf1: C
Ptalquef1(c) = u;RepresentandoossmbolosdoalfabetoporelementosdeZ27.
Tem-se:F A B C D E F G H I J K L MZ 0 1 2 3 4 5 6 7 8 9 10 11 12N O
P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25 26Teorema3.3Sejan Nea,b
Zxados. Semdc(a, n) = 1,entaoafuncaof: Zn ZnCaptulo3.
AritmeticaModular 31dadaporf(x) = ax + beumcriptosistema.Prova:
Comomdc(a, n) = 1. tem-sequeexistea= a1 Zntalquea a1= 1. Assimf1(x)
= ax + b,ondeb= ab,talquef f1= f1 f=
I,comf1ainversadef.Nocriptossistemaf(x) = ax + bopar(a, b)
edenominadochavedecodica cao.AplicacaoSejaosmbolox
Z27correspondendoaumamensagemdeblocos,ondea = 2,b = 1,eafun caof:
Z27 Z27,ondef(x) = 2x +
1eumcriptossistema.Codicandoamensagem:medalhadeouroCalculando:f(12)
= 25, f(4) = 9, f(3) = 7, f(0) = 1, f(11) = 23, f(7) = 15,f(0) = 1,
f(26) = 26, f(3) = 7, f(4) = 9, f(26) = 26, f(14) = 2,f(20) = 14,
f(17) = 18, e f(20) =
14.Amensagemcifrada:ZJHBXPBHJCOSCParadecodicarutiliza-seafun
caoinversa.Assim,f1(x) = 14x 14;f1(25) = 12, f1(7) = 3, f1(1) = 0,
f1(23) = 11, f1(15) = 7,f1(1) = 0, f1(26) = 26, f1(7) = 3, f1(9) =
4, f1(26) = 26,f1(2) = 14, f1(14) = 20, f1(18) = 17 e f1(2) =
14.Amensagemoriginal:Captulo3. AritmeticaModular
32medalhadeouroMensagensemblocoaplicandovetores.X= (aij)21=_xy_
Z226Paran NeD = ad cb Z. Semdc(n, D) = 1,entaoafun cao,f: Z2n
Z2ndenidaporf(X) = AX + B,A =_a bc d_ M2Zn, B=_ef_ Z2neX=_xy_
Z2eumcriptossistemaAs matrizes sao mensagens unitaria com blocos de
dois smbolos, onde x ey Z26 Assim,A =_1 26 7_ M2(Z26)e B=_610_
Z2nParacodicarotexto,AIConsidereovetorX=_08_ Z226.f(X) =_1 26
7__08_+_610_=_2212_=_WM_Amensagemcifrada eWMBibliograa[1] ARRUDA,
Rafael Lucas de. Introducao`ateoriadosn umeroscomaplicacoes
emcripto-graa.UNESP,SaoJosedoRioPreto,SaoPaulo2006.[2]
Hefez,A.CursodeAlgebra.V.1,ed.2.RiodeJaneiro,1997.[3] Silva,A.A.N
umeros,RelacoeseCriptograa. DMAT-UFPB,JoaoPessoa,1999.[4] SILVA,
ElenV. P. da.
Introducao`acriptograaRSA.2006.Monograa-FaculdadedeEngenhariadeIlhaSolteira-FEIS,SaoPaulo,2006.33
