trllatemticas dtscreas

nnmruESPTNoSAARMENTA

AAHaomega

68

II.

TEoRiADENMERos

d a Sean y b dos.entercspositivos,y sea ]a conbinacin lineal Teorm*2.7 b). positiva mnima de a y b. Entohcesd = mcd.(a, Demosasin Sead = tzx + y la co[inacin linea] positiva mnima de a y b. Por eI algorilmo de la division :

e
\r' Eucldes
(33G275a.c) t"-" a" Eucliales se clgbe a su L, monumental obra Elell,letos qu6 conBta de 13libos gu contieaenios fudahen' hasta se tog y todo el sale mai,smtico tiepo. Apart de su cotonido, la estructua lgica de esta obra ha irlluido n el pensamiontomatemicoy cientfi_ co ms clugninguraotra. Especiccamenteel contedo de los nementoa es el qiguiente: libros 1 a 4, geomeia plana: Iibos 5 a 10, fazonesy prcporcioDesibos 11 a 13, geomtia de slidos. En relacincon la teotia de nmero6, en eI libro 7 se uatan los teoas d di visjbilidad, rneros prios, algoltroo de Euclides, mximo comn divisor y minimo comn mL tiplo, adeEs de gue las proposiciores 30 y 32 juntas son esoncialmente equlvalentes ai teolema fundamental de Ia aritmhca; en el lrbro I se presentael tema ds las proporcons etr teoria da ml.Be' ros; ialrie etr el libro 9 se deqtueslra la oxistncia de ilidad de ilnros P!imos (proposicl 20) y se ltrantea l,aconstucc$D d lc,snt!e. ros pefectos pat98 (proposici36). ATFAOMEGA

a = d q +r Porlo tanto

9on

03r<d'

r = a - dq = a - lax + by)q= (l - xq)a+ (-qy)b line de a y b. No puedeser gue 0 < r, ya De aqu que r es una combinacin gue d divid a a. En forma = Ocon Io cual se concluye gue r < d, por Io tanto r puedever que d drvldea b, por lo tanto d es un divisocomnde se anIoga ahoraque c es otro divisorcomnde a y . Seobseryaque a y ,. supngase lineal de 4 y r)' de ah que c esmenor c divide a d (puesd es ua combinacin o igual a d.

paradetermnar mximocomn el un El siguienteteoremadescribe procedimiento divisor de dos enterosPosltvos. positivos 4 Teorena 2.8 (Agoritmo de Eucld6sl. Sean y b dos entercs el repetidamente algo' queq> b Sedefinen16=ayrt = b, y aplicando tales ritmo de la divisin se obtiene
t'o= rtQl'l rz rt = rzq|+ 13
O<r2111

o<7<rz
Q < rn< rn-1 0 = rn+r "+l

* '^ i,-r=,,--,n^-,
rn) = rnqn+ t

mcd(4,b) = rn,estoes, el riJtimoesiduo es distinto de cero. Entonces

DscRETAs RAMNEsrINosAABMENTA MArEMTrcAs

2.5 MxrMo coMN DrvrsoR

