• Author / Uploaded
• Miguel

• Categories
• Número primo
• División (Matemáticas)
• Conceptos matemáticos
• Teoría de números
• Números

Citation preview

Parte 1 Teoría Elemental de Números 1 1-1 Algoritmos de División y Euclides 3 1-2 Números primos y Teorema Fundamental de la Aritmética 29 1-3 El Principio de Inducción 55 1-4 Ecuaciones Diofánticas 69

1-5 Congruencias 91 1-6 Sistemas de Numeración y Criterios de Divisibilidad 123

Parte 2 Introducción a la Teoría de Grafos 133 2-1 Grafos, Digrafos y Multigrafos 135

lndice General

2-2 Grafos eulerianos y hamiltonianos 151 2-3 Exploración de Grafos 173 2-4 Mapas y Coloraciones 197

Parte 3 Métodos Combinatorios 215 3-1 Técnicas básicas 217 3-2 Permutaciones, Variaciones y Combinaciones 229 3-3 Teorema del Binomio 261 3-4 Principio de Inclusión-Exclusión 281 3-5 Recursividad y Relaciones Reccurrentes 289

Bibliografía 305 ik

lndice 307 , - -.

Lista de Símbolos 311

fJ;

-y&i:?q !7

1

Teoría Elemental de Números

1

1 Teoría Elemental de Nomeros

-

Rccordernos que la suma y el producto de númcms cnicros son uper+acionesque satisfacen las propiedades ascicii~tivily comniutativü, Ademis, (X.+) es un grupo ahclianti. Tambiin se satisface la propiedad distri butiva

por lo quc (Z, +, .) cs un ariillo coriinutaiivo con elemenro iinidrzd (el I y sin divisores del cero, es decir si ab = O enionces neccsariamentc a = O ri b .-u.

continurici6n se demiiestrari algunas propiedades elenientriles de los nílmcros enteros rcspccir~1i cslas operaciones. 12

1-1.3 Propiedades Scün a, h, L: númcros cnter-os, 1 ,-0.a = 0. 3.- ii(-6) = -ü.b. 3.-Si ; i ; t O y ab= ac,cnlonces b = c . 4.- Si a # O y a 1 b, entonces ;i ( hx para cadacntcro x . 5.-Sc;ina#OybfO,siaIbybIcentoncessIc. 6.- Sea a $0. SI;i 1 h y a 1 c. sc vcriíica que ü 1 (bx + cy) para cualquier par de enlcrr~sx c y. 7.- Sean a y b positivos. Si a 1 h cntonccs a 5 ti. 8.-Sean 1i rt O y b +O. Si a 1 b y b 1 a, se tiene que a = b 6 a = -h.

Demostraci6n I .- Como O + O = O lerierrios que

qiic por la prnpicdad disinbutiva es Oa micmhros 0.a lenemos que

+

01i, Restando en ambos

1

1

f -1 Algo ritmos de División y Euclides

neros enteros son la y ccimmutativa. isfoce l a propiedad

(el 1 ) y :sariamenre a = U 6 :rito unidlid

par la propiedad asociativa. Por tanto,

pero como O es el elciiieiilu iieutiu de la surna, coriclui mtis que O = Oa. 2,- Por Jefinicicin -ab cs cl clcmento opuesto de ah respecto a la sunia y además es único. lZsi pues,

Luego a(-b) es el elemento cipucsto de ah y por tanto igiial :t -3b. 3.- En la igualdad ab = ac sumamos -ac a ambos miembi-os.Se obtienc,

Corno a +; O y X no tiene divisores de cero eiiiusiccs ~icccsüriamcntc

1 para cualquier par

a = -b.

:stand[) cri

ambos

Sumando c a arnbos rnicmhri)~dc la igualdad obtenemos b = c. 4.- Por definicihn si a 1 h existe un niimero q tal que b = liq. De ayui quc b.r = ayx, Sea q'= qx, cnlonccl; hx = aq' y por tanto a 1 bx. S.- Si a 1 h existe q1tal qiie b = aqi. Si b 1 c existe ql tal que c = hq2. Poitanto c = bq2 = aqlq7. Sea q = qiqz, se tiene qiie. c aq luego ü 1 c. 6 . -Si a 1 b y a 1 c existen q, y q2 tales que b = üq, y c = aq1. Entonces,

