2.2: El Algoritmo de División

Una aplicación del Principio de Ordenamiento Bien que usaremos a menudo es el algoritmo de división.

Teorema$2.9$

Las probabilidades asignadas a eventos por una función de distribución en un espacio muestral están dadas por.

Prueba

Este es un ejemplo perfecto del tipo de prueba de existencia y singularidad. Primero debemos probar que los números$q$ y$r$ en realidad existen. Entonces debemos demostrar que si$q'$ y$r'$ son otros dos números de este tipo, entonces$q = q'$ y$r = r'\text{.}$

Existencia de$q$ y$r\text{.}$ Let

$$S = \{ a - bk : k \in {\mathbb Z} \text{ and } a - bk \geq 0 \}\text{.} \nonumber$$

Si$0 \in S\text{,}$ entonces$b$ divide$a\text{,}$ y podemos dejar$q = a/b$ y$r = 0\text{.}$ Si$0 \notin S\text{,}$ podemos usar el Principio de Ordenamiento Bien. Primero debemos demostrar que no$S$ está vacío. Si$a \gt 0\text{,}$ entonces$a - b \cdot 0 \in S\text{.}$ Si$a \lt 0\text{,}$ entonces$a - b(2a) = a(1 - 2b) \in S\text{.}$ En cualquier caso$S \neq \emptyset\text{.}$ Por el Principio Bien Ordenado,$S$ debe tener un miembro más pequeño, digamos$r = a - bq\text{.}$ Por lo tanto, Ahora$a = bq + r\text{,}$$r \geq 0\text{.}$ mostramos que$r \lt b\text{.}$ Supongamos que$r \gt b\text{.}$ Entonces

$$a - b(q + 1)= a - bq - b = r - b \gt 0\text{.} \nonumber$$

En este caso tendríamos$a - b(q + 1)$ en el set$S\text{.}$ Pero entonces$a - b(q + 1) \lt a - bq\text{,}$ lo que contradiría el hecho de que$r = a - bq$ es el miembro más pequeño de So$S\text{.}$$r \leq b\text{.}$ Since$0 \notin S\text{,}$$r \neq b$ y así$r \lt b\text{.}$

Singularidad de$q$ y$r\text{.}$ Supongamos que existen enteros$r\text{,}$$r'\text{,}$$q\text{,}$ y$q'$ tales que

$$a = bq + r, 0 \leq r \lt b \quad \text{and}\quad a = bq' + r', 0 \leq r' \lt b\text{.} \nonumber$$

Entonces$bq + r = bq' + r'\text{.}$ Supongamos que$r' \geq r\text{.}$ De la última ecuación que tenemos$b(q - q') = r' - r\text{;}$ por lo tanto,$b$ debemos dividir$r' - r$ y$0 \leq r'- r \leq r' \lt b\text{.}$ Esto es posible sólo si$r' - r = 0\text{.}$ Por lo tanto,$r = r'$ y$q = q'\text{.}$

Dejar$a$ y$b$ ser enteros. Si$b = ak$ para algún entero$k\text{,}$ escribimos$a \mid b\text{.}$ Un entero$d$ se llama un divisor común de$a$ y$b$ if$d \mid a$ y$d \mid b\text{.}$ El mayor divisor común de enteros$a$ y$b$ es un entero positivo$d$ tal que$d$ es un divisor común de$a$ y$b$ y si$d'$ es cualquier otro divisor común de$a$ y$b\text{,}$ luego$d' \mid d\text{.}$ escribimos$d = \gcd(a, b)\text{;}$ por ejemplo,$\gcd( 24, 36) = 12$ y$\gcd(120, 102) = 6\text{.}$ Decimos que dos enteros$a$ y $b$son relativamente primos si$\gcd( a, b ) = 1\text{.}$

Teorema$2.10$

Dejar$a$ y$b$ ser enteros no nulos. Entonces existen enteros$r$ y$s$ tal que

$$\gcd( a, b) = ar + bs\text{.} \nonumber$$

Además, el mayor divisor común de$a$ y$b$ es único.

Prueba

Let

$$S = \{ am + bn : m, n \in {\mathbb Z} \text{ and } am + bn \gt 0 \}\text{.} \nonumber$$

Claramente, el conjunto no$S$ está vacío; de ahí que por el Principio de Ordenamiento Bien se$S$ debe tener un miembro más pequeño, digamos$d = ar + bs\text{.}$ Afirmamos que$d = \gcd( a, b)\text{.}$ Escribe$a = dq + r'$ donde$0 \leq r' \lt d\text{.}$ Si$r' \gt 0\text{,}$ entonces

\ begin {align*} r'& = a - dq\\ & = a - (ar + bs) q\\ & = a - arq - bsq\\ & = a (1 - rq) + b (-sq)\ text {,}\ end {align*}

que está en$S\text{.}$ Pero esto contradiría el hecho de que$d$ es el miembro más pequeño de$S\text{.}$ Por lo tanto,$r' = 0$ y$d$ divide$a\text{.}$ Un argumento similar muestra que$d$ divide$b\text{.}$ Por lo tanto,$d$ es un divisor común de$a$ y$b\text{.}$

