domingo, 8 de febrero de 2009

11.-Congruencias

En muchos problemas, la idea central para encontrar la solución es considerar los residuos de los números que se relacionan al dividirse entre otro número fijo. Esto nos llevara a desarrollar la noción de congruencias de números, la cual unifica y extiende muchos resultados desarrollados hasta ahora.
Congruencias
Definición. Sean a y b dos números enteros, y sea m un entero distinto de cero. Decimos que a es congruente a b módulo m si m divide a b-a. Esto lo escribimos como
ab (mod m) ⇔ m | b-a.
A grandes rasgos lo que decimos es que dos números a y b son congruentes (equivalentes, iguales) módulo m si ambos son de la forma mk +r con una misma r, esto es, si dejan el mismo residuo al dividirse por m . Para decir que a no es congruente a b modulo m escribimos

Ejemplos.
8 ≡ 23 (mod 5) puesto que 5 |(23-8)= 15 Notemos que tanto 23 y 5 son de la forma 5k +3.
36≡0 (Mod 12) puesto que 12 |(36-0)=36.
-22≡ 6 (mod 7) dado que 7|(6 –(-22))= 28.
Las ventajas de usar congruencias es que estas comparten muchas propiedades con la igualdad (de ahí que sea apropiado decir que los números son “congruentes”) ;
Si a,b,c,d,n son enteros y n ≠ 0 entonces :
I.-. a ≡ a (mod n)
II.- Si a ≡ b (mod n ) entonces b ≡ a (mod n)
III.- Si a ≡ b (mod n) y b ≡ c (mod n) entonces a ≡ c (mod n).
IV.-Si a ≡ b (mod n) entonces a +x ≡ b + x (mod n) para todo entero x
V.-Si a ≡ b (mod n) y c ≡d (mod n) entonces ( a +c)≡ (b +d) (mod n)
VI.- Si a ≡ b (mod n) entonces ax ≡ bx (mod n) para todo entero x
VII.-Si a ≡ b(mod n) y c ≡ b (mod n) entonces ac ≡ bd (mod n)
VIII.-Si a ≡ b (mod n) entonces ax ≡bx (mod n) para x ∈Z+
IX.- Si f(x) es un polinomio de coeficientes enteros, entonces a ≡b (mod n) implica que f (a) ≡ f(b) (mod n)
X.-Si a ≡b (mod n) y d |n entonces a ≡b (mod d).
XI.- Si a ≡b (mod m), a ≡b (mod n)y (m,n) = 1 entonces a ≡b (mod mn)
XII.-a ≡0 (mod n) si y solo si n| a.
El teorema anterior se prueba a partir de los teoremas de divisibilidad. Como ejemplo a ≡b (mod n) entonces a+x ≡ b+x (mod n).
Prueba a ≡b (mod n) quiere decir que n |(b-a). Pero b-a = b +x+a-x=(b+x) - (a+x) por lo que n |(b+x) –(a+x), lo que significa que a+x ≡b+x (mod n).
Hay sin, embargo, una propiedad que la igualdad no comparte con la congruencia. Si ax =bx , con x no igual a cero podemos decir que a =b , pero con las congruencias no. Por ejemplo 10×6 ≡ 4×6 (mod 4) pero
Es decir, no se permite cancelar factores en las congruencias. El siguiente teorema nos proporciona condiciones para poder efectuar tal operación.
Teorema 11.2 Sean a,b enteros. Entonces


II.-Si ax ≡ bx (mod n) y (n,x)=1 entonces a ≡ b(mod n ).
III.- a≡ b (mod nk) para k =1,2,…r si y sólo si a≡ b (mod [n1,n2,...nr]).
Prueba. Si ax ≡ bx (mod n) entonces bx-ax= nz para algún entero z. Entonces

Y por tanto


Pero
Por lo que