donde q = q l x + qzy. Asi pues, ü 1 (bx + cy). 7.- Si u 1 h c.ristc q tal quc h = aq. Como a y b son positivos q es positivo. Por t ~ n i podenios o esctibii-

I

7 Teoría Elemental de Números b) Si ac 1 1

Como q es posit~voq-1 2 O por tanto s r O. De b = a + S se deduce que a 5 b. 8.- Como a 1 h existe q l tal que b = a q l . De b 1 a se tiene que existe q2 tal quc a bq2. Por tanto a = aqlq2.Se deduce que qlqz = 1 y por tanto q l = q 2 = 1 iiq, = Y ? = - l , p ~ r l u q u c i i - b i i ~ = - b 4.

Solucidn a.- I)e a 1 b y c Por tanto

-

Por la propiedad 1 de 1-1.3 tenemos que 0.a = O para todo níirnero cri tcro a, cntonccs para lodo númcro cnlcro a sc ticne que a 1 0.

1-1.4 Ejemplos Pruéhese que dados a, ti, c y d enteros, entonces I (a + b)(c + d) ac + bc + ad + bd,

-

h) (-a)(-h)

donde q = q [q. h.- Si ac 1 bc ( propiedad disl

Corno c + O

decir b = aq. y

= :ih.

Solucidn a,- Por la propiedad distri biitiva podemos escribir

y ~iplicandola propiedad distributiva de nuevo a cada sumando tenernos

1-1.6 Definicidr Llamaremo:

definida por 1 n

ObsFrvcsc I entero tiene im b.- PorlapropiedadZde 1-1.3 se tieneque

(-a)(-b) = -[(-a)b]

= -[-(rib)] = ab. +

1-1.5 Ejemplos Seaii a, b, c y d entesus cori a # O y c + O . DemuEsiicsc quc a) Si ii 1 h y c 1 d cntonccs ac j hd.

1 -1.7 Propiedad

1.-lnlcNv{ 2.-[nI=Osiy! 3.- Ia.hI=l al.1 4.-la+blSla

5.-Sia*O, b *

1

-

1- 1 Aigoritmos de Divisidn y Euclldes b) Si ac 1 tic eritorices n 1 b.

Solución

+ s se deducc quc

a.- Dc a 1 b y c 1 d sabenios que existen q l y qz tales que b = aql y d = cq,.

Por [unto

le que existc q2 tal q~ = L y pur tanto

para tcido número que a 10.

bd = üqtcq2 = acq lqz = cicq,

donde q = qlq2. Asipues ac 1 hd. b.- Si ac 1 bc existe q tal que bc = 3cq. Entonces bc - cicq = O, y por la propiedad distributiva podemos escribir

Como c # O y Z no tiene divisores de cero deducimos que b - aq = O, es decir h = aq, y así a 1 h.

+

A continuación definimos el valor ribsoluto de los números enteros. 1-1.6 Definici6n

Llamaremos vnIor nbsolirro a la aplicaci6n

;urnandotenemos

i.

ie que

Obsérvese que la aplicación esth bien definida, es decir todo niirnero entero tiene imagen mediante 1 ] y esta imagen es única. 1-1.7 Propiedades del valor absoluto l.-lnl ~ N v ( 0 ) . 2.- ln 1 =Osi y s61osin=0. 3.- ) a.b ( = 1 ri 1.1 b l. 4.-la+h[llal+lbl. 5 . - S i a ; t O , b # O y a I bentonces1aI O cntonces rib 2 0;por tanto

Como

El caso tenemos c

5.- Si a 1 propiedad

l u 114 1.Pl Aiiülogamente se cs~urliael caso cuai~doa c O y h > O. Por Último, si ü < O y h ~ O t c n c r r i v s ü b > O y a d e m , Z s I aI = - a y l b [ = -b.Portsnto

4.- De la definicitin de valor- absoluto sabemos quc

u t b

/a+bl=

sia+b20,

Soluci6n De ladt a c O. Por -asalb Si a < O Veamoi

Pero esto i = -a y por

!

1- 1 Aigoritrnos de División y Euclides

r absoluto. Como b 0. enlotices existen entcros

q y r únicosiales que

6.- Sean divisor c

lineai de

7- 1 Algoritmos de División y Euciides donde 2b 5 r < 3b.

d 1 (a - b), entonces 'a+ b)- ( a - b)= 2b. = 2. Como d 1 2 se 8)

3.- I )ernuksrrese que: a) El cuadrado de cualquier entero es de lu forma 3k ó 3k+ l . h) El cubo de cualquier entero es de la forma 9k, 9ki-169k +S.

4.- Sean in, x e y enteros, cori m # O. PruEhcsc quc x MOD m = y MODm s i y solo si x - y es múltiplo de ni. 5.- Calcúlese cuanto vale

6.- Sean a, h y d nlimeros enteros con d > O. Pruébese quc si d cs un divisor comiin dc a y h, y d se puede expresar como una combinación lineal de U y b entoiices d = rii.c.d.(si,b).

7.- Clsando el Algoritmo de Euclides para el c Alculo dc d = m .c.ci.(a,h), encuéntrense x e y tales que d = ax + by. a) a = 1312, b = 800.

3nces existen enteros

I 1

Números primos y Teorema Fundamental de la AritmBtica. I

!

l

Un coiicepto esencial en la 'leoria de Niimercis es el de niinlero primo. i!n la Secci6n anterior hemos visto quc cada numcro cnlcm p > 1 cs divisihlc por 1 y p. Si Cslos son los Únicos divisores positivos de p, direnios eritoricrs que p es un nu~lieropiiii-io. Fn esta Scccirin sc cstudian algunlis prcipiedades bisicas de los iiUriieros prinios. Conio corisecuencia de ellas se establece e l Teorelila Fundamental de la Aritmktjca, que permite factorizar todo niimero entero como productn Jc primos. Poslcriomcntc sc dernueslra la exisieiicili de iriliriiios ilurrieros yririios y se establece la relacióti entre las factorizac16nes de niin-ieros enteros eil primos y el cAlciilo del máximo comiin divisor y minimo coniiin multiplo de varios números. [.a Seccihn finaliLa con una inlroduccibii a iiúi~icrosprinios "grandes", 1-2.1 Definición Dado uii 1iiiniei.o entero p 1 , diremos que p es ui-i tilitrict.~yt-ii~o( o simplemente primo), si 1 y p son las Únicos divisores pcisitivos dc p. IJn cnieru a l qut: es no primo Ir: denoniirlaremos núrneru cumprresio.

Dc la dcfinicibn dc prinio, es claro qiie u11entero p 3 I es pritrici si y s61o si es jiiiposible expresar p - a.b, doiidr: a y b soii eiiter-os, y aiiibos lqacp y 1 ~ b ~ 1 ~ . En lo que sigiie p designará iin niimero pritno inayor que 1 . Rn e l conjunto dc los diez prirtieros riut~ierostialurales 2, 3, 5 y 7 sun prinios, mientras que 4,G,S. 9 y I O son iiumeros compuestos. Obsetvenios que el niimero 2 cs el Único prjmo par.

1-2.2 Ejemplo Factorizar 276 como un producto de primos. Sotuciiin Conio 276 es par entoiices es divisible por 2 y por tanto 276 2.138.

-

-

7 Teoría Elemental de Números

Puesto quc 23 es priino, finalmetitc sc puede escribir

1-2.3 Definición Scari a , ,..., a, iina faniilia de nGine1.0~enteros. Iliremos que los al, ,... a,, sonprinios ~jttresi,si se tiene que

y por lo*

Obse dcscnml

1-2.4 Ejemplo ilemirestresc quc 3111 + 11 y 3m m

6

-+-

7 son primos eritre si para todo

7,.

Solución Obsei~eniosqiie existen dos ntirrieros enteros a = 2 y b = -3 ialcs que

1-2.6 Lemi Sean L

cntoitces por 1- 1-23 m.c.d.(Rm+ 1 1,Zm + 7) eiitre si.

+

-

1 y por tanto son primos

si yilueí Demos1 Como

1-2.5 Ejemplo Dernuestrese que si p r 3 es u11 iiurnero primo enlonces p2 + 2 es uii numero compuesto. Solución Tudo nii~iieroentero piiede expresarse conio Por hi

7-2 Números primos y Teorema Fundamental de la Aritmética.

Observenios que 6k, 6k +2 y 6k +4 sori pares y 6k t- 3 = 3(2k + 1) cs mi~ltiplode 3. Por tanto solo los que sean de la forma Gk + 1 o 6k 3- 5 pucdcn ser primos. Entonces, si p = Ak t 1 se tiene

ysi p = 6 k

i

5 se tiene

y por 10 türito siriibvs su11coinpucslus.

)s. Diremos qiie los