Supongamos que$d'$ es otro divisor común de$a$$b\text{,}$ y y queremos demostrar que$d' \mid d\text{.}$ si dejamos$a = d'h$ y$b = d'k\text{,}$ luego

$$d = ar + bs = d'hr + d'ks = d'(hr + ks)\text{.} \nonumber$$

Así que$d'$ hay que dividir$d\text{.}$ Por lo tanto,$d$ debe ser el único mayor divisor común de$a$ y$b\text{.}$

Corolario 2.11

Let$a$ y$b$ ser dos enteros que son relativamente primos. Entonces existen enteros$r$ y$s$ tal que$ar + bs = 1\text{.}$

El Algoritmo Euclidiana

Entre otras cosas, el Teorema 2.10 nos permite computar el mayor divisor común de dos enteros.

Ejemplo$2.12$

Vamos a calcular el mayor divisor común de$945$ y$2415\text{.}$

Solución

En primer lugar, observe que

\ begin {align*} 2415 & = 945\ cdot 2 + 525\\ 945 & = 525\ cdot 1 + 420\\ 525 & = 420\ cdot 1 + 105\\ 420 & = 105\ cdot 4 + 0\ texto {.} \ end {alinear*}

Revertiendo nuestros pasos,$105$$420\text{,}$$105$ divide divide$525\text{,}$$105$ divide$945\text{,}$ y$105$ divide$2415\text{.}$ Por lo tanto,$105$ divide ambos$945$ y$2415\text{.}$ Si$d$ fueran otro divisor común de$945$ y$2415\text{,}$ entonces$d$ también tendría que dividir$105\text{.}$ Por lo tanto,$\gcd( 945, 2415 ) = 105\text{.}$

Si trabajamos hacia atrás a través de la secuencia de ecuaciones anterior, también podemos obtener números$r$ y$s$ tal que$945 r + 2415 s = 105\text{.}$ Observe que

\ begin {alinear*} 105 & = 525 + (-1)\ cdot 420\\ & = 525 + (-1)\ cdot [945 + (-1)\ cdot 525]\\ & = 2\ cdot 525 + (-1)\ cdot 945\ & = 2\ cdot [2415 + (-2)\ cdot 945] + (-1)\ cdot 945\ & = 2\ cdot 2415 + (-5)\ cdot 945\ texto {.} \ end {alinear*}

Entonces$r = -5$ y$s= 2\text{.}$ Observe que$r$ y no$s$ son únicos, ya que$r = 41$ y también$s = -16$ funcionarían.

Para calcular$\gcd(a,b) = d\text{,}$ estamos usando divisiones repetidas para obtener una secuencia decreciente de enteros positivos es$r_1 \gt r_2 \gt \cdots \gt r_n = d\text{;}$ decir,

\ begin {align*} b & = a q_1 + r_1\\ a & = r_1 q_2 + r_2\\ r_1 & = r_2 q_3 + r_3\\ &\ vdots\\ r_ {n - 2} & = r_ {n - 1} q_ {n} + r_ {n}\\ r_ {n - 1} & = r_n q_ {n + 1}\ texto {.} \ end {alinear*}

Para encontrar$r$ y$s$ tal que$ar + bs = d\text{,}$ iniciemos con esta última ecuación y sustituimos los resultados obtenidos de las ecuaciones anteriores:

\ begin {alinear*} d & = r_n\\ & = r_ {n - 2} - r_ {n - 1} q_n\\ & = r_ {n - 2} - q_n (r_ {n - 3} - q_ {n - 1} r_ {n - 2})\\ & = -q_n r_ {n - 3} + (1+ q_n q_ {n-1}) r_ {n - 2}\\ &\ vdots\\ & = ra + sb\ texto {.} \ end {alinear*}

El algoritmo que acabamos de usar para encontrar el mayor divisor común$d$ de dos enteros$a$ y$b$ y para escribir$d$ como la combinación lineal de$a$ y$b$ se conoce como el algoritmo euclidiano.

Números primos

Dejar$p$ ser un entero tal que$p \gt 1\text{.}$ Decimos que$p$ es un número primo, o simplemente$p$ es primo, si los únicos números positivos que dividen$p$ son$1$ y$p$ en sí mismos. Se dice$n \gt 1$ que un entero que no es primo es compuesto.

Lema$2.13$. Euclid

Dejar$a$ y$b$ ser enteros y$p$ ser un número primo. Si$p \mid ab\text{,}$ entonces cualquiera$p \mid a$ o$p \mid b\text{.}$

Prueba

Supongamos que$p$ no divide$a\text{.}$ Debemos demostrar que$p \mid b\text{.}$ ya que$\gcd( a, p ) = 1\text{,}$ existen enteros$r$ y$s$ tal que$ar + ps = 1\text{.}$ Así

$$b = b(ar + ps) = (ab)r + p(bs)\text{.} \nonumber$$