divide a b-a, es decir,
De este modo hemos probado que ax ≡ bx (mod n)implica
Ahora, supongamos que
Esto quiere decir que
De donde (b-a)(n,x)=nz, es decir ,n |(b-a)(n,x). Pero x es un múltiplo de (n,x) lo cual nos dice que n |(b-a)x. Se sigue que ax ≡ bx (mod n).Ya hemos probado el primer inciso, el segundo es una aplicaciòn directa del primero.Para probar el tercero, notemos que ni| (b-a) nos dice que (b-a) es un múltiplo comùn de todas las ni, por lo que [n1,n2,...nr ] |b-a.Ya queda probado que a ≡b (mod nk) (k=1...r) implica a≡ b(mod[n1,n2,...nr])
Para el regreso , notemos que nk es un divisor de [n1,n2,...nr], por lo que a ≡ b (mod [n1,n2,...nr )]implica a≡ b (mod p)
Un caso muy especial y útil del teorema anterior es el siguiente resultado:
Teorema 11.3 Sea p un número primo y t un número que no es divisible entre p. Si at ≡ bt (mod p) entonces a ≡b (mod p).
Para ilustrar el uso de congruencias al resolver problemas, demostraremos el siguiente teorema:
Teorema 11.4. Si a es impar, entonces a2-1 es divisible entre 8.
Prueba .Si a es impar, entonces alguna de las siguientes proposiciones es cierta.
a ≡ 1 (mod 8)
a ≡ 3 (mod 8)
a ≡ 5 (mod 8)
a ≡ 7 (mod 8)
Por otro lado 12 ≡ 1 (mod 8),32 ≡ 1 (mod 8),52≡1 (mod 8), 72 ≡1 (mod 8) , por lo que en cualquier caso, a2 ≡ 1 (mod 8), lo que es lo mismo que decir a2-1 es divisible entre 8.
Una prueba ligeramente distinta:
Prueba. Supongamos que a es impar es decir , a≡ 1 (mod 2). Entonces
a2 ≡ 12 ≡1 (mod 2).
Por otro lado, si a2-1 no fuese divisible entre 8 tendríamos

Y como 2 8 esto implicaría que
Esto es una contradicción , por lo que concluimos que a2-1 debe ser divisible entre 8.
Los teoremas principales sobre divisibilidad pueden formularse con congruencias. El teorema 10.15 se enuncia:
Teorema 11.5 Si p es primo, ab ≡ 0 (mod p) y

entonces b ≡0 (mod p).
El teorema anterior es el análogo (para la igualdad) de la afirmación ab = 0 entonces a=0 o b =0 . Es importante recalcar que el módulo debe ser primo. Como ejercicio, encontrar un contraejemplo cuando el número no es primo.
El teorema que dice que si a = bq +r entonces (a,b) = (b,r) puede rescribirse como
Teorema 11.6 Si x ≡y (mod n) entonces (x,n) =(y,n)
Para terminar , es importante recalcar que aunque los resultados de congruencia se puedan rescribir como resultados de divisibilidad y viceversa, las congruencias generalmente permiten realizar pruebas más claras y concisas, además de que familiarizarse con ellas permite entender resultados más profundos y poderosos. Por esto es que se recomienda especialmente que en lo posible se intente usar congruencias en vez de divisibilidad para resolver los problemas.

jueves, 5 de febrero de 2009

10.4 Ecuaciones lineales diofantinas.

