LOS NMEROS ENTEROSLos nmeros enteros son: .

Denotamos por el conjunto de los nmeros enteros. En este conjunto hay definidas dos operaciones: la suma + y el producto .Propiedades de la suma y del producto en Las operaciones + y satisfacen las siguientes propiedades: 1) Propiedad Asociativa:

2) Propiedad Conmutativa:

3) Existencia de elemento neutro:Para cada a se tiene que

4) Existe elemento opuesto para la suma: Para cada existe un nico elemento tal que

5) El producto es distributivo respecto de la suma: Sean a, b, c tres nmeros en Z se tiene que

El principio de Buena Ordenacin

Los nmeros enteros pueden ordenarse mediante la conocida relacin ser menor o igual que, que se representa por .Ejemplo 1.3.1. 3 7 y 4 1.

Proposicin: La relacin satisface las siguientes propiedades:

1) Reflexiva: a a para todo 2) Antisimtrica: si a b y b a, entonces a = b para todos a, .3) Transitiva: si a b y b c, entonces a c para todos a, b, .4) Dos enteros cualesquiera a y b siempre son comparables, esto es, bien a b, bien b a.

Ejemplo: Sea un conjunto y sea

Conjunto de las partes de A. La relacin es una relacin de orden en P(A) pero no es una relacin de ordenen total.Por ejemplo si , los conjuntos {a, b, c} y {b, c, d} P(A) no son comparables por que

El Principio de Induccin

El principio de induccin es una tcnica muy utilizada en Matemticas para demostrar la veracidad de algunas proposiciones en las que interviene una variable entera positiva n.

Principio de Induccin caso particular

Sea P(n) una proposicin matemtica dependiente de n (n 1), para la cual se tiene que:(a) P(1) es verdadera; es decir 1 satisface la proposicin.

(b) Para todo k 1, si P(k) es verdadera entonces P(k + 1) tambin lo es.

En esta situacin, la proposicin P(n) es verdadera para todo n N.

Ejemplo: demuestra que para todo n 1.Paso 1: Definimos la proposicin P(n). Sea:

Paso 2: Comprobamos que P (1) es verdadera. Puesto que , entonces P(1) es verdadera.

Paso 3: Sea k 1 arbitrario, tal que P(k) es verdadera. Es decir:

Veamos si P(k + 1) es verdadera. Para ello deberemos probar que:

En efecto: utilizamos la hiptesis de induccin:

Por tanto: P(k + 1) es verdadera. Luego la proposicin P(n) es verdadera para todo n 1.

Ejemplo 2: Probar que

Si p(n) es verdadera entonces:

Si p (k+1) es verdadero entonces debe ser igual:

Lo que prueba que p (k + 1) es verdadera. Luego, la frmula Es verdadera para todo n .

DivisibilidadSean, donde . Se dice que a divide a b si, y solo si, existe k tal que b = ak. Si a divide a b se escribe a|b. Si a|b se dice que a es divisor de b. Si a|b se dice que b es mltiplo de a.Ejemplos1) 3|15, pues existe k = 3 tal que 15 = 3 5.2) 7|14, pues existe k = 2 tal que 14 = (7) (2).Propiedades de la Divisibilidad Si a, b, c y d son enteros, entonces:1).2) 3) .4) 5) 6) 7) 8)

ALGORITMO DE LA DIVISINSean , existen enteros nicos tales que:.Se dice que q y r son el cociente y el resto de la divisin de a y b.Ejemplos1) 2)

MXIMO COMN DIVISORDefinicin 1: Sean . Se dice que , con , es un divisor comn de a y b si, y solo si,

Definicin 2: Sean a, b tal que al menos uno de ellos es distinto de cero.Se dice que d es el mximo comn divisor de a, b y se escribe: si, y slo si, satisface las condiciones siguientes:1) d es divisor comn de a y de b.2) Si d' es un divisor comn de a y de b, entonces d'|d.3) d > 0

Ejemplo:Los divisores positivos de a = 24 son: 1, 2, 3, 4, 6 ,12 y 24.Los divisores positivos de b = 18 son: 1, 2, 3, 6, 9 y 18.Por tanto, los divisores positivos comunes a 24 y 18 son 1, 2, 3, 6.Entonces:

Observacin: Sean a, b tal que al menos uno de ellos es distinto de cero.1) 2) Si entonces d , d es un divisor comn de a y de b. Por tanto, no existe un mximo comn divisor.3) El mximo comn divisor de a, b es nico.4) 5) Proposicin entonces.Ejemplo 1: ..

Ejemplo 2: Dos enteros a y b no ambos nulos son primos entre s .1) 19 y 11 son primos entre s: .2) 5 y 13 son primos entre s: .