Demostracin Pdmero se demuesta que mcd(rj, ri+t) = mcd(rj+r'rj+2) para todaj= 0, l, ..., n - 1. Seac un divisor comn de r v j + L Como rj= rj+t4j+t ri*z * se sigue que l+2 = rj - rj+gj+t, y de aqu que c divide a rj+z.por 10tanto c es un divisor.comn de r+ty rj+2.Anlogamente,todo divisor comn de r1 V ,12 es un divsor comn de rj y r,+r,con Io cual se concluye que /lcnf(r,,ru,) = ntcd(r*1,r+).Por Io tanto ncd(a, b) = ntcd(ro. r1) = mccl(r., r) = .., = tncd(t 0\ = r,1. ,,.

69

Ejemplo 2,16 Determinar el.mximocomndivisorde 126 v 78. Solucin Aplicandoel algoritmode Euclidesse obtieneque 12=78(l)+48 78=48(l)+30 48=30(l)+18. 30=18(l)+12 1 8 =1 2 ( l ) + 6 tz= 6(2) Porlo fanto mcd(12, = 6. 78)

El lgoritmo Euclidedtambien puedeutilizarseparaexpresar maxrmo de el comun dilisor de dos nmeroscomocombinacin titeal de eos,comose muestraen el sr!luiente ejemplo.

E 6mplo 2,17 Expresar el mximo comn divisor de 126y 78 como combinacin lineal de dichos nmeros. Solucn A partir del ejempio aterior se tiene que

Merrcs DIscFETAs RAMNEspNosA ARMENTA

ALFAOMEGA

70

II.

Tsonre o l,,rulu{snos

que Eemplo2,la Mostrar r?d(5 n+3,3n+ 2)= l,pracualquir numeronatural?. Solucln Aplicandoel algoritmode Euclidesse tiene gue + 5n + 3 = (3n+ 2)(1) (2n+ ll l 3n-2=(2n+xlr+(r+ l) 2r+1=(n+lXl)+n r+l=r(l)+t n = t(n) Porlo tanto el mcd(5tt+ 3,3tt + 7) = \,

Dlofanto
f:r lln su obra,Ari,'rorca constba {que d 13 liros de los cualegsose coservan 6), Diofato expoo ls 6madas ecuacioros auofatLnas; eje@plos de stas on las sioulentes: , ar].b!=l . /'+l'=1 (ocuacin lin.I diofantina) (paran=2sotireel teoremade Pitgoar ypaan>2eltimo teoromade Fetmat) (cuac,in P) ds
(2O{}284)

Dados dos enteros positivos 4 y , el propstogeneral del simulador MAXIMOCOMUN DIVISOR el el es determnar nxcdde stos utilizando algoritmode Euclides expuestoen esta seccn.

. t - y'= il

4 1 1 1 ( l a c o n j e n ud E r . -=:+:+: a n x Y z ds'straus establoce gue para todo enteo positivo n > 2 erists unasolucin con, ), posr_ z lodos enrcro9 [rvosJ Un hechosencilloy sin ebargo scendentes que en 1637Fermatesc!i sn el magen de su copia de A'jtlrecalo gue se conoce comoel ltimoteoread Fermat, qlre en trmios modertroi dice Si x es un nmeroenieomayorque ente_ no 2, entoncs existennmeros rosd,ycdjstitos de 0 tales que cumplan Ia igualdad

Torema 2,9 alr. Demostracin

Seana, b yc tes enteros.Simcd(a,b)= | ya]bc, entonces

Si ncd(a, b) = I entonces existen x, ) enteros, tales que ax+b!=1

de aqu que a(xc)+(bc)J=c Es decir, c es combinacinlinea.lde a y bc. Como a I a y a I lt. se sigue que ? .. ) Dos enteos ry se dice que son primos relativos si r,?cd(4, - 1. g1 resultado anterior es falso si a y no son primos relativos, por ejemplo, 6 divide a 2(9) pero noa2,y6nodivdea9. En el siglo UI d. C., et matemtico gdego Diofanto consider el problema de obtener soluciones entefas de ecuacionescon coeficientes enteros. Este tipo de ecuaclones son conocidas en la actualidad como ecuaciones diofantinas. El signrienieteorema esta.bleceuna condicin necesada y suficiente para que una ecuacin lineal dio' fatina en dos variabies tenga solucin.
MATEMTIcAs DIscBETAs - RAMN EsPtNosA ARMENTA

Etn espciallosesfuBrsst6 zospor clemost'af teorema esltruaron el deEatollo Ia!60de rfa de los nmeroF algbaicos,

ALFAOMEGA

2.5 MxrMo coMN DrvrsoR Teorema 2.lO Sean y b d.os a entercsno ambos cerc,y sea = mcd.(a, d b). qx ).a,lcuacin + by = c tiene sotuciones entens siy slo siil. \n::!y: st d. y = Aaemas I c x xo,y = yo es una solucin pafiicu)ar de la ecuacion,en_ tonces todas las solucionesestn dadaspor x = xo+ (btd)n donde n es malquier nmeroenterc, Demostracin Seanx, y dos enterostales gue ax + by = c. eomo d a y I que d I c. por Io tanto,para gue la ecuacin d l, se signre tenga solucrones enterases necesario que d divida a c. Supngase ahoraque d I c, es decir, c = dq para algnrn enteroq. Como = tncd(4, se sigxe d rcorema2.7que d. ), exstenenteross,, tales que d = as + t, de aqu que c = dq = asq+ btq, por lo tanto r0 = sq y yo = t4 es una solucin particular de l ecuacin. Sean x = xo+ (bld)n,y = yo- @/d)n, donden es un nmeroentero.por lo tano ax + by = oco+ a(bln + by- b(ald)n= al!+.bys= Ahora se ver gue toda solucinde la ecuacin debeser de la forma descfita en el teorema. Seanr, y dos enteros tales gue 4.r + ) = c. Comotambin axo+ byo= c, se sguegue y = yo_ @td)n

7t

a(x-x+b6/-yd=0
y de agu gue (a/d)(x- xg = (b/d)(y- y) Qomomcd(ald, b/d) = 1 1y6u""problema2.29),se signe Ia proposicin de antedor gue rad)l\o - y) por lo tanto existeu entero tal que -, = n(a/d),y de aquise sigxe que 0/0 y = yo- @ld)n.Sustituyendo la ecuacin tiene que en se (a/d)(x.- xg = (b/d)n(atd) Porlo tanto (r -,r0) = (bld)n,es deci, x = xo+(b/d)n.

E omFlo 2.19
toJx+ lAYy=99
MA?EMTCAS DIscRETAs- RAN EspINosA ARMENTA

ALFAOMEGA

72

II.

TEORTA NUMERoS DE

Solucln .B;UClres: + 765=.189(4) 9 189=9(21)+0 = tiene. Por 10tanto d = mcd(765,189) 9. como d i 99, Ia ecuacin = como765- 4(189) 9 se tiene que 765(11)'+ Adems, solucin. =99, de modoque;6 = 11,yo= -44 st una solucinpar189(-44) de tisutar.Adems,por el teoremaarterior,todaslas soluciones la son de la forma: ecuacin x=11+ZLn J=44-85n

Hllberty la teora oe numeros

T:T -l matematico alemn Davicl Hiliren es 11862"1943) considerado uno de los matemticos ms imponantes dg toalos Ios tiempos debido aI descubimionto y desarrollo de muchas ideas fundamentalss n varias reas de la nataDtca,en particular formul la teola de los espa' cios de Hilbert (uno d6 los fuDdaentos d6l anlisis funcional), acept y dofendi co$ vehemencla la teoria de conjunts y los nmeros iransffrtosde Geotg Centor, y en el congEesode atemticos d6 1900 present una colecci da problemas que de6i el cuso de Ia mayo patte de la iwestigacin matrtic dgl slglo xx. En la ieoia de nmeros Hilbert unic el campo de la teoia de nmeros lge_ braicos con sn ttado Zanbeticht do 1897 y resoiri el Uardo problema de Wairg. ''Problema de WaJing. Determiar si para n entero positivo k, existe ulnte. ro s (que depnda slo de ) tal que la

En general, una ecuacin diofantina es una ecuacin de Ia forma D(xr,...,,,) donde D es un polinomio con coeficientes enteros. En 1900 el matemtico alemn David Hilberi present una lista de 23 problemas que consideraba cruciales para el desaollo de las matemticas deLsiglo xx, en particular el problema 10 consista en disear un mlodo para determinar en un nmero flnito de pasos si una ecuacin diofantina tiene soluciones enteras o no. Finalmente, en 1970 se demosir que tal mtodo no existe. En la lectura adicional

DE LOSPFOBLEMAS HILBEFT por propuestos esteclebre de algunos losproblemas se describen de Internacional MatemtiCongreso matemtico el Segundo en cos.

tenga soluciones para cada, > L El poblema se conoce con e] nomre del matemtico rngls E. Wang qu esta' bleci en 17?0 (sin demosacin y con limiiada evidencia numrica) que cada s la suma de 4 cuadrados, d6 I cubos, de '19 cualtas potnclas, etctfa"4.