Una ecuación lineal diofantina es una ecuación de la forma
ax +by = c
donde a,b,c son números enteros y x, y son variables que toman valores enteros.
Veamos algunos ejemplos:
La ecuación 4x-6y=5 no tiene soluciones enteras, ya que sin importar el valor de x y y el lado izquierdo siempre es un número par, mientras que el derecho es un número impar.
La ecuación 4x-6y =2 tiene solución , ya que (4,6)=2 y entonces existe una combinación lineal de 4 y 6 que es igual a dos.
La ecuación 4x- 6y = 10 tiene solución . Si x0 y y0 son solución de 4x –6y =2 entonces 5x0 y 5y0 son solución de 4x- 6y = 10.
Podemos generalizar los últimos dos ejemplos. Si d = (a,b) sabemos que existen enteros x0, y0 tales que ax0 + by0 = d, es decir, la ecuación.
ax + by =(a,b)
Siempre tiene solución.
Más aún si c es un múltiplo de d (por ejemplo c =kd) entonces
a (kx0) + b(ky0) = k (ax0 +by 0)= kd =c
es decir, una ecuación de la forma
ax +by = k (a,b)
siempre tiene solución. Esto constituye el primer teorema de la sección.
Teorema 10.19 Si (a,b)| c entonces la ecuación lineal diofantina
Ax +by = c
Siempre tiene solución entera.
Un corolario muy importante es:
Corolario 10.20Si a y b son primos relativos, la ecuación ax +by =c siempre tiene solución entera.
Ahora nos preguntamos: ¿Habrá alguna ecuación lineal ax +by =c que tenga solución y en donde (a,b) no divida a c?
Vamos a restringirnos únicamente al caso en que c es positivo, puesto que si u y v son solución de ax + by = c entonces –u y –v son solución de ax +by = -c.
Por un lado, como (a,b) es la mínima combinación lineal positiva si c = 1,2,...,(a,b)-1 la ecuación ax +by = c no puede tener solución. De esta manera, si existe una solución, necesariamente c ≥ (a,b).
Supongamos que la ecuación ax +by = c tiene como solución a x1 y y1 , que d =(a,b), no divide a c, y sean x0 y y0 una solución para ax + by =d. De esta manera tenemos
ax1 +by1 =c
ax0 +by0 =d
Por el algoritmo de la división tenemos c = md +r con 0 < r < c puesto que d no divide a c. Entonces:
ax+ by = md +r
= m (ax0 + by0 ) +r
=a (mx0) +b (my0)+r
y por tanto
a(x1- mx0) + b (y1-my0) = r.
¡Lo anterior es una contradicción! Puesto que tenemos una combinación lineal positiva de a y b igual a r y 0 < r < d, eso contradice que d era la combinación lineal mínima positiva (es decir, d no era el máximo común divisor). La contradicción surgió de suponer que ax + by =c podía tener solución aunque (a,b) no dividiera a c, por lo que hemos demostrado el siguiente teorema.
Teorema 10.21La ecuación lineal diofantina
Ax +by = c
Tiene solución si y solo si (a,b) |c

Ya estamos en condición de determinar si una ecuación dada tiene solución o no, ahora nos interesa determinar cuales son las soluciones. Supongamos que la ecuación ax +by =c tiene solución, es decir c = kd donde d= (a,b).
Si u y v son una solución de ax +by =d, entonces x 0 =k y y0 =kv son una solución de ax + by =c. De este modo podemos encontrar al menos una solución a la ecuación . Sea x1, y1 otra solución. Como x1x0 existe un entero r tal que x1 =x0 +r. Sustituyamos en la ecuación.

a (x0 +r) +by 1 = c =ax0 +by0
Y al simplificar obtenemos
Un argumento simétrico muestra que si y1 = y0-s entonces Una vez más sustituimos en la ecuación