+

Observemos qiie el níimero 5 divide a 100 y que este se puede descomponer de diversas maneras como prodiicto de dos números:

os entrc si para lodo

i

En cada ~ m de a las descomposjciones el nhnero 5 divide, al rricrios, a Lino de los dos factores. El siguiente Lema, obtenido por Eiiclides, IlcrriustrarP que cs uri resultado gcncral.

2 y b = -3 tales que 1-2.6 Lema de Euclides Sean a, b y c nunieros erileros. Supongamos quc a y c son primos entre si y que c 1 ab. Entonces c 1 b.

Y

- por taita son primos

fitonces p2 + 2 es un

Demostración Como a y c son prin~osentre si existen ~iutiietosx, y E Z tales que

1

Multiplicri~idoai~ibosiiiiei~ibr-os de la igualdad por b se tiene

-

-

f Teorla Elemental de Números

7-2 Nume

c 1 (bax+bcy) y por tanto c 1 b.

Solucibn

-

+

Como i

1-2.7 Corolario Sca p un nuniei-o entero mayor que l. [.as afimiaciories sigiiientes son equivalentes: El numero p es primo. Para ciialqiiier par n y b de niiiliei-os enteros, si p ah entonccs p 1 ü 6 P 1 h. Demostraciiin Supungan~osqiie y es tin numero primo y quc p 1 ab. E~iipleai~do el Lcnia de Euclides, podemos suponer quc p no es pi-inio coi1 a, entoiices si d = in.c.d.(p,a) es ri 1 , d 1 p y d 1 a. Coi110 p es primo d = p y por taiito p 1 a. Suporigamos ahora quc p no cs priiriu. Existe11eiitonces números a y h tales que 1 i l } y S = { M,n(n-1) n~ ... 1>2"].Claramente 4 E S ya que 4.3.2.1 = 24 z4 = 16. Sca k 2 4 y supongamos que k E S . Por tanto k(k - l)(k - 2)... 1 =. zk. Multiplicando ambos niiernbros por k + 1 tetiernos

ya que k + 1 > 2. Asi pues k + 1 e S. Por el Corolario 1-7.8, S = M y la propiedad es cierta para todo n 2 4.

1-3.1O Corolario Sea no E Z y supongamos que P es una propiediid para la cual 1) P(no) es cierta, cs dccir el riumero no satisfice P. 2 ) Para cada k 2 II(, arbitr"o se tiene que si P(k) cs cierta eiitonces P(k

+ 1) cs ciertsi.