ALGORITMO DE EUCLIDESSean tales que . Como calcular el mximo comn divisor de a y de bPaso 1: Dividiendo a entre b obtenemos:. Si, entonces y hemos acabado. Si , pasamos al Paso 2.Paso 2: Dividimos b entre r1 obtenemos:. Si r2 = 0, entonces y hemos acabado. Si r2 0, pasamos al Paso 3.Paso 3: Dividimos r1 entre r2 obtenemos:. Si r3 = 0, entonces y hemos acabado. Si r3 0, pasamos al Paso 4.Los resultados de las sucesivas divisiones los podemos escribir entonces de la siguiente forma:

Este proceso continua hasta que lleguemos a una divisin con resto cero.La sucesin de restos () k1 es finita por ser estrictamente decreciente:.El ltimo resto no nulo es entonces el mximo comn divisor buscado.Supongamos que el ultimo resto nulo es = 0, entonces.Ejemplo 1: Calculemos mediante el algoritmo de Euclides.

Como el ltimo resto no nulo es 1951 concluimos que:

Ejemplo 2: Calculemos mediante el algoritmo de Euclides

Como el ltimo resto no nulo es 1 concluimos que:

ECUACIONES DIOFNTICA LINEALES Sean . Se llama ecuacin diofntica lineal a toda ecuacin de la forma: , donde las incgnitas enteras de la ecuacin.Ejemplos ..Teorema: Sean a, b, c Z. La ecuacin tiene soluciones enteras si, y solo si .Ejemplos 1) La ecuacin no tiene solucin pues2) La ecuacin tiene solucin pues

Cmo calcular una solucin particular entera () de la ecuacin .Paso 1: Calculamos el (mediante el algoritmo de Euclides)

Entonces.Paso 2: Verificar que divide a c.Paso 3: Clculo de una solucin particular de la ecuacin:Por el Teorema de Bezout, existen tales que.Calculemos u0 y v0:Despejando en la penltima igualdad del algoritmo de Euclides obtenemos.Despejando a su vez de la anterior igualdad, que es:, y sustituyendo en obtenemos:

Si continuamos subiendo por la columna de igualdades y en cada paso despejamos el resto de la divisin y lo sustituimos en la combinacin lineal correspondiente, al final llegamos a expresar como combinacin lineal de a y de b, es decir: obtenemos tales que:

Paso 4: Clculo de una solucin particular de la ecuacin:Como divide a c, entonces existe tal que:

Luego .Por tanto:

La solucin general de la ecuacin Supongamos que la ecuacin diofantica admite una solucin particular(). Entonces la frmula de la solucin general (x, y) es:

Donde t es un parmetro que toma cualquier valor entero. Por tanto, hay infinitas soluciones enteras.Ejemplo 2: Encuentra una solucin particular de la ecuacin Diofntica siguiente:

Paso 1: Calculamos (mediante el algoritmo de Euclides)2378 = 1 1769 + 6091769 = 2 609 + 551609 = 1 551 + 58551 = 9 58 + 2958 = 2 29 + 0El ltimo resto no nulo es 29 por lo que:

Paso 2: Puesto que 29 divide a entonces la ecuacin tiene solucin.Paso 3: Clculo de una solucin particular de la ecuacin :Por el Teorema de Bezout, existen tales que29 = 2378 + 1769 .Calculemos :29 = 551 9 58= 551 9 (609 1 551)= 10 551 9 609= 10 (1769 2 609) 9 609= 10 1769 29 609= 10 1769 29 (2378 1 1769)= 39 1769 29 2378Obtenemos .Paso 4: Clculo de una solucin particular de ():Tenemos , multiplicando esta igualdad por 71 obtenemos

Hemos encontrado una solucin particular.Paso 5: Solucin general de (): Entonces la frmula de la solucin general (x, y) es:

Donde t .

Ejemplo 3: Se quiere encontrar una solucin entera de la ecuacin diofntica:.En primer lugar observamos que mediante el algoritmo de Euclides:

Por tanto y adems como , se tiene que la ecuacin diofntica tiene soluciones enteras.Despejando de la primera ecuacin se tiene:

Y en este caso obtenemos:

Que es una solucin entera de la ecuacin diofntica.

Ejemplo 4: Se quiere encontrar las soluciones enteras de la ecuacin diofntica del ejemplo anterior:.

En primer lugar observamos que mediante el algoritmo de Euclides:

Sabemos que es una solucin particular, por tanto aplicando la proposicin anterior se tiene que todas las soluciones son de la forma:

Nmeros primosSea . Se dice que p es primo si, y solo si, sus nicos divisores positivos son Ejemplo:

TEOREMA FUNDAMENTAL DE LA ARITMTICATodo entero n > 1 se puede expresar como producto de primos:

Adems, esta expresin es nica salvo en el orden de los factores.

Factorizacin Cannica de un Entero Proposicin: Todo entero se puede escribir de manera nica de la forma:

Donde con pi primo para cada

Ejemplo:1) La factorizacin cannica de es: 2) La de -588 es:

Proposicin Si n es un entero tal que ningn primo lo divide (es decir, ) entonces n es primo.

Ejemplo 1: Estudia si es primo. Calculamos.Estudiamos si hay algn nmero primo que divide a 173:

Por tanto 173 es un nmero primo.Ejemplo 2: Estudia si es primo. Calculamos

Estudiamos si hay algn nmero primo que divide a 917:

Por tanto 917 no es un nmero primo.Ejemplo 3: Estudia si es primo. Calculamos :.Estudiamos si hay algn nmero primo que divide a 821:

Por tanto 821 es un nmero primo.

CongruenciasDefinicin Sea y sea , se dice que son congruentes modulo m si y slo si m divide es decir, y lo representamos por:

Ejemplo:1) 2) 3) 4) Propiedades de las congruenciasProposicin: Sea m > 1. Si a, b, c, d, k son enteros cualesquiera entonces se verifican las siguientes propiedades:1).2).3) ).

4) entonces: .5) Si entonces .6) Si entonces para todo entero positivo n.

Ejemplo: Tenemos , entonces

Ejemplo: Calcula el resto r de la divisin de 25743 por 13:Sabemos que , entonces

Luego el resto r es 12 (porque el resto r siempre satisface ).

SISTEMAS DE CONGRUENCIAS LINEALESSean , donde Estudiaremos ahora soluciones del sistema de congruencias lineales:

El sistema de congruencias

Tiene una nica solucin modulo y las dems soluciones son de la forma

Ejemplo 1: En el siglo I el matemtico chino Sun-Tsu estudi el siguiente problema: Encontrar un nmero natural que genera los restos 2,3 y 2 al dividirlo por 3,5 y 7 respectivamente. Esto equivale a encontrar tal que:

Paso1: Veamos lo primero si estamos en las hiptesis del Teorema.1)

2

Por tanto, estamos en las hiptesis del Teorema, esto implica que el sistema tiene solucin.Paso 2: Mtodo de clculo de la solucin general del sistema de congruencias:1) Calculamos una solucin particular de cada una de las ecuaciones: .

2) Calculamos . Definimos para .

.3) Resolvemos las ecuacionespara cada i = 1, 2, 3. Es decir:

Unas soluciones de estas son: = 2, = 1, = 1.4) Definimos.Calculamos el valor de :

5) La solucin general del sistema de congruencias es:.Por tanto,.6) Para calcular el menor nmero x0 [0, m) que verifica el sistema de congruencias damos valores a h:)...El nmero buscado es = 23.Luego:

TEOREMA DE FERMATTeorema: Si es un nmero primo que no divide al nmero a, entonces:

EL INVERSO MULTIPLICATIVOEl multiplicador modular inverso de un entero n mdulo p es un entero m tal que

Esto significa que es el inverso multiplicativo en el anillo de los enteros mdulo p. Es equivalente a

El multiplicador inverso de n mdulo p existe si y slo si n y p son coprimos, es decir si:.Si existe el multiplicador modular inverso de n mdulo p, se puede definir la operacin de divisin entre n mdulo p mediante la multiplicacin por el inverso.Ejemplo 2: Calcula el resto que se obtiene al dividir . El nmero 7 es primo y no divide 23, luego por el Teorema de Fermat

Por otra parte 2587 = 431 6 + 1. Por tanto

Esto implica que . As que existe un numero tal que:

Luego:

Finalmente el resto que se obtiene al dividir .Ejemplo 3: Resolver:

De (1) y (2)

De donde: . (4)De (4) y (3)

De donde: Solucin general:

Ejemplo 3: Resolver:

De (1) y (2)

De donde: . (4)De (4) y (3)

De donde: Solucin general:

Ejemplo 4: Hallar el resto de:

Primero:

Segundo:

De (4) y (5) tenemos:

Por lo tanto el resto es 56.Ejemplo 5:Hallar el inverso de a=47 en

Por el teorema de Fermat:

Es igual a ().El inverso es 31.Ejemplo 6: Hallar el inverso de a=47 en aplicando el algoritmo de Euclides.

Condicin para existe el inverso:

Aplicando el algoritmo de Euclides:

El inverso es 31.

Ejemplo 5: Hallar el resto de:

Por lo tanto:

Entonces:

El resto de cuyo resto es 3 al dividirlo en 11.