Y al simplificar llegamos a bs-ar= 0. Sean
Entonces (a`,b`) = 1 y (r`,s)`=1 Además
b`s`- a`r`=0.
Esto implica que b`s` =a`r`. Además, la coprimalidad implicara que r’ =b’ y s`=a`.Por tanto tenemos que,
Así toda solución es de la forma
Donde t es un entero que satisface la relación
Para terminar, notemos que

¡Esto quiere decir que todo entero satisface la relación anterior! En otras palabras , los números de la forma x =x0 +bt/d y y=y0-at/d siempre son soluciones y además toda pareja de números que es de esa forma es solución.

Para recapitular todo el trabajo desarrollado en esta sección establecemos el teorema principal.
Teorema 10.22 (Resolución de la ecuación lineal de congruencia.)
La ecuación ax +by =c tiene solución si y solo si d = (a,b) divide a c. Además , las soluciones son los números de la forma
Donde x0 y y0 son una solución particular y t es cualquier número entero.

martes, 3 de febrero de 2009

10.3 Mínimo común múltiplo.

Definición 10.6 Si a,b son enteros (no ambos cero), entonces el mínimo común múltiplo de a y b es el menor entero positivo que es múltiplo tanto de a como de b. Este número lo denotamos con [a,b].
Podemos extender la definición a un conjunto a1,a2,a3,...an de enteros que no sean todos cero, definiendo su mínimo común múltiplo como el menor entero positivo que es múltiplo de todos ellos.
Estamos interesados en buscar alguna relación entre el máximo común divisor y el mínimo común múltiplo. Escojamos dos números, digamos
a =252=22 ×32×7 y b = 735 = 3×5×72
Para facilitar el análisis, podemos “completar” los factores para que los primos que aparecen en ambas expresiones sean los mismos:
a = 252 = 22×32×50×71
b = 735= 20×31×51×71
Si calculamos manualmente (a,b) y [a,b] obtenemos
(252,735 ) = 21 = 20 ×31 × 51×71
[252,735] = 8820 = 22 ×32 × 51×71
Podemos ver que los primos que aparecen en ambas expresiones son los mismos que los que aparecen en las factorizaciones (acompletadas ) de los números variando únicamente los exponentes. Esto lo enunciamos como sigue:
Teorema 10.17 Sea p un número primo.
El exponente con el que p aparece en (a,b) es el mínimo de los exponentes con los que aparece en las factorizaciones de a y n.
El exponente con el que p aparece en [a,b] es el máximo de los exponentes con los que aparece en las factorizaciones de a y b.
El teorema anterior puede deducirse del Teorema fundamental de la aritmética y de las definiciones de máximo común divisor y mínimo común múltiplo. Ya tenemos la herramienta necesaria para demostrar la siguiente relación, cuya prueba se deja como ejercicio.
Teorema 10.18 Si a,b son enteros, entonces
ab= (a,b) [a,b] .

lunes, 2 de febrero de 2009

10.2 Máximo común divisor.

Definición 1.3 Dados dos números a y b no negativos y no ambos cero el mayor número que divide a los dos se denomina máximo común divisor de a y b. Denotamos a este número como(a,b). En general, dado un conjunto de enteros no negativos y no todos cero{a1,a2...an}, definimos a su máximo común divisor (a1,a2....an)como el mayor entero positivo que los divide a todos.
La definición anterior implica que (a,b) siempre es positivo. Algunas propiedades básicas son:
1.-(a,1) =1 para toda a
2.-(a,a) =a para toda a.
3.-(a,0) =a para toda a.
4.-(a,b) = (b,a).
5.-(a,b) = (b, a-b).
Para probar la última propiedad notemos que si un número divide a a y b, divide a a-b por lo que es un divisor común de b y a-b. A la inversa si divide a b y a a-b divide a (a-b)+b=a. Esto implica que los divisores comunes de a y b son los mismos que los de b y a-b y por tanto el mayor de ambos conjuntos es el mismo número.
Esta propiedad también nos permite calcular el MCD de dos números dados. Por ejemplo, sean a= 26, b = 10. Entonces
(26,10)=(10,16)=(16,10)=(10,6)=(6,4)=(4,2)=2
Estas cuentas se pueden acelerar mediante el uso del algoritmo de la división. Si a =bq + r con o ≤ r < b (entonces (a,b)=(b, a-bq)= (b,r) se deja la prueba de estas igualdades al lector. Así como 26 = 10 × 2 +6 el cálculo anterior se convierte en:
(26,10)= (10,6) =(6,4) =(4,2) = 2.
El proceso arriba mencionado se conoce como algoritmo de Euclides.

(Teorema 10.7) Si g es el máximo común divisor de a y b, entonces existen enteros u,v tales que g =au +bv..
Prueba Consideremos el conjunto de todos los números de la forma ax +by con x,y enteros (el conjunto de combinaciones lineales de a y b). De este conjunto escojamos el menor enteo positivo y llamémosle d. Sean u,v tales que d = au +bv. Si



aplicamos el algoritmo de la división a = dq +r con 0 < r < d. Pero
r=a – dq=a- (au +bv)q =a(1-qu) +b (-qv)
Significa que r es positivo, está en el conjunto y es menor a d. Esto es una contradicción ya que habíamos supuesto que d era el menor número positivo del conjunto. Por tanto. d | a. Por un argumento similar obtenemos que d |b.
Ahora sea g el máximo común divisor de a y b. Como g |a y g | b, g | au +bv. Si g ≠ d tendríamos que g < d, es decir g no era el mayor de todos los divisores comunes de a y b, lo cual es una contradicción, concluimos pues ,que g=d.


Corolario 10.8 El máximo común divisor de a y b es la combinación lineal positiva más pequeña de ambos.
Corolario 10.9 = Si (a,b)=1 , la ecuación ax + by =1 tiene solución entera.
Prueba . Hállese los enteros x, y para los que (a,b) = ax +by.
Corolario 10.10 (a, a +a) =1.
Prueba (-1) × a +(1) × (a-1)=1. Entonces 1 es la combinación lineal positiva más pequeña y por lo tanto igual a (a,a +1).
Teorema 10.11 (am,bm) = m(a,b).
Prueba. (am,bm) es el menor valor positivo de amx + bmy = m (ax +by). Esto es lo mismo que m veces el menor valor positivo de ax +by el cual es a,b).
Corolario 1.12 Si d = (a,b) entonces








Otra manera de caracterizar l máximo común divisor de a y b es como sigue. Supongamos que d es cualquier divisor común de a y b. Entonces d divide a cualquier combinación lineal de a y b. , en particular divide a la menor positiva es decir, es decir divide a (a,b). Y como a |b implica a ≤ b, (a,b) es el único número con esta propiedad. Lo cual prueba el siguiente teorema.
Teorema 10.13 El máximo común divisor de a y b es el único entero positivo que es divisible entre cualquier número que divida tanto a a como a b.
Definición 10.4 Dados dos números a, b decimos que son primos relativos, si (a,b)= 1. En general, decimos que un conjunto (x1,x2,...xn) de enteros son primos relativo entre si cuando (x1,x2,...xn)=1.
Definición 10.5 dado un conjunto {x 1,x,2...xn } de enteros, decimos que son primos relativos dos a dos si (xi,xj)=1 para cualquier pareja xi,xj.
Ser primos relativos entre sí y ser primos relativos dos a dos no es lo mismo. Por ejemplo, los números 4,6,9 son primos relativos entre sí puesto que (4,6,9)= 1, pero no son primos relativos dos a dos ya que (4,6)=2.
A continuación se enuncia no de los resultados más usados en relación al máximo común divisor y a la vez uno de los más fuertes, ya que será pieza clave en la demostración del Teorema fundamental de la aritmética.
Teorema 10.14 Si c |ab y (c,a)=1 entonces c |b.
Prueba. Como c |ab y c| bc, c |(ab, bc) .Pero (ab,bc)= b (a,c)= b. Por tanto, c| ab.
Un caso muy especial se obtiene cuando c es primo.
Teorema 10.15
Si p es primo y divide a ab, y p no divide a a entonces p divide a b.
Prueba sea d = (a,p). Entonces d |p por lo tanto d solo puede ser 1 o p . Como
Tenemos que d≠ p y por lo tanto d =1. Aplicando el teorema anterior llegamos a que p| b.
Teorema 10.16 (Teorema fundamental de la aritmética) Todo número se puede factorizar de manera única como producto de primos.
Prueba. Ya hemos probado que todo número se puede factorizar en primos, y nos resta probar la unicidad de esta factorización. Sean



dos factorizaciones distintas donde por conveniencia suponemos que los primos aparecen listados en orden creciente. Cada pi divide a n y por tanto a alguna qj(aplicando varias veces el argumento anterior). Pero un primo divide a otro si y solo si son el mismo. Entonces cada pi es alguna qj, y por un argumento similar cada qj es una pi, esto implica que p i=qi para cada i.
Falta ver que las potencias son las mismas, pero si por ejemplo aj < b j dividimos a ambos lados entre

y del lado derecho nos sobran factores pj que dividen al lado izquierdo y son iguales a alguna pk, lo cual es imposible. Una contradicción similar elimina el caso aj > bj.
Así podemos concluir que las factorizaciones son las mismas.
Ahora, retomemos el problema de expresar el máximo común divisor de dos números como combinación lineal de los mismos. Probamos que siempre es posible escribir (a,b) en la forma au + bv donde u y v son enteros y hemos usado este hecho en diversas pruebas, aunque no mencionamos de manera explícita como hallar esos números. El procedimiento para hallar los coeficientes a y b se basa en el algoritmo de la división y más que escribir explícitamente el proceso, lo ilustraremos con un ejemplo.
Así, deseamos expresas (124,44) como combinación lineal de 124 y 44.
124 = 44 × 2 +36
44 = 36 × 1 + 8
36 = 8 ×4 +4
8 = 4 × 2 +0
Entonces (124,44) =4. Despejamos el 4 y empezamos a sustituir de la siguiente manera:
4 = 36 -(4×8)
=36-4(44-36)
=5 × 36 – (4 ×44)
=5 (124- )44×2)) –( 4 × 44)
= (5 ×124) – 14 ×44
Así, 4 = (124 × 5) –(44 ×14). Comparemos esto con el proceso para calcular únicamente (124,44)(versión rápida):
(124,44)=(44,36)= (36,8)=(8,4)=(4,0)=4
y notemos que los números que aparecen son los mismos que aparecen al desarrollar todo el algoritmo de la división, con lo que comprobamos que el algoritmo de Euclides es en realidad la aplicación sucesiva del algoritmo de la división.
Vale la pena recalcar que los coeficientes que se encuentran no son los únicos, de hecho hay una infinidad de soluciones. Para este caso en particular notamos que:

Cada entero t nos genera una combinación distinta.

domingo, 1 de febrero de 2009

Divisibilidad

Conceptos básicos
El concepto fundamental en el que estaremos interesados ahora, será el de divisibilidad, por ello introduciremos la siguiente definición .
Definición 1.1 Sean a y b dos números enteros. Decimos que a divide a b (lo que simbolizamos con a|b) si existe un entero c tal que
b = ac. Esto equivale a decir que b es múltiplo de a , o a que la división b ÷a no deja residuo.
Si a no divide a b, escribimos:



Esto es lo mismo que decir que la división b ÷a deja residuo.
Ejemplos:
3|12 pues 12 =4×3
4|20 ya que si c=5, 20= 4c.
3|0 dado que 0=3c cuando c=0




Para cualquier entero a, a+1 | a2 -1, ya que a 2 -1 =(a +1) × k con k = a-1.
De la definición podemos derivar ciertas propiedades básicas:
1.Todo número se divide a sí mismo: a | a
2.Si a | b, entonces a |-b. Como 4 |8 (8=4×2), 4|-8. (pues -8=4×(-2)).
3.Si a | b, entonces a |bc para todo entero c. (4|12, entonces 4|12×5).
4.Si a y b son positivos y a |b, entonces a≤ b.
5.Si a | b y b | c entonces a | c. Ejemplo: 2|10 y 10 |30, entonces 2 |30.
Si a |b y a |c entonces a | (b+c).Así 2|4 y 2|6 implica 2 | (4+6)
La prueba de la última propiedad es típica de las pruebas de problemas de divisibilidad, así que se incluye para tener un modelo.
Prueba. Si a | b y a |c, entonces existen números enteros m y n tales que b =am y c= an. Entonces b+c = am+ an = a (m+n). Como b + c = ak cuando k = (m+n), la definición de divisibilidad nos dice que a | b +c. La prueba queda terminada.
La prueba anterior puede extenderse a varios sumandos:
Teorema 10.1 Si a |x1 ,a |x2, a |x3,... a |xn, entonces
A | (c1x1 +c2x2+c3x4+...+cnxn)
Para cualquier combinación de enteros, c1,c2,c3,...cn.