Entonces P(n) sc salishce para todo entero n 2 no. Demostracibn Es análoga a la del Corolario 1-3.8 tei~ienduen c.ilenta el Corolario 1-3.5. Se deja al lcctor corno ejercicio.

13.1 1 Ejemplo ílemuéstrcsc que para cada enlero no negativo n, y para cada conjunto A con n elementos existen cxactamente 2" subconjuntos distintos dc A,

Solucibn Sea Y(n) la prupicdad; para cada conjunto A con card(A) = n el cardinal del conjunto de las partes dc A, cs dccir card(q(A)), es 2". Sea S = {n E 2,n 10,P(n) es cierta). Obviamente O E S ya que card(A) - O implica qiie A = 0 y cnlonccs

$2(A) = ,

Supon

F ijcmos

cor~juiit Sea B que t,

€

subcoiiju B = D'w

Así pues,

Eii oi condiciot motivo ii

Inducciói

1-3.12 Teors

Sea S u

I)1 E ! 2) Para entonces

Ei-itonc Demostr IJna ve

coniradic

S # N. Er tiene prir n o > 1. M 2,..., no con la hip

Ecuaciones Diofánticas t, < 2" para cada

emostrar usandu cl 3don EN.S i n = 1 todokccin 1 < k < n

1 para lodo n