Por otro lado, es posible extender la definlcin de mximo comn divisor de la si > guiente manera: si {a 1,42.. . ., a,,} es un conjuntode enteros'donde 1 3, entonces se comn divisor de a. a2, ..., .J,, def,ne como el mximo
mcd(a1, a2, . . ., an) = nlcd(at, mcd(u ct2,. .., a "))

Porejemplo:
mcd(6, 1. 12) = ncd(6, ttcd(4, l2)) = ncd(6, 4) = 2

4 Tom M. Aposroti Ito(luc.tiotl to analytic numbe rreoyi Springer Verlag, New York 1976i p. 306. MATEMTrcAs DscRETAs- RAMN ESPINoSAABMENTA

ALFAOMEGA

2.11

PRoBLEMAS

91

.;t:,ii

2.24 Resolver el problema anteior utilizando el simulador

2.26 Resoiver el problema anterior utilizando el simularior MAXIMO COMI'N DIVISOR

2.27 ::

M e r e r rn s D t s c n . r sl R r N a o N s p r N o s A M E N - A E AR

ALIAOMEGA

92

IL

TEoniADENMERos

2.35 Resolver el problema anterior utilizando ei simulador

2:36 Determinrel mximocomndivisode 156,39, -104, :108.

2.37 Resolver el problema antedor utilizando el simulador MAXIMO COMUN DTVISOR

ALFAOMEGA

2.11

PRoBTEMAs

93

a\ 693 c't 1925

::

'1"

2.45 2.46 2.4? 2.48

nxcm(q, b).

2.49 s i = 2 s . 5 r ' 1 3 1 ncn(a, b).

MATriTrcAs DrscRETAs- RAMN EsplNosA ARMENTA

ALTAOMEGA

76

II.

Tsonin DENMERos donde p, p2,.. ., p, son primos distintos,y 0 < ai,0 < bipan toda.l = l,. .., ,r. Entonces

nlcd(a, = pi" p;''. p':" b)

.y

n t ( n t l o , h \ =p ' , ' p l ' . p ! '

donde r?;= mnimo {a b) y M,= miy..noIoj, b) conj = 1, ..., /r. Por Io tanto t,t,dra.btnrcntta.ht= p; l p pi' f! ,"

,,. = pM pr.+M. p,+M, = pi.h' p:'+b' " p::-b'

= Pi" " pi pi p';'" ' P'"' p';'

2.1
En 1801 el matemtico alemn Carl Gauss introdujo la nocin de congruencia, la cual permiti obtener fcilmente resultados relacionados con la divisibilidad.

I c

Cal Fneich Gauss es considerado "el prjncipe de las ma!emiicas asi como "ei oatemico rs nand6 desde la atigedad". Adems de ser un no prodigio, Gauss hizo iportantos contjbucioDesen las ras d la teoria de nmelos, la estadstca, el aDlisis,la geomtia diferencial, la geodesia, la geoflsica la electrostiica, la En relacin con la leoria de nmeros, en 1798 tmin de escrib Disgutsitjones Aitmeice que consolid y defini Ias lineas de desarrollo modenas de esta ea. En trmios geDerales,en esta obra Gauss ee y organiza los resultados de la teoria de nmeros obtenidos por Fermai, Euler, Lagrage y Legene, presenta la demostracin del teoema fundamental de la aritmtica, hace ua clara exposicin de la arjtmetica modular y expone la prrmer demostacin de la ley de reciFocjdad cuadrtica la cual establec las conaliciones pra la solucin de ecuaciones cuaticas mdu.lo oeos Prmos. En partioa slguiendo esta Lineade r.nvestigacin, en un

T'\ J-,, e ongen alemn

Gaussy la teora ue numeros

f
que es Porejemplo, = l3 (md5) porque13- 3 = 5(2).Considerando n un entero 3 positivoarbitrarioperojo, a continuacin demuestran de se algunaspropiedades las congruencras.
Teorema 2.13 (j) (jt Si a. l, y ( son enteros,entonces

= r (urd i) (rndr?); sr a = b (md r) entonces1,= 7

(iji) sia = (nrd y b = c (md r) entonces = c (d r) r?!) r Demostracin (j) (rl) Como (a - a = 16,se sigue que a = a (md /fl). entonces (b - a) = aq para algn entero 4, y por Io Si a = 1.,(md ??) tanta (a - b) = m(-q), de aqui que D = a (md nr),

(jii) Sin= (md nt) y b=c (ndr?) entoncesexisten enterosqty q2tales que (b - a) = 1qt y (c - b) = tnqz,de aqu que (c - a) = u(qt + q2) y por lotantoa=c(mdm).
MATEMTIcAS DISoRETAS RAMr'i EspNosA ARMEI'ITA

ALFAOMEGA

2.7 CoNcRUENcrAs El signienteresultado muestra que las congmencias compatles con las opeson raconesds suna y multiplicac!n en Z. Teorema 2.74 Si a, b y c sonenterosy a = b (mdm\, entonces li], (ii) (4 + c) = (b + c) (md) ac = (1(i n1.

77

Demostraci Por hiptesis se tiene que existe un entero ?, tal que (b-a)=aq. l (b + c) - (a + c) = (b - a) = mq, ps lo tanto (a + c) = ( + c) (mdm).

(i) bc - ac = clb- a)= m(cq\,es dec ac = Dc(mdm). En general es falso que rna congruencase preserve al divid amboslados po! un entero,por ejemplo,9 = 15 (md6), pero 3 no es congruentecon 5 mdulo6. Sin embargo,el siguiente resultadoproporcionauna condicin sufrcientepara que una congruenciase preserve al dividir entre un ertero.
Teofema 2.15 Si ac = bc (m& m) y d = mcd(c,rn), entoces a= b (md nldl. Demotrasin Se tiene que ac = bc (m6d. ?)impca qle mq = cb - ca = c( - a) paa algrn entero 4, de aqui gue, didiendo entIe d = rncd(c,m) sa tiene gue

(mtd)q=116-o (nl esdec:Lr, | G/d)(b- a). Qomo mcd(nld, = 1,s sigvedetteoema c/d) 2.5 qre (,nld\| ( - a) y por lo tanto a = b (mdmtd).
Cotofarlo 2,1 Si ac = bc (mdm) y mcd.(c,m) I, entonces = a=b(m6dm).

El siguiente resultado muestra que se pueden sumar o multiplicar congruencias.

Teoroma 2,16 Si a = (mdm) y c = d.(m6d, antonces n), (r) (t0

I

(a + c) = (b + A (m6dm)i ac = bd 116 ^.
ALF'AOMEGA

MATrMTtcAs DIscRETAs RAMNEsprNosA ARMENTA

-.ll

78

II.

TEoRiADENMERos

Demostracin Porhiptesisexistenenteosql y 42,tales que (b-a)=nqt (r) (t f @'-c)=vqt

(b + t - @+ c) = (b - a) + (d - c) = rnqt+ mq2=m(q| + 42)y por lo tato (a + c) = (b + d) (m6dm). + bd - ac = bd. bc + bc - ac = b(d - c) + c(b - a) = [q, a mqt= m(bqz c4r) de aqu que 4c =bd (m6dm)'

a^ leorma 2.17 Si a = b (mdrn) entorzces = b" (mdm) pan cualquier enterc Positivon. Demostracin Si n = l, eI resultadoes cierto por hiptesis. es Supngaseque la a-firmacin cierta para /,es decir' a" = b" (md r|1)'como a"a= b"b del se ambin a = (mdm), entonces sigme teoremaanterior qle (m6dm). = (mdr) y de agu gue annt b"*t En el siguienteeiemplose muestracmocalcularel residuoal dividir un lmelo de la forma M", con n g[ande,entre un enteropositivom

Ahora bien

ALFAOMEGA

2.7

CoNGRUENctAs

79

Seaa un enteropositivo,que en baEediez se escribecomo a=arlV+...+a1l0t+a gue l0 = I (md9), se sigue del teoremaanterior que ld = i (md9) Considerando y de agu gue arlO*= ar (md9) para iodo enterono negatvot. por lo tanto, por el toorema2.16resultaque a = (a.+ ... + a + a6)(md9) Esdecir,todo enteropositivo es congruentecon la suma de sus dgitos mdulo nue_ 4217= 14 (md9) y 14= 5 (mod9), de agu que 4217= 5 (mrd9). ve.Poreiemplo, Esta observacinpermite establecerun procedimiento para verificar que la suma o el producto de dos enteros es corecta: sumaf los digitos de los nmeros y efectuar la operacin sobre la suma de los dgitos. Por ejemplo,

2153 x3t4 676042

2+ I + 5+ 3= I l , 2 3+l+4=8, x8 6 + 7+ 6 + 0 + 4 + 2 = 2 5 , 2 + 5 = ' 1 , L 6 l + 6 = 7

Siel producto la suma de los dgdtosno es igual al produsto de la suma de de losdgitosde la respuesta,entoncesel resultadode la multiplicacinno se coecto.
En el siguiente teorema se platean vados restados de divisibdad.

Teorema 2.18 Sia=anlO'+... +a1l0r + ao entonces l, a es visible ene 9, si y slosi an+ ... + a.t+ ao es divisible entre9.

(x) a es diuisible enfe3, siy s\osiq,,+ ... .r a1* d es divisihle entrc3. (ix) a es divisible entre 2, si y s|o si aDes divisible entrc . (jv) a es divisibleentre5, si y sdo si ao= 0 o ao=5. (rr) a es visible enldell, siy s\osiao- at + ... + (-1), a" es divisible
ente ll. Derostraci (t) Se sigue del hecho de que a = (a, + ... + c1 + a) (md 9). ALFAOMEGA

MATEMTCAS DscRETAs- RAMN EsptNosA ABMENTA

80

II.

TEoRiA DENMERos

(it

Como10= I (md3), se sigue que l0* = I (md3) paatodo enterono + nsgativo, de agu que a = (a,r ... + a + a6)(md3).

(ji) Como l0 = 0 (md 2), se sigmecnre ld = 0 (md 2) para todo entero positivo , por lo tanto a= a (md?). (jv) Como l0 = 0 (md 5), se sigue gue ld = 0 (md 5) para todo entero positivof, de agu gue a = c (rnd5). Ademso= 0 (md5), si y slo siao=0oao=5. cuolot = (-1)t (md 11), por lo tanto (v) CoBo l0 = -1 (md I l) se sigrue ( a = ( a - a l l . . . + ( - 1 ) ' a , ) m dl 1 ) .

Lama 2.3 Seana y b dos enteros y m un anterc posivo' Si mcd(a,m) = | entoncesla congzuenclalinea) ax=b(m6dm) ene solucin. Adems,si xs es una solucin particula4 entonces todas lag por solucionesestn d.ad.as x = xo+ mn, donden es uJtenterc afuitario. DmostaciD Satiene gue a = (mdr)6i y 8losi b - ex = my para algn entero y. Esta esuacines eguivaletrte a la eoaqinlineal diofantia ax+my=D ya m) la qualpor el teorema2.10tiene solucin, q:e mcd(a, = 1. Adems,por mismo teorema, las soluciones son de la fofma r = xo+ tnn, y = yo * an, el donde = )fo,y = )0 es una solucin particular y n es sualguernmelo entero. Los valores r = 0 + mrson las solucionesdo la congruencialineal.
ALFAOMEGA
ARMENTA EsPNosA DscRETAs RA.4N MATEMCAS

2.7 CoNcRUENciAs

81

r (moo/). Sofucfn Coo mcd(2,7).1, se siguequela congruencia tiire solucin. particulares.r0 -3. Ademscualquie Unasolucin = otra solucines de Ia formax = -3 + ?n,para alghnteron.

Ejmplo 26

Resover sjstemade congruencias el lineales: x= I (md 3) r=3(md5)

9olucln Parargsolvereste sisteqrase observ4'pnmero gue 4 particularde la primeracongruencia, es una solucin por adems el lemaanrcriortoda solucinde la primeraiongruencialineal es de la forma x=4+3k dondet es un enteroarbitrario.Sustituyendo la segxndaconen gruencia lineal se obtiene gue (4+3k)=3(md5)
y de aqu gue

3e: -l (md5) Una solucinparticular de Ia segundacongruenciaes 3 y cualquier otra solucines de la forma t = 3 + 5n, donde11 cualquierente. es ro. Porlo tantolas soluciones sistemade congruencias del linea]es sonde la forma = 4 + 3(3+ 5)= 13+ l5. n

Eempo 2,27 En ei siglb m d. C,, el matemticochino Sun Zi esqibi el libro Sun Tzu SuangChlng (Manual de Matemticasdel MaestroSun),en dordese presenta frersosproblemasmatemticos.En paticulerel problema dice Io siguiente: 2q perono sesabecuntas Tenemos numerode coss, un son exagtamente.Si las dividimos entre 3 nos sobran 2. Si las dividimos entre 5 nos sobran3. Silas dividimos entre7 nos sobrsn2, Cunta,6 cosastenemos?
l\fATEMATrcAsDrscRETAs- FAMN EsprNosA ARMEN?A

AL'AOMEGA

82

II.

TEoRADENMERos

1, na solucinpartisular d esta congruenca,es ademsde cualquier otra splucin de la forma = 1 + 5t. sustituyndo en la tersera congruencia se obtiene que

Una soucin partiqular de esta congruencia es 1 y cualguieJ otra solucion d.ela + f o r m a ,= 1 + ? t r . P o r l o t a n t o = 8 + 1 5 ( 1 7 n ) = 2 3 + 1 0 5 n .

En los ejemplos anieriores cualesquiera dos mdulos eran primos relativos, Como se ver, sta es una condicin sunciente para que un sistema de congruencias lineales con coecientes unitarios tenga solucin, adems de que cualesquera dos soluciones son congruentes mdulo el producto de los mdulos. Sin embargo, prrmero se reguiere demoslrar el signtiente lema.

son entercs,y b es otrc enterc tal que Lema 2,4 Si my,m2,...,m,. m c d ( m i )= | b, ... entonces mcd(mr2 mt,b) = l.
ALFAOMEGA
MATEMATToAS DISCRETAS RAMN ESPINoSAARMENTA

P a r a t o d a i = 1 , 2 ,..' r

2.7

CoNGRUENCTAS

83

peronjo.ta demostracin hace Demostracn Sea un enteroarbitrarjo, se por induccinsobreel nmerode trminos/. PaIa r = | el resultado se cumple trivialmente. Supngaseahora gue el resultadoes verdaderopara r, y seanrnl, tnz,,.,, m mr+t,enterostales gue b) mcd(mi, = I paraioda i = l, ..., , r + l. Porhiptesisde iduccin se tiene qlJemcd(m1m2... b) = l, por lo tanto existen dos enterosl y 12 tales m,, que
)l1(m1m2... m,) + ^2b = |

Por otra parte, comomcd(nr,+|. = I entonces b) existenenterospl y p2tales que

Irfir+t+lzb=l Multiplicando las dos ecuaciones antedores se obtiene gue ... (1,1(m1n2 n,.) + L2b)(4m, + V2b) | =
na.d,,i rac,,lrr ,

m,.*) + Qm,* ],,2+ ),a(m p2 . . m,)t2+ 7,"2 b = | tlu (m pt2 ... nt,. t2b) ... y, por lo tanto, ,rcd(m1m2 nrnr1,b) = I.

Teorema 2,19 lTeorema chno det reaiduo). Sean m2,..., nr. nxr en= tercspositivostalesque rncd(ntbnt) | pan toda +.j. EntonceseJsjstema de congrue ciaslineales
r = (md ri ) r = D2(rndar2) : x = lt,.(m6d m1) tiene solucin nica mdulo M = mtm2 ,,. nr.

Demostfacin Si r = I el restado se siguedel lema2.3.Supngase ahora que el resultadoes cierto para sistemasconsistentes r congTuencias de Iineales, considrese sistemade r+ I congruencas y un lineales. hiptesis Por de induccin, el subsstemaformado por las primeras r congruencias tiene una solucinpanicular i, ademsde gue cualquierotra solucines de la
MATEMTICAS DscRETAs- RAMoN EspNosA ARMENTA

ALFAOMEGA

84

IL

TBonIADENMBRos forma = i + doade n 6g ut entoro abitraio y a = rlm2.,. m, Qomox taEbi debe satisfacer a r tlma congruslcia, s6 ti6na gue i + an a bn(mda,*) y tt6 aquf que az = (*- i) (md mn*) mn) - | pq lo que, por 61lema Abora bien, por el lsua 2,4 se sabe qus mcd.(a, 2.3,osta co[gruoda dne ua soludo particur't0,ademsde gue cuelquier otfa 60luciDes de la fottta n = zo+ rrNt. 10tanto Por x = i + a(no+ m*tk) = (i + an) + amnlk De agu que todas las solucionesdel sistema de congruenciassoDde liaforma .r = 0 + Mk, dodo M = mtnh ... rrr+ly & es un eotero bitrario,

sl constaba origialEsnte de diez meses EDla aDtigua Roma calendario : o Martius: en boor a Marte. . Aprs: dedicado Venus(Apru oDetrusco). a . Maius: decllcdo Maya,Eadre de Morcurio. a . fuiug: dedicado Juo. a o Quinlis:.el mesquinio. r Sextis: el messexto. . Septamberiel Bas sptimo. . Oc'tabef:el mesoctavo. . Novebe, el megnoveoo. . D66.emben me8daiso, e
I

etr el EstosEessstoDan total 304das,Paacomplota aosolarhabfa61 dias d iviero. En el ao713a. C. ol rey NumaPopiliusaadidosnuevosmssas:
ALFAOMEGA
MATrUTtcA8 DscnETAs- RAUN ESprNosAARMBNTA

94

II.

DE TEoRiA NMERos

2.50 Resolver el problema anierior utilizando el simulador MXIMO COMUN DIVISOR

p'Ia". qe 2.51 Demostrar sip esprimoyP Ia'',entonces

Congruencias
2.52 PaIaqn

253
Calcular el

b) l?.r= 14(md2l)

AI,FAOMEGA

MATEMT1oAsDIscRETAS- RAMoN ESPINoSAARMENTA

2.11

PRoBLEMAS

95

2.64 Resolver siguiete el sistemade congruencias iineales: r = 5 ( m dl l ) r=4(md8).

a) b)

2.66 2.67

perpetuo Calendario
2.68 Calcular el dla de la semana del 30 de abril de 1777 (nacrrniento de Gauss).

2.69 Resolverel problemaanteriorutilizando el simulador CALENDARIO PERPETUO

M A T E r r A T r c A sl s c R T A s- R A M o N E s p t N o s AA R M E N T A D

ALPAOMEGA

4.8

APLTcACToN:cRtprocRAFiA

777

Eemplo 4.39 igma.les. Demotacin observar gue

Comouno de los d.osp meros factres es par ss sigue gue n5- = 0 (md 2), por lo tanto n5- ?= 0 (md l0), lo cual pruebael resultado.

Supngaseque se requiere envia informacin confldencial a travs de cierto canal de comunicacin. Ante el desgo de que la informacin que se envre sea interceptada por otra persona que pueda aprovecharse de sta en nuesiro perjuicio, se han ideado mtodos para tansformar el mensaje original de modo que la informacin que se enve est oculta, y pueda ser encontrada solamente por la persona a la que se quiere enviar el mensaje. La disciplina que estudia estosmtodos se llama criptografia (del gdego kypos, escondido, y gnphein, escribir). EI mensajeque se quiere enviar se llama texto comn, y el mensaje transformado se ilama texto ecriptado o cifrado. Tanto el texto comn como el texto cifrado estn escdtos con smbolos de un alfabeto particular. Al proceso de pasar del texto comn al texto cifrado se Ie Uamaencriptar o codiicar, y ai proceso de pasar de teo cifrado al texto original se le llama desencriptar o descifrar,

i',
t,.l

tl

#.

g
B!,

B s,
F;

que Ejenrplo 4.O En Ios mensajes Julio Csarenviabaa sustropas,cadaietra por del alfabetose reemplazaba la letra que se encontraba tres posciones despus,suponiendo stasestaban un crculo,de modoqueA sequiadespus que en de Ia Z. Porejemplo,Ia palabraATAOUENse convertaen DWDTXHO. pensaSi mosque a cadaletra de}alfabetole corresponde nmerodel I al 26,represenun tando su posicinen el alfabeto,s M es el texto comny C es el texto crado, enonces C=M+3(n6d26)

F,

Mrutc DlscngtAs RAMoN EsprNosA ARMENTA

ALFAOMEGA

778

IV,

GRUPos, ANrrLosY cAMPos

El receptor del mensaie puede descifrarlo usando la frmula M=C-3(md26) En este caso el nmero 3 es Ia clave para enctiptar y desencdptar mensajes. Si dos personas queran comunicarce usando este sistema, ambas deba conocer la cla_ ve y evitar que sta fuera conocida poI terceros.

En un crptosistema de clavo privada, el emisor y el receptor de un mensaje conocen y utilizan Ia misma clave secreta para encdptar y desencdptar el mensaje, respectivamente. EI pdncipal reto consiste en mantener en secreto la clave, Io cual es difcil, especialmente en sistemas abiertos con mltiples usuarios. Por esaazn en 1976 Whitfleld Dfe y Martin Hellman2 propusieron una idea radicalmenLe nueva en criptogTafa.La idea es la siguiente, supngase que se pudiera disenar un mtodo de encriptamiento y desencriptamiento de datos, donde la clave de encriptamiento fuera dsiita que la clave de desencriptamiento, y que el conocimiento de una de esas claves no permitiera encontrar la otra. De esta manera, Lu banco, por ejemplo, podra hacer pblica la clave de enciptamiento, para poder recibt mensajes de sus clientes, manteniendo en secreto la clave de desenciptamiento, asegurndose de que sta sea prcticamente imposible de descubr, Un mtodo con estas caractesticas es llamado un criptosistema de clave pblica. En 1977,poco despus de que esta idea fuera propuesta, tres jvenes matemticos del MIT, Ronald Rivest, Adi shamir y Leonard Adleman3, dieron un ejemplo concreto de cmo esta idea poda llevarse a Ia prctica. En honor a sus descubridores, el mtodo se conoce como criptosstema RSA. En Io que sigue se supone que cada letra del alfabeto es una pareja de nmeros enteros del 01 al 26. Tambin se utiliza Ia pareja 00 para denotar un espacio. Por ejemplo, el mensaje BUENoS DIAS, se puede representar como 0 2 2 1 0 5 1 4 1 5 1 9 0 0 0 4 01 9 .1 90 El mtodo RSA se inicia seleccionandodos nmeros pdmos distitos, p y 4, ambos suicientemente glandes. Sea n = pq, por lo lanlo (p(n) = (p - l)(q - l). Luego rje ellge un entero > 1 tal qne mcd(e,(p(e))= 1 y se resuelve la congruencia lineal ed= I fudE(n)) La eligiendo d de modo que 0 < d < @(1). pareja de enteros (, ,) es la clave plbljira que utilizar el emisor para encplar mensaies y la pareja (d, l ) es Ia clave pdvada que utilizar el receptorpara descifrarmensales.

dc d(

'zW Diffle v M. S. Hellma, New directions in crwiographf IEEE, Trnsactions i)n InfartDaon Thea)y' 22 tr9?6). 644-654. 3 R. Rivest, A. Shami, L. Adleman. A ethod for obtainig digital signawes at public key cliptosys' 1 r e m s .c o m m . o f h e A c M , 2 1 ( 1 9 7 8 ) , 2 0 - 1 2 6

ALFAOMEGA

M A T E M A T T C A Sl s c R E T A s R A M o E s p r N ,s A A R M E I" A D

4.8 ApLrcAcrN:cRrpTocRAFA Tambinse supone que el mensaje que se guiere enviar es un nmero entre 0 y - l, si no es asel mensajssepuededivid en bloguesde nmerosen eserango. Sim es el mensaje original, entonces el mensaje cifado C es el residuo obtenido a.ldividir M" ente n, eguivalentemento,C es la solucin d,ela congruencra W=C(m6dn) 0 .donde S C < n. Para desciffar el mensaj el receptor calcula el residuo R obteniat divid C entrs , equivalentemente do C=R(md) donde0 < n < . El siguiente teorema muestra que R = M.

179

Teolgt|a 4.22 Seanp y q dos primos stintos, n= pq, y e, d enteos pos Sio vostdes que ed = | (m6drp(n)). 3 M < n y W=C(mdn) (md n) C = JR donde0 < R < n entoncesR = M. Demostracln Porhiptesis d= I (md(p - lXq - l)) po Io tanto existe un entero positivo /r tal que
ed=l+k(p-l)(q-l)

Deaqugue
R=C = (M")d = M"o
= Mt+k(t>t)(.t-t) . = MMk(F-t)(q-t)

(mdn) (md z) (md n)

(md ) (md )

Como se sigiue pln, que (m6dp\ R _ MMktp_Dk)) Seaflrma que I = M (mdp). Paa probar esta anlmacin se considelan los casos plM y pI M
DscRETAs I{AMN EsprNosAARMENTA

ALFAOMEGA

180

IV,

Y Gnupos,ANrLLos cAMPos Caso 1. Si plM entoncesM = 0 (mdp), por Io tanto : Mlktt'-t)\q-t) 0: M (md p) Esdecir,R=M(mdp). Caso 2. Si p ,f M, se sigue del pequeo teorema de Fermat que Mt-t=l(md,p) Por lo tato = = Mt(r-t)(4-t) 1k(s-r) I (md p) = De aqv MMk(t'-t)kt-r) M (rnd p) y por 10iario R = M (md p). Como 4ln, un argumento similar muestra que R = M (md 4). Por 10tanto R es una solucrn del sistema de congruencias lineales

n=M@6dp)
R=M(m6dq) Como p y 4 son pdmos distintos se iiene q|j.encd(p, q) = l, de agu que, por el teorema chino del residuo R = M (md n), donde r = :q. Como adems 0<M<xentoncesR=M.

gneral los simuladores el de en Deacuerdo con lo expuesto estaseccin, propsito . GENERADOR CLAVES DE RSA . CODIFICADOR FSA . DECODIFICADOR FSA y y un respectivamente gsneraruna clavepblicay una privada, codificar mensaje es generadas, decodifcar mismousandolasclaves el

Elomplo 4.41 Detetminaruna parejade clavesen el sistemaRSA,usandolos PrimosP=7Y4=11. yg(n)-60. Un entero mayorque I y primorelativo.. . Solucl Enestecason=77 = 7, por lo que una clave pblica es (, n) = (7,'7?).Pdra determin la a 60 es e clavepivadacorrespondienteseconsideIalacongruencialineal. 7d=lOnd60) la cualtiene solucind = 43. PorIo tanto la.clavepdvada os (d, n1:: ga,7l.
.:i:;. :1,, , . , ,.;:;.1

l' :
.',:!i,. ;it:l:;..;l

ALTAOMEGA

_ ARMENTA MATEMTCASDISCRETAS RAMN ESPINOSA

4.8 ApLlcAcrN:cRrprocRAFA

181

Eemplo 4,42 Encrptarel mensaje HOLA con ta clavepblica (7. 77),usandoel sistemaRSA. Solucln En formanumricase tiene que HOI,A = O8151201 gue es un nmeto mayor gue r= 77, pr lo que se ncesita divid.ir el mensajeen bbques de una letra: '
t -

H=08=Mr

O=15=Mz,

L=12=M

A=01=M

Paracadauno de los submensajes se necesitaobtenerCi = M] Mi mdulo 77. Se puede verif,carfcilmenteeue C1= 57, C2=71, C3= ll y Qu= l, por lo gue el mensaje encriptadoes C=57 7l l2 01

Eemplo 4,43 DescrarC = 5? usando la clave privada (43, 7't). Solucln Senecesita calqlar57o3 77, mdulo Conestefln se ob. servacJue = 25+ 23+ 2 + | = 32+ I + 2 + l. Porestoseiiene que 43
5743-5732.5i8.572.5i

Ahora bien (md77) (md77) (m6d77) (m6d77)

57t6=362=64 5732=642=15

(md77) (m6d77)

PorIo tanto = 5'741 5'7. 15 . 36. 15= 8 (md7?) Es dec, el mensajenunrico es 08, gue cosespondea la letra H.
MATEMTrcAs DrscRETAs- RAMN EspiNosA ARMENTA

ALFAOMEGA

182

IV.

v Grupos, ANILLos cAMPos

'

En la prctica los nmeros p y q se eligen de modo gue tenga alrededor de 100 dgitos docimales,por lo gue n =pq tiens alIededor de 200 dfgitos. En la astualidad en no existe un mtodo que permita fadorizar un ntlmso tan gTrande un emps suflcientemente paguso como paa gue pueda ser utilizado para enconuar h clavo prvada d, por esta razn el sietemaBSApuede considlarse comoun cipto. sistema de clave Pblica.

y RSA 4.8.1 MATLAB el crlptosistema

tr

adioonal En la lectura RSA MATLABY EL CRIPTOSISTEMA paraimplementar simuladorss como Ge. la s6 describe formaen que se usa MATLAB norador de clavss BSA, Codlflcadot RSA y DcodlfcadorRSA.

En este caphllo se presentola nocin de opecinbinaria, luego se eLpusoel con" cepto de gnupoy los @nceptosde anillo y caopo, probado suspropiedadosen cada caso.En partrcularse pressnt el anillo de los enterosmdllo m y cmos utiliza la moderna' ait[itica modularen la criptogirafa ED el slguiente capitulo se estudia un ao particular: el ano de los polinomios con cosfsientes en un caripo arbiario.

ALFAOMEEA

MATEMTICAS DISCNTTA8 - RAMN ESPINO8A A3MENTA

..10 PRoBLEMAS

'i.51,

gue [] es ei eiinentounitaroen 2,, 4.56 Demostrar

': , ;lii;., ..

. i , : . . . i i ' ! r : :,

lill,,' . . ,:" : ,
;,

4.57 Demostrar propiedaddistribufiva en 2,,,,. Ia 4.58 Escribir tabiasparala sumay el producco Za. las en

i '.

Ztg 4.63 Utzar el torema de Euler para determirar ei inverso de [5] en Z59. . ara deferminar el inverso de l8l enZ31. '

t l l v t p- 1 1 , -

4,67 Utzar el sistemaRSApara enciptar el mensajeAVE blica(5,85).

4.68 Usardo los slmuladores . GENERADOR DE CTAVES RSA . CODIFICADOR RSA . DECODIFICADOR RSA
rae^lvr l rhlr .rti^i

4.69 Utilizar el sstema RSA para encptar el mensaje UVA con Ia clave pblica (7, 9l).

M t r v r r r c , rD ! c R E f A t '

R A M o Nf s f . N . , . A p r , , N - ^

ALFAOMEGA

GRUPos, ANELoSY cAMPos

4.7 UsaDdoos simuiadore . GENEnADORDE CLITVES nSA . CODItrICADOANSA . DECODIFIOADOR RSA fesolver eI problema anterior.

ALFAOMEGA

D$CRETAS RAMN EspnlosA ARMENTA MATEr,rTrcAg