Dados a y b, un número de la forma ax + by se denomina una combinación lineal de a y b. En general dados x1,x2,...,xn, un número de la forma u1x1 + u2x2+...+unxn se conoce como una combinación lineal de los números x1,x2,....xn. Entonces el teorema anterior lo enunciamos: “Si un número divide a un conjunto de enteros, divide a cualquier combinación lineal de los mismos.”

Por ejemplo dado que 3 |6 , 3|12 y 3|15, aplicando el teorema anterior con c1=5, c2= -7, c3=2, deducimos que 3 | (6 ×5 + 12× (-7) +15 ×2 )
El concepto de divisibilidad puede generalizarse de la siguiente manera:
Teorema 10.2 (Algoritmo de la división)Sean a y b dos enteros con b > 0. Entonces existen enteros únicos c y r tales que a = bc+r y 0≤ r < b.
Lo importante a notar es que el residuo es positivo y cumple o ≤ r < b, y si



Entonces 0 < r < b. Básicamente, el entero c es el cociente de la división a÷b y r es el residuo.
Ejemplos:A= 12, b= 5. a=b×2+2.
A= 38, b= 8. a=b×4+6.
A= 20, b= 4. a=b×5+0.
A= 7, b= 10. a=b×0+7.
A= -15, b= 4. a=b×(-4)+1.
A= 18, b= -5. a=b×(-3)+3.
A= -14, b= -3. a=b×5+1.