1

E

N.

tl

DioFantii Cuc un matemitic0 que trabajó en Alejandriri ü mediados dcl siglo 111 u. C. Escribirj seis libros siibrc problemas de 'l'eoría de Núrnet40s, y fiie lino de los primeros en intr+oducii.la noixiiin simbólica en rnuiemaiicas; por ejemplo utiIiz6 un símbolo similni. a tiuestra Icira ' x ' pürn desigriar la vuriuble indcicrminada de una ecuación. Estudio proh temas en los que consideraba In i-eprcscn~icibndc números enteros como suma dc cuadrados. En honor suyo se usa el nonibse de ecuacioncs diofinticas para designar una amplia clase de ecuaciones algebraicas con más de una indetem-iinadaen un particulur sisicrna dc números como son

Z y Q (níirneros racionales). Se dedica esta SecciVn a una in[rrducción a las eciiaciones diofrinticas. Se resueIven 1;is ecuaciones litieales de dos variables en X, las ecuaciones de la f u m a 2 - = n, que sirven para estudiar después el mttodo de factorizaci611 dt: Fermal, y las ecuaciones pitagóricas x2 + y2 = 2. Se termina la Sección con el i s i llamado Úliirno Tcorcrnil de Ferrnat.

1-4.1 Teorema Scan a , b y n números enteros. La ecuaci811lincal ax + by = n tiene solucii5n cntcra xg e y0 si y s61o si d = m.c.d.(a,b) divide a n . Demostración Supongümus quc la ccuación tiene solución xo e yo, entonces

Sea d = m.c.d.(a,b)entonces d 1 axg y d 1 byo por tanto d 1 n Supcingamos ahora qtie d 1 n. Si n = O entonces xu = O c yo = O es ubviumentc una solución que llamaremos ti-ivilil, Si n + O cntonccs d debe ser distintodecero. Pur 1-I.22existenenterosxIe y , talesque

1

I Teoría Elemental de Números

Sean xo =

n"

d

e YO

' . Es suficicnk coiiipiobar que xo e ' 7

yo cs

solución de la ecuacirjn. Para ello basra sustituir en la misma 1-4.3 Ejem

Encué

1-4.2 Algoritmo para encontrar una soluci6n Dado Ia ecuacifin ax + by = n en primer lugar calculemos el m.c.d.(a,b) mediante el algoritmo de Euc!idcs.Sabeinos que a- bql+rl, b = rlq? + r2, ('1-4.2.1) 5-2= rt-lqt+ rt, 't-

1 = 't %*l.

Solucior Calcul

de Euclic

Asi pu, la ecuacir Escri bi

-

donde r,=m.c.d.(a, h) =d. Por tanto rtm2 r,_,q,= d y se puedeescribir

que es equivalente a

Si continuamos ascendiendo por las igualdades (1-4.2.1) al final llegamos a poder escribir d como

Suponj a n. Enio dondc q * y q2* son expresiones en fundón de q ,..., q., Por el Tcurcrna 1-4.1 una solucibn de la ecuacihn serií tiene la fa

-

Veamos en un e\jeniploconcrcto cómo sc aplica el algoritmo.

obar que xo e yo es L

Y

misma

1

I

1

Calculemos en primer lugar el in.c.d.(525, 100)mcdiantc cl algoritmo de Euclidcs. 525 = 100.5 + 25,

ugar calculemos cl mos que I

(1-4.2.1)

1-4.3 Ejemplo Encuéntrese una solucicin de la ecuacibn diofhntica

(

-

100 =4.25. Así pues, m.c.d.(525, 100) 25. Observeinos que 25 1 50 y por 1 -4.1 la ecuación ticnc solucihn.

Escribimos y se puede escri hir

y en este caso tenemos q l F = 1 y q2* = -5. Una solución seri entonces

:S

(1-4.2.1) al final

El siguiente Tcorcma permite encontrar todas las soluciones de una ecuaci6n diofántica lineal n parirlir dc una soluci6n particular conocida. 1-4.4 Teorema Supongamos que a, b y n son enteros no nulos y d = m.c.d.(a, h) divide a n. Eiitonces la soluciiin general de la ecuaci6n

,., q,. Por el Teorema tiene 1a forma

I

h

I Teoría Elemental de Nrimeros

como a- y d

donde t

E

Z y ( xo, y O i csuna solución de (1-4.4.1 ).

Solución Sea ( xo, yo} una soluci61i paiticullir de (1-4.4.1 ), cnlonces

Por hipótesis d ( n así pues,

Yo-

Y1 =

( 1-4,4,5) S

y de aquí

y por Úliirr

Así pue (1-4.4.2). 1

Restando las expresirin ( 1-4.4.3)de la ( 1-4.4.4.) se tiene

o bien

E1 niimcrti

-d iietie que dividir al miembro cic la dci-echa de ( 1 -4.4.5) y a .

Luego {

1

entre sí.

1-4 Ecuaciones Dlofánticas

b entre si entonces a- dividc a yo - y l . Por tanto, d d a a yo - y 1 = t - , y de aqui y1 = yo - t - . Sustitiiyendo y 1 por yo --t 2 en d d d ( 1-4.4.5)se obtiene a d

crimo - y - son primos

y por últi rno

-4.4.3) cumplirh

:tiene

Así pues toda soluciijn dc ( 1 -4.4.1) se puede escribir eii 1u forma Recíprocamente para todo t E Z cada par de valores { x y, ) de la forma ( 1-4.4.2) es solución de (1-4.4.1):

,,

( 1-4.4.2).

=axo+ byo=n.

Luego {xl,y l } es solución de (1-4.4.1)cua1quicrilqucsca t

E

2. +

1 Teoría Elemental de N h e r o s

1-4.5 Ejemplo Encuéntrense todíis las soluciones LIc la C C U S I C ~ del ~ ~ I e-jeinplo 1-4.3.

Soluci6n

En 1-4.3 se vio que xo = 2 c yo = -10 era una soluci6n particiilar de la ecuación 525x + 100y = Síl. Idasolución general tendrA la forma

1-4.6 Ejemplo Una joyería vende collares dc pcrlas a 640 € y pulseras a 330 f . Una persona ha cnmprado ciillares y pulseras por valor de 7 140 f:. ¿Sufintris ohjcios dc cada clase ha con~pradosabiendo que hay más pulscriis quc col lsires? Solución La ecuación qiie debcrnns rcstil vcr cs

donde a esel niirnero decrillares y n cscl dcpulserns. Aplican do el algoritmo de Euclides tenemos A40 = 330 + 3 10, 330=310+70, 310 = 15.20 + 10, 20=2.10+0. Pur Ilinio iii.c.d.(640,730)= 10. F,scrihimos ahvrlt 10 = 310 - 15.20, l o = 310- 1 5 . ( 3 3 0 - 3 1 0 ) ~ 16.310- 15.330, IO = I6.(640- 330) -15.330 = 16.640 - 3 1.330.

En el s parlic ularc

enunciado, Ohscrvc

la soluci6n

De las ct

Además o bien

Luego e ) t (=346y a= n=

1-4 Ecuaciones Diof i nticas

Luego una solucion particular scrh

ición particular de la ir4 la forina

! 1

y la soluci6n general será

ulseras 330 €. Una l e 7 140 f . i,Cuüntos ay más pulseras que

En el siguiente paso dchcrnos determinar el valor o los valorcs particulares del parainetro t que satisfacen las condiciones del cnunciadn, cs decir, n > a y obviamente ambos valores positivos. Observemos que en este caso t debe ser negativo. Podeirios rtiescrihir la solución general en la siguiente forma cuando t < 0: a=11424-331tI,

n=-32134+64(t(. De las condiciones a > O y n r O ohicnemos

1 1424 M< 33 , es decir 1 t 11 346 y

Además de n > a obtenemos 97ltI>I1424+22134=33558, o bien

Luego el Único valor de t que satisface todas las condiciones es

( t ( = 346 y de aquí t = -346. Por tanto la saluci6n buscada es a = 11 424 - 33.346 = 6 , 6 collares, n =-22 134+64.346= 10, 10pulucras.

+

I

1 Teoría Elemental de Números

Consideremos ahora la ecuaciiin x2 - y' = n coii ii > O. Como antes nos interesan 5610 las soluciones cntcras dc csta ecuricioil, soluciones que el siguiente Tcrircma proporciona, 1-4.7 Teorema 1 .a ecuaci6n diufúniica x2 - y2 = n con n > O, tiene solución si y sóln si ti se puede factorizar como producto de dos númcrns dc la mismili paridd. es decir ambos pares o ambos iinpares. Si existeti, las soiuciones de esla ccuacirín tiencn la fui.rnri

2

x = a+h y= a-b i

- 3

2

dnndc r i y b rcconen todos los pares de nlimeros de la misma paridad y i d e s que n = a.b Demostración Podemos escribir

SoluciCin Factorii

Entonce misma par 120=61 Comti E quea2b.1

donde x - y y x + y tienen la misma paridad, ya quc

Supongamos ahora que n = a.b donde 3 y b tienen la mism;i paridad. Si se escribe x+)'=a, x -y=h,

entonces al resolver este sistema se obtiene x=- a + b

2

a-b , ,y= 2

que es una solucián de laecuilcihn x2 - y2 = n.En ekcto

donde x = ! { 17, 131, {

A pan algoriimo

n > O. Corno rinics 5611, solucioiies que

le solución si y sólo meros de la misma isten, las soluciunes

-

1-4.8 Ejemplo Encudntrensc todas las solucicincs positivas de la ecuac18n

Solución Factorizando 1SO ohienemos

la misma paridad y Entonces podemos cscri hir 1 20 como producto de dos números con la misma paridad de las siguientes maneras: 120=60.2=30.4=20.ti= 12.10= 10.12=6.20=4.30=2.60. Como huscamos soluciones positivas cntonces x, y 2 O lo que exige que P L b. Sc iicnc por tanto R

b

x

v

a misma paridad. Si

+ b ,y = a-b donde x = a. Luego las soluciones buscadas son ( 3 1 , 291, 2 2 { l 7 , 1 3 } , { 1 3 , 7 } y [ l l , l } .+ A partir del resultado sintcriiir, Femat estableci6 en 1643 un algoritmo para estudiar si un número natural n impar es coinpuesto.

t

1 Teoría Elemental de Números Aunque el algoritmo piiedc resultar en algunos clisos niuy largo, riu requiere conocer todos los primos inenores que

Veamos

1-4.9 Algoritmo da Factorizaci6n de Fermat. Sea n uri niirnero natural impar. Si n cs compuesto se tiene que n = a-h donde a y b han de ser imparcs ttirnbién. Ademils podernr-is supurici que a 2 b > 1 . Por el Tcorcnia 1-4.7 se puede escribir

1-4.10 Ejemplj Gstíídiesi compuc.Fto Solución El prirnei

h.

ü+b 2

42)

a-h 2 - ".

(2)

Lucgv estudiar- si iin número impar es compuesto es un pmhlema equivalente a rcsiiivcr la ecuacibn xZ - y2 = n. Esta ccuación puede escribirse, x 2 - n = y 2 . El primcr paso cs dc~erininarel mínimo entero posiiivo q que satisfagri que q' 2 n y pocterionnentc habri que estudiar si alguno de los nfimcrtis

obt enernos niímeros m

I !

y ver s i para

!

q2 -", ( q + 1)2-n. (q+2)2-.,.. cs uri

cundrüdo. Este proceso no cx infinito ya que 2

n +2ri+l-4n - n - l

4

Pnr tanto 12 733 se de! 2

.

Esta soluciiiri corresponde a la faciori~~aciiin Irivisil n = 11.1. Luego los úriicos valores que hay que cscudiar son aquellos níimeros m quc

satisfacen

Considcr núiiieros: nal soluciones e riiingulos re los antiguos dc solucione cotnplct~dcl

Si para ningunu de estos números m, m2 - n cs un cuadrado, eiitonces n scriprimo. +

En primer de la ecuacid para cualquic

1-4 Ecuaclunes Diofánticas

-

Veamos cómo se aplica el tilgon trno cn un ejemplo concreto.

asos miiy largo, no

1

1-4.1 0 Ejemplo

se tiene que n = a.b is podeinos suponer i

I

Estúdiese iiiediante el algoritmo dc Ferrnat si el número 22733 es compuesto. Soluci6n El primer paso cs cncon trar el menor q tal que q 2 2 22 733. Opcranclo obtenemos q = 1 5 I . Como 22733

+

= 1 1367, hay que esludiar

10s

L

sto es un prublerria :sta ecuación puede

jitivo q qiie satisfaga uno de los nlimei.os

ní~merosm rüles que

y ver si para alguno de ellos iri2 -22733 cs un cuadrado. 'Tenemos 151'-22733 ~22801-22733= 68, 152'-32733 =23 104-22733 =371, 15.3~ -72733 =23409 -22733 = 676 = (2f1)~. Por t:into x 153 e y = 26. Así pucs U = 179 y b = 137. El nuniero

-

22733 vc descompone así,

al n = n. l . Luego Iris

os números

111 que

1 cuadrado. entonces

Ciinsideremos ahora h ecuación pitagórica x' + y2 = zZ con n, y, z nurriercis naturales. Como en los casos anteriores siilo nos interesan Iris soluciones en tcws. Este problema es equivalente ri encantrar todos los triángulos rectringuliis con Iridas de longitud entera y fue esludiado por los antiguos gzórnetras gricgris. Pitágciriis encontr6 una cantidad infinita de soluciones, pero fue Euclides en sus Elcmentas el que dio la soluci611 complcia dcl problema. b;n primer lugar observemos quc si la terna (xo, yo, zO)es uria soluciiin

ccuación x 2 + = z2. en toilces también ts solucihn (hxo. hyo,hzo) pasa cuülquicr nhmero entero ?L # O ya que

di la

!

I Teoria Elemental de Números

Pus otiii parte, si d es el máximo común divisor. de xo, y o y zo entonces

"

( d-

Y(, -

d

"o

-)d

fambidn cs soluciSn y adenih

3 Yo y 3 d ' d d

lu cual es I zOcs impa

de ser de d Supong* Por tanto 2

son prirnus

entre si. Pur taiito para resolver el problcma basta buscar las soluciones ( x ~ ' ,yd, zO1)con x t1> O con distinta paridad; por lo tanto

y así

S'

y t'soncuadrados s'=xf

y I'=~:, luego,por(l-414.11,

Pucstci que zly t son positivos

jad. Supongamos quc si, k'2-k')-1 d q ' + 3.

S

l

0