Ya que$p$ divide tanto como$ab$ a sí mismo,$p$ debe dividir$b = (ab)r + p(bs)\text{.}$

Teorema$2.14$. Euclid

Existe un número infinito de primos.

Prueba

Vamos a probar este teorema por contradicción. Supongamos que sólo hay un número finito de primos,$p_1, p_2, \ldots, p_n\text{.}$ digamos Let$P = p_1 p_2 \cdots p_n + 1\text{.}$ Then$P$ debe ser divisible por algunos$p_i$ para$1 \leq i \leq n\text{.}$ En este caso,$p_i$ debe dividir$P - p_1 p_2 \cdots p_n = 1\text{,}$ lo que es una contradicción. Por lo tanto, o bien$P$ es primo o existe un número primo adicional$p \neq p_i$ que divide$P\text{.}$

Teorema$2.15$. Fundamental Theorem of Arithmetic

Dejar$n$ ser un entero tal que$n \gt 1\text{.}$ Entonces

$$n = p_1 p_2 \cdots p_k\text{,} \nonumber$$

donde$p_1, \ldots, p_k$ son primos (no necesariamente distintos). Además, esta factorización es única; es decir, si

$$n = q_1 q_2 \cdots q_l\text{,} \nonumber$$

entonces$k = l$ y los$q_i$ 's son solo los$p_i$' s reorganizados.

Prueba

Singularidad. Para mostrar singularidad utilizaremos la inducción en$n\text{.}$ El teorema es ciertamente cierto$n = 2$ ya que en este caso$n$ es primo. Ahora supongamos que el resultado se mantiene para todos los enteros de$m$ tal manera que$1 \leq m \lt n\text{,}$ y

$$n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l\text{,} \nonumber$$

donde$p_1 \leq p_2 \leq \cdots \leq p_k$ y$q_1 \leq q_2 \leq \cdots \leq q_l\text{.}$ Por Lema 2.13,$p_1 \mid q_i$ para algunos$i = 1, \ldots, l$ y$q_1 \mid p_j$ para algunos$j = 1, \ldots, k\text{.}$ Dado que todos los$p_i$'s y$q_i$'s son primos,$p_1 = q_i$ y$q_1 = p_j\text{.}$ Por lo tanto,$p_1 = q_1$ desde$p_1 \leq p_j = q_1 \leq q_i = p_1\text{.}$ Por la hipótesis de inducción,

$$n' = p_2 \cdots p_k = q_2 \cdots q_l \nonumber$$

tiene una factorización única. Por lo tanto,$k = l$ y$q_i = p_i$ para$i = 1, \ldots, k\text{.}$

Existencia. Para mostrar la existencia, supongamos que hay algún entero que no se puede escribir como producto de primos. $S$Sea el conjunto de todos esos números. Por el Principio de Bien Ordenado,$S$ tiene un número menor, digamos$a\text{.}$ Si los únicos factores positivos de$a$ son$a$ y$1\text{,}$ luego$a$ es primo, lo cual es una contradicción. De ahí,$a = a_1 a_2$ dónde$1 \lt a_1 \lt a$ y$1 \lt a_2 \lt a\text{.}$ Ni$a_1\in S$ ni$a_2 \in S\text{,}$ desde que$a$ es el elemento más pequeño en$S\text{.}$ So

\ begin {align*} a_1 & = p_1\ cdots p_r\\ a_2 & = q_1\ cdots q_s\ texto {.} \ end {alinear*}

Por lo tanto,

$$a = a_1 a_2 = p_1 \cdots p_r q_1 \cdots q_s\text{.} \nonumber$$

Entonces$a \notin S\text{,}$, que es una contradicción.

Nota Histórica

Los números primos fueron estudiados por primera vez por los antiguos griegos. Dos resultados importantes de la antigüedad son la prueba de Euclides de que existe un número infinito de primos y el Tamiz de Eratóstenes, un método para calcular todos los números primos menos de un entero positivo fijo$n\text{.}$ Un problema en la teoría de números es encontrar una función$f$ tal que$f(n)$ sea primo por cada entero$n\text{.}$ Pierre Fermat (1601? —1665) conjeturó que$2^{2^n} + 1$ era primo para todos$n\text{,}$ pero más tarde fue mostrado por Leonhard Euler (1707—1783) que

$$2^{2^5} + 1 = 4{,}294{,}967{,}297 \nonumber$$

es un número compuesto. Una de las muchas conjeturas no comprobadas sobre los números primos es la Conjetura de Goldbach. En una carta a Euler en 1742, Christian Goldbach declaró la conjetura de que cada entero par con la excepción de$2$ parecía ser la suma de dos primos:$4 = 2 + 2\text{,}$$6 = 3 + 3\text{,}$$8 =3 + 5\text{,}$$\ldots\text{.}$ Aunque la conjetura ha sido verificada para los números arriba a través de$4 \times 10^{18}\text{,}$ ella aún no ha sido probado en general. Dado que los números primos juegan un papel importante en la criptografía de clave pública, actualmente existe un gran interés en determinar si un número grande es primo o no.