Este algoritmo adquirirá mayor importancia en la siguiente sección.
Definición 10.2
Un número positivo se llama número primo si tiene solo dos divisores positivos distintos. Un número mayor a 1 que no es primo se denomina compuesto.
Teorema 10.3
Todo número mayor a 1 es divisible por algún primo.
Prueba. Sea n >1. Supongamos que no es divisible por ningún primo. En particular, n mismo no puede ser primo pues seria divisible entre si mismo. Como n no es primo, tiene algún divisor positivo d1 distinto de 1 y n, es decir 1 < d1 < n. Pero d1 no puede ser primo porque dividiría a n. Entonces existe un d2 que divide a d1 tal que 1 < d2 < d1 < n. Como d2 no puede ser primo porque divide a n, repetimos el argumento con d2 para obtener un d3 tal que 1 < d3 < d2 < d1 < n. Como d3 no puede ser primo existe un d4 que divide a d3 y así sucesivamente. Esto lleva a una contradicción pues no es posible continuar indefinidamente este proceso ya que entre 1 y n solo hay un número finito de términos. Por tanto n debe ser divisible entre algún primo.
Este tipo de pruebas se conoce como por descenso infinito y se basa en que si la condición pedida no se cumple se crea una sucesión infinita decreciente de elementos positivos, lo cual es imposible porque los enteros positivos tienen elemento mínimo. Las pruebas por descenso infinito fueron ampliamente usadas por Fermat.
El teorema anterior será usado en muchas pruebas en la siguiente forma “Si n es un número compuesto , hay un primo p que lo divide”.
Sea n un entero mayor a 1. Si n es primo, es igual a sí mismo. Si no es primo existe un primo p1 que lo divide y entonces p = p1n1. Si n1 es primo, n es igual a un producto de primos, de lo contrario existe un primo p2 que divide a n1 y así p=p1p1n2. Si n2 es primo, n es igual a un producto de primos, en caso contrario existe un primo p3 que lo divide. Continuamos aplicando este argumento y construimos una sucesión n1,n1,n3... decreciente de enteros positivos que debe terminar, es decir en algún momento nk es un número primo. De esta manera ya probamos el siguiente teorema:
Teorema 10.4 Todo número mayor a 1 puede escribirse como producto de primos.
Es decir, un número n> 1 puede escribirse de la forma:

Donde cada pj es un número primo.
Por ejemplo 12=22×3, 60=22×3×5, 101=101,99=32×11. Ahora bien, al igual que 12= 2×6=3×4 tiene varias factorizaciones, nada nos garantiza que un número dado no se pueda factorizar de maneras diferentes en producto de primos (sin importar el orden). Pero después probaremos que para cada número dado la factorización en primos sí es única. Así podemos establecer el siguiente teorema (aunque la prueba de la unicidad la posponemos hasta tener las herramientas necesarias).
Teorema 10.5 (Teorema fundamental d la aritmética)Todo número se puede factorizar de manera única como producto de primos.
Para finalizar la sección probaremos uno de los resultados clásicos de la teoría de los números y que fue establecido hace cerca de 2000 años.
Teorema 10.6 (Euclides) Hay una cantidad infinita de números primos.
Prueba. Supongamos que hay una cantidad finita de números primos y sea p1,p2,...pn la lista de todos ellos. Consideremos el número p1×p2×... ×pn+1. Como ese número es mayor a 1 hay un primo que lo divide. Sea p tal que p | p1×p2×... ×np+1. Como p | p×p2×... ×pn+1 se sigue que p |1 , lo cual es imposible. Concluimos que debe existir una cantidad infinita de primos.