Algoritmo de la división

Contenido

Algoritmo de la división#

Introducción#

En este capítulo vamos a ver la definición de divisibilidad, la cual es un concepto fundamental en la teoría de números. Este concepto es la clave angular sobre la que se construyen conceptos como el máximo común divisor, los números primos y compuestos entre otros. Nos permite analizar las relaciones entre los números enteros y resolver una amplia variedad de problemas.

Pensemos en un problema sencillo de repartición. Si queremos repartir \(20\) manzanas entre \(5\) personas y que cada persona tenga la misma cantidad de manzanas, la repartición sería exacta y cada persona recibiría \(4\) manzanas.

Si cambiamos un poco el problema anterior, ¿Podríamos repartir \(20\) manzanas entre \(6\) persona y que cada persona tenga la misma cantidad de manzanas?
La respuesta es que no. Si queremos que todas las personas tengan la misma cantidad de manzanas, tendríamos que dar a cada persona \(3\) manzanas pero nos sobrarían \(2\) manzanas por asignar. Lo anterior nos lleva a pensar en los términos cociente y residuo los cuales aparecen en el algoritmo de la división.

Enunciaremos y demostraremos el teorema del algoritmo de la división, que tradicionalmente es llamado algoritmo, pero no nos presenta ningún algoritmo para encontrar el cociente y el residuo. Lo que si nos enuncia es que estos valores existen y son únicos. Para poder demostrar el algoritmo de la división necesitamos el principio del mínimo o del buen orden si necesitas recordar o profundizar en este, puedes revisar el curso Álgebra Superior II.

Divisibilidad#

La divisibilidad es un concepto fundamental en la teoría de números. Podemos encontrar varias expresiones que hacen referencia a este concepto tales como, un número \(a\) es múltiplo de \(b\) o que un número \(b\) es factor de \(a\), pero la mayoría de las ocasiones usaremos que \(a\) divide a \(b\).
Veamos la definición formal de ser divisible.

Definición 2 (Divisibilidad)

Sean \(a\) y \(b\) enteros. Decimos que \(a\) divide a \(b\) si existe un entero \(q\) tal que \(a = bq\).

Si \(a\) divide a \(b\), usaremos la notación \(a|b\) y si \(a\) no divide a \(b\), usaremos la notación \(a \nmid b\).

Ejemplo 9

Encuentra todos los divisores positivos de \(12\).

Solución.

Utilicemos la definición de divisibilidad y veamos qué factores dividen al número \(12\).

\[\begin{align*} 12 &= 12\cdot 1,\text{ por lo tanto 12 divide a 12.} \\ & \\ 12 &= 6\cdot 2, \text{ por lo tanto 6 divide a 12.} \\ & \\ 12 &= 4\cdot 3, \text{ por lo tanto 4 divide a 12.} \\ & \\ 12 &= 3\cdot 4, \text{ por lo tanto 3 divide a 12.} \\ & \\ 12 &= 2\cdot 6, \text{ por lo tanto 2 divide a 12.} \\ & \\ 12 &= 1\cdot 12, \text{ por lo tanto 1 divide a 12.} \end{align*}\]

Ahora que tenemos la definición de divisibilidad, veamos algunas propiedades que se cumplen.

Proposición 2

Para cualesquiera enteros \(a,b\) y \(c\). La noción de divisibilidad cumple lo siguiente:

La divisibilidad tiene la propiedad de reflexividad, es decir, \(a|a\).
La divisibilidad tiene la propiedad de transitividad, si \(a|b\) y \(b|c\), entonces \(a|c\).
Si \(a|b\) y \(b \neq 0\), entonces \(|a| \le |b|\).
Si \(a|b\) y \(a|c\), entonces \( a|(\alpha b + \beta c)\), para cualesquiera enteros \(\alpha\) y \(\beta\).
Si \(a|b\) y \(a|(b \pm c)\), entonces \(a|c\).
Si \(a|b\) y \(b|a\), entonces \(|a| = |b|\).
Se tiene que \(a|0\) para cualquier entero \(a\).

Demostraremos algunas de las propiedades a manera de ejemplo y dejaremos las demás como ejercicios para el lector.

Demostración. 1.
Sabemos que para todo entero \(a\) se cumple que \(a = a\cdot 1\), luego por definición tendríamos que \(a|a\).\(\square\)

Demostración. 2.

Por hipótesis tenemos que \(a|b\) y \(b|c\) entonces podemos escribir que existen enteros \(q_1,q_2\) tales que:

\[\begin{align*} b &= aq_1, \\ & \\ c &= bq_2. \end{align*}\]

Luego si sustituimos la primer ecuación en la segunda ecuación y tendríamos que,

\[c = bq_2 = (aq_1) \cdot q_2 = a\cdot (q_1 q_2).\]

Entonces como \(c = ak\), donde \(k = q_1q_2\), se cumple que \(a|c\). \(\square\)

Ejemplo 10

Como \(12|60\) y \(60|240\) entonces \(12|240\).
Esto es cierto ya que

\[240 = 60\cdot 4 = (12\cdot 5)\cdot 4 = 12 \cdot 20.\]

Demostración. 3.

Notemos que como \(a|b\) y \(b\neq 0\), tendríamos que \(b = aq\) para algún entero \(q\). Es imposible que \(q = 0\), pues implicaría que \(b = 0\).
Así, \(q\ge 1\) o \(q\le -1\). En el primer caso, \(|q| = q \ge 1\). En el segundo caso, \(|q| = -q \ge 1\).
Entonces tenemos que \(|q|\geq 1\). Luego \(|b| = |a|\cdot |q| \geq |a|\). \(\square\)

Ejemplo 11

Como \(15|45\), entonces se cumple que \(15 < 45\).

Demostración. 4.

Por hipótesis tenemos que \(a|b\) y que \(a|c\), es decir que para \(q_1\), \(q_2\) enteros se cumple que \(b = aq_1\) y \(c = aq_2\). Luego tenemos lo siguiente:

\[\begin{align*} \alpha b + \beta c &= \alpha \cdot (aq_1) + \beta \cdot (aq_2) \\ & \\ &= a\cdot (\alpha q_1 + \beta q_2). \end{align*}\]

Por lo tanto, por la definición de divisibilidad \(a| (\alpha b + \beta c)\) para cualesquiera enteros \(\alpha, \beta\). \(\square\)

Ejemplo 12

Como \(5|20\) y \(5|35\) entonces \(5|(20\alpha + 35\beta )\). Lo anterior es cierto para cualesquiera valores de \(\alpha\) y \(\beta\). Tomemos \(\alpha = 3\) y \(\beta = 4\), entonces tendremos lo siguiente,

\[20\alpha + 35\beta = 20\cdot 3 + 35\cdot 4 = (5\cdot 4)\cdot 3 + (5\cdot 7)\cdot 4 = 5\cdot(12 + 28) = 5\cdot 40.\]

Por lo tanto, \(5\) divide a \(20\alpha + 35\beta\).

Veamos algunos ejercicios relacionados con la divisibilidad.

Ejemplo 13

Demuestra que si \(n\) divide a \(m\), entonces \(n^2\) divide a \(m^2\).

Solución.

Por hipótesis tenemos que \(n|m\), entonces por la Definición 2 sabemos que existe un entero \(q\) tal que \(m = nq\).
Si elevamos ambos lados de la igualdad al cuadrado obtenemos que,

\[m^2 = (n q)^2 = n^2\cdot q^2.\]

Esto quiere decir que \(m^2 = n^2\cdot k\), donde \(k = q^2\). Por lo tanto, por la definición tendríamos que \(n^2| m^2\). \(\square\)

Ejemplo 14

Demuestra o da un contraejemplo del siguiente enunciado.

Si \(a\) divide a \(b\) y \(c\) divide a \(d\), entonces \((a + c)|(b+d)\).

Solución.

La proposición es falsa, daremos un contraejemplo.
Tomemos los siguientes valores \(a = 2, b = 4, c = 3\) y \(d = 9\), entonces tendríamos que \(2|4\) y \(3|9\) pero \(2 + 3 = 5 \nmid 13 = 4 + 9\). Por lo tanto, no se cumple en general.

Ejemplo 15

Demuestra que si \(n\) es divisible entre \(4\) entonces \(n^2\) es divisible por \(16\).

Solución.

Por hipótesis tenemos que \(4|n\), es decir que \(n = 4q\) para algún entero \(q\). Si elevamos al cuadrado la igualdad anterior tendríamos que

\[n^2 = (4q)^2 = 16q^2.\]

Por lo tanto, tendríamos que \(n^2 = 16q^2 = 16k\), donde \(k = q^2\), así, se cumple que \(16|n^2\). \(\square\)

Proposición 3

Demuestra que si \(a| b_i\) para \(1 \le i \le n\), entonces \(a|(b_1\beta_1 + b_2\beta_2 + \ldots + b_n\beta_n),\) para cualesquiera enteros \(\beta_i.\)

Demostración. Por hipótesis tenemos que \(a|b_i\) para \(1 \le i \le n\), entonces para cada \(i\) tendríamos que \(b_i = ak_i\) para algún entero \(k_i\).
Ahora, consideremos la combinación lineal de los \(b_i\) con coeficientes enteros \(\beta_i\),

\[S = \sum_{i=1}^{n}b_i\beta_i = b_1\beta_1 + b_2\beta_2 + \ldots + b_n\beta_n.\]

Vamos a sustituir cada uno de los \(b_i = ak_i\) en la expresión,

\[S = (ak_1)\beta_1 + (ak_2)\beta_2 + \ldots + (ak_n)\beta_n.\]

Luego, podemos factorizar el valor en común \(a\),

\[S = a(k_1\beta_1 + k_2\beta_2 + \ldots + k_n\beta_n).\]

Sea \(K = k_1\beta_1 + k_2\beta_2 + \ldots + k_n\beta_n\). Como es la suma del producto de enteros, entonces es un entero, es decir que \(K\in \mathbb{Z}\).

Por lo tanto, tenemos que \(S = aK\) y por definición \(a|(b_1\beta_1 + b_2\beta_2 + \ldots + b_n\beta_n)\).\(\square\)

Algoritmo de la división#

Como mencionamos al inicio del capítulo, vamos a enunciar el principio del mínimo ya que lo usaremos en la demostración del algoritmo de la división. Para no salirnos del tema principal dejaremos una nota al final del capítulo con referencia a esta proposición.

Proposición 4 (Principio del mínimo)

Sea \(S\) un subconjunto no vacío de los números naturales \(\mathbb{N}\). Entonces \(S\) tiene un único elemento mínimo, es decir, existe un único elemento \(m\in S\) tal que para todo \(n\in S\) se tiene que \(m\leq n\).

La idea de que un número deje residuo al dividirse nos lleva a enunciar y demostrar el algoritmo de la división.

Teorema 3 (Algoritmo de la división)

Sean \(a\) un entero y \(b\) un entero positivo. Entonces existen \(q\) y \(r\) enteros únicos tales que: \(a=bq+r\), donde \(0\le r<b\).

Demostración. La demostración consiste de dos partes. Primero probaremos la existencia de dichos enteros \(q\) y \(r\) y después probaremos que estos dos son únicos.

Prueba de existencia.

Consideremos al conjunto \(S\) que tiene la siguiente forma \(S=\{a-bn : n\in \mathbb{Z} \text{ y } a-bn\geq 0 \}\).
Podemos notar que \(S\) es un conjunto de enteros no negativos, es decir, \(S \subseteq \mathbb{N}\). Vamos a probar que \(S\) es no vacío y que por lo tanto por el principio de la Proposición 5 tendrá un mínimo.

Caso \(1\).
Supongamos que \(a\geq 0\). Entonces si tomamos \(n = 0\) tenemos que \(a = a - b\cdot 0 \in S\), así \(S\) contiene un elemento.

Caso \(2\).
Supongamos que \(a<0\). Ya que \( b \in \mathbb{Z^+}\), \(b\geq 1\). Entonces si multiplicamos esta desigualdad por \(-a\) en ambos lados, tenemos lo siguiente,

\[\begin{align*} b &\geq 1 \\ & \\ -ab &\geq -a \\ & \\ a - ab &\geq 0, \\ \end{align*}\]

como consecuencia tenemos que \(a - ab \in S\).

En ambos casos, \(S\) tiene al menos un elemento, así vemos que \(S\) es un subconjunto no vacío de \(\mathbb{N}\). Luego por el principio del mínimo, \(S\) tiene un elemento mínimo, digamos \(r\).
Ya que \(r\in S\), existe un entero \(q\) tal que \(r = a - bq\), en donde \(r \geq 0\).

Para mostrar que \(r < b\), procederemos por contradicción.

Supongamos que \(r \geq b\). Entonces \(r - b \geq 0\). Pero como \(r = a -bq\) tenemos que,

\[\begin{align*} r - b &\geq 0 \\ & \\ (a-bq)-b &\geq 0 \\ & \\ a - b(q+1) &\geq 0. \end{align*}\]

Ya que \(a-b(q+1)\) es de la forma \(a-bn\), donde \(n = q+1\) y es mayor o igual que cero, \(a-b(q+1) \in S\). Esto quiere decir que \(r-b \in S\). Ya que \(b>0\), tenemos que \(r-b < r\). Así, \(r-b\) es menor a \(r\) y está en \(S\). Esto contradice nuestra elección de \(r\), entonces \(r<b\).
Por lo tanto, existen enteros \(q\) y \(r\) tal que \(a=bq +r\), en donde \(0\le r < b\).

Prueba de unicidad.

Nos gustaría probar que los enteros \(q\) y \(r\) son únicos.
Supongamos que hay enteros \(q, q', r\) y \(r'\) tales que

\[\begin{align*} a = bq + r &\text{, en donde } 0\le r < b, \\ & \\ a = bq' + r' &\text{, en donde } 0\le r' < b. \end{align*}\]

Por conveniencia supongamos que \(q\geq q'\). Entonces,

\[r'-r=(a-bq')-(a-bq)=bq-bq'=b(q-q').\]

Como \(q\geq q',\) sucede que \(q-q'\geq 0,\) por lo tanto \(r'-r \geq 0\). Pero como \(r'<b\) y \(r<b, r' - r < b \).
Supongamos que \(q > q'\), de lo anterior podemos decir que \(q-q'\geq 1\). Entonces \(b(q-q') \geq b\), esto quiere decir que \(r'-r \geq b\). Lo anterior es una contradicción porque \(r'-r < b\). Por lo tanto, \(q \not> q'\) y así \(q=q'\), entonces \(r=r'\).

Así, hemos probado que \(q\) y \(r\) son únicos. \(\square\)

Ejemplo 16

Encuentra el cociente \(q\) y el residuo \(r\) cuando:

\(125\) es dividido por \(15\).
\(-23\) es dividido por \(5\).

Solución.

\(125=15\cdot 8 +5\), entonces \(q=8\) y \(r=5\).
De la expresión \(-23=5\cdot(-4)+(-3)\), podríamos pensar que \(q=-4\) y \(r=-3\), pero el Teorema 3 dice que \(r\) no puede ser negativo. La expresión correcta sería \(-23=5\cdot(-5)+2\) y así \(0 \le r=2<5\) y \(q=-5\).

Con el algoritmo de la división podemos definir dos clases de números, lo números pares y los números impares. Las definiciones de estos números se derivan del algoritmo de la división, dando un valor de \(b = 2\) en la expresión \(a = bq + r\).

Definición 3 (Número par)

Diremos que un entero \(a\) es un número par si es de la forma \(a = 2k\).

Definición 4 (Número impar)

Diremos que un entero \(a\) es un número impar si es de la forma \(a = 2k + 1\).

Ejemplo 17

Demuestra que si \(n\) es impar entonces \(n^2\) también es impar.

Solución.

Por definición tenemos que \(n = 2k + 1\). Si elevamos al cuadrado la expresión tendremos que

\[n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2k(2k+2) + 1.\]

Por lo tanto \(n^2 = 2s + 1\), donde \(s = k(2k+1)\), es decir, que \(n^2\) es un número impar.\(\square\)

Ejemplo 18

Prueba que si \(x\) y \(y\) son números impares, entonces \(x^2 + y^2\) es par pero no es divisible entre \(4\).

Solución.

Como \(x\) y \(y\) son impares, entonces tenemos que \(x = 2k_1 + 1\) y \(y = 2k_2 + 1\) para algunos enteros \(k_1,k_2\), vamos a desarrollar la expresión,

\[\begin{align*} x^2 + y^2 &= (2k_1 + 1)^2 + (2k_2 + 1)^2 \\ & \\ &= 4k_1^2 + 4k_1 + 1 + 4k_2^2 + 4k_2 + 1 \\ & \\ &= 4(k_1^2 + k_2^2) + 4(k_1 + k_2) + 2 \\ & \\ &= 4q_1 + 4q_2 + 2, \end{align*}\]

en donde \(q_1 = k_1^2 + k_2^2\) y \(q_2 = k_1 + k_2\).

Como \(x^2 + y^2 = 2(2q_1 + 2q_2 + 1)\) entonces tenemos que el resultado es par.

Además, como \(x^2 + y^2 = 4\cdot (q_1 + q_2) + 2\), tenemos que \(4\nmid (x^2 + y^2)\) ya que el residuo es \(2\) para cualquier valor de \(k\).

Para terminar este capítulo pensemos en lo siguiente. De la Definición 2 de divisibilidad podemos decir que los múltiplos de un número \(n\) son aquellos que dejan residuo \(0\) al dividirse entre \(n\). Pero también podríamos preguntarnos por todos los números que al dividirse entre \(n\) dejan residuo \(1\), o todos los números que dejan residuo \(2\), etc.

A todos los números que dejan residuo \(1\) podemos agruparlos en un conjunto que llamaremos \([1]_n\). Del mismo modo para cada residuo \(r\) entre \(0\) y \(n-1\) podemos considerar el conjunto \([r]_n\). Podríamos notar que dos enteros están en el mismo conjunto \([r]_n\) si dejan el mismo residuo \(r\) al dividirse entre \(n\). Por el momento no discutiremos mucho esto, pero es importante que te des cuenta que un entero positivo \(n\) parte a todos los enteros en \(n\) clases.

Código para ver la divisibilidad de un entero \(n\) entre \(m\)#

El siguiente código nos dice si un entero \(n\) es divisible entre otro entero \(n\), además si no es divisible nos regresa los valores de \(q\) y \(r\) mencionados en el algoritmo de la división.

def divisible(m,n):
    if m%n == 0:
        print(n," divide a ",m," pues: ",m,"=",m//n,"x",n)
    else:
        print(n,"  NO divide a ",m," pues: ",m,"=",m//n,"x",n,"+",m%n,", con q =",m//n," y r =",m%n)

divisible(48,3)

3  divide a  48  pues:  48 = 16 x 3

divisible(48,5)

5   NO divide a  48  pues:  48 = 9 x 5 + 3 , con q = 9  y r = 3

divisible(900,-45 )

-45  divide a  900  pues:  900 = -20 x -45

divisible(10001, 32)

32   NO divide a  10001  pues:  10001 = 312 x 32 + 17 , con q = 312  y r = 17

Explicación del código#

En este capítulo introducimos la estructura de las funciones. Estas sirven para utilizar repetidamente un bloque de código sin necesidad de volver a escribirlo. Se utiliza la palabra clave def seguida del nombre de la función y paréntesis que contienen los parámetros de entrada de la función. Estos parámetros pueden ser de cualquier tipo, desde un valor entero hasta una lista de elementos. Incluso podríamos definir una función sin parámetros. Luego, se agrega un bloque de código identado que define las acciones que debe realizar la función.

def nombre_funcion(arg1,arg2, ...):
    # bloque de código a ejecutar
    # bloque de código a ejecutar

Una vez que tenemos construida una función, la forma en la que la usamos es simplemente poniendo el nombre de la función y los parámetros que esta necesita. Por ejemplo,

nombre_funcion(argumentos)

También utilizamos los condicionales if y else.
El condicional if y su contraparte else son estructuras que te permiten ejecutar diferentes bloques de código dependiendo de una condición dada.
El condicional if se utiliza para evaluar una expresión booleana y ejecutar un bloque de código si la condición es verdadera. De ser falsa la condición entonces el código pasa al condicional else y se ejecuta el bloque de código identado debajo del else. Estos condicionales son útiles para tomar decisiones en la ejecución de un programa, permiten que el flujo del código varíe dependiendo de si se cumple o no una condición específica.
La sintaxis sería la siguiente.

if condición_booleana:
    # bloque de código a ejecutar
    # bloque de código a ejecutar
else: 
    # bloque de código a ejecutar
    # bloque de código a ejecutar

Utilizamos la función print para imprimir diferentes valores en la consola. Podemos imprimir diferentes objetos con la función print, pero necesitamos separarlos por comas, en el siguiente ejemplo imprimimos cadenas de texto y variables con valores asignados. La sintaxis sería la siguiente.

a = 10
b = 1
print("Cadena de texto",a,"otra cadena de texto",b)

En el ejemplo anterior, la función print nos regresaría en la consola lo siguiente, «Cadena de texto 10 otra cadena de texto 1», es decir, que no imprime las comas dentro de la función, únicamente imprime las cadenas de texto y el valor de las variables.

Por último vimos una operación nueva %. Lo que hace esta operación es devolver el residuo de la división de un número por otro. Por ejemplo.

a = 21%4

El resultado de la variable «a» sería \(1\), ya que \(21 = 4\cdot 5 + 1\).

Ahora veamos cómo funciona el código para revisar la divisibilidad de un número entre otro.

def divisible(m,n):
    if m%n == 0:
        print(n," divide a ",m," pues: ",m,"=",m//n,"x",n)
    else:
        print(n," no divide a ",m," pues: ",m,"=",m//n,"x",n,"+",m%n,", con q =",m//n," y r =",m%n)

Definimos una función llamada «divisible» que recibe como argumentos dos números enteros, el primero, «m» es el dividendo y el segundo, «n» es el divisor.

def divisible(m,n):

Luego, creamos un condicional if en donde se evalúa una condición booleana, el condicional verifica si la variable «m» deja residuo cero al dividirse entre la variable «n». Si es cierta la condición, el código identado dentro del condicional if nos imprime en la consola que la variable «n» divide a la variable «m» y el número \(m\) escrito de la forma \(m = qn\) para algún entero \(q\).

    if m%n == 0:
        print(n," divide a ",m," pues: ",m,"=",m//n,"x",n)

Si la condición en el condicional if es falsa, el código pasa al condicional else. El código identado dentro del condicional nos imprime en la consola que la variable «n» no divide a la variable «m» y el número \(m\) escrito de la forma \(m = qn + r\).

    else:
        print(n," no divide a ",m," pues: ",m,"=",m//n,"x",n,"+",m%n,", con q =",m//n," y r =",m%n)

Ejercicios de práctica#

Demuestra las propiedades faltantes en la Proposición 2.
Prueba que \(n^3-n\) es divisible por 6 para cada entero \(n\).
Demuestra que si \(3|k^3\), entonces \(3|k\).
Demuestra que el producto de cualesquiera \(3\) enteros consecutivos es divisible por \(6\).
Encuentra el cociente y el residuo cuando el primer entero es dividido por el segundo.
- \(78,11\)
- \(-325,13\)
- \(134,17\)
- \(1086,34\)
Demuestra las siguientes proposiciones:
- El cuadrado de todo número impar es de la forma \(8k + 1\).
- La cuarta potencia de todo número impar es de la forma \(16k + 1\).
Demuestra que la suma de una cantidad impar de números impares es siempre un número impar.
Demuestra que si el producto de una cantidad finita de enteros es impar, entonces todos los enteros involucrados deben ser impares.

Apéndice#

En los números naturales se cumple el principio de inducción. Otro principio importante que también se cumple es el principio del mínimo o del buen orden. A continuación lo enunciamos.

Proposición 5 (Principio del mínimo)

Sea \(S\) un subconjunto no vacío de los números naturales \(\mathbb{N}\). Entonces \(S\) tiene un único elemento mínimo, es decir, existe un único elemento \(m\in S\) tal que para todo \(n\in S\) se tiene que \(m\leq n\).

Demostración. Demostraremos el contrapositivo usando inducción. Lo que veremos es que si \(S\) no tiene un elemento mínimo, entonces \(S\) es vacío. Equivalentemente, lo que haremos es demostrar que \(\mathbb{N}\setminus S\) es todo \(\mathbb{N}\). Para ello, consideremos la siguiente afirmación: «Si \(n\) es un natural, entonces \(0,1,\ldots,n\) están todos en \(\mathbb{N} \setminus S\).» Demostraremos esta afirmación por inducción.

Lo primero que notamos es que \(0\) no puede estar en \(S\) pues en otro caso sería un mínimo de \(S\) ya que todo natural cumple \(n\geq 0\). Así, \(0\) está en \(\mathbb{N}\setminus S\), lo que es la base inductiva de nuestra afirmación.

Supongamos cierto el resultado para cierta \(n\), es decir, que \(0,1,\ldots,n\) están en \(\mathbb{N}\setminus S\). Esto quiere decir que \(0,1,\ldots,n\) no están en \(S\). Pero entonces \(n+1\) no puede estar en \(S\), pues en otro caso sería un mínimo de \(S\). Así, \(n+1\) está en \(\mathbb{N}\setminus S\). Como \(0,1,\ldots,n\) ya estaban, entonces se cumple que \(0,1,\ldots,n+1\) están en \(\mathbb{N}\setminus S\). Por lo tanto, la afirmación es cierta para \(n+1\) y por lo tanto es cierta para todo \(n\in\mathbb{N}\). En consecuencia, \(S\) es vacío. Dicho de otra forma, si \(S\) no es vacío, entonces debe tener un mínimo.

La unicidad es sencilla. Si existe otro elemento \(m'\) que también es mínimo, entonces por ser mínimo se tiene \(m'\leq m\). Y por ser \(m\) mínimo se tiene que \(m\leq m'\). Por lo tanto \(m=m'\). \(\square\)

Es fundamental que estemos trabajando con los números naturales, pues de otra forma no podemos garantizar la existencia del tal mínimo. Por ejemplo, el intervalo \((0,1)\) de los racionales (o de los reales) no tiene un elemento mínimo dentro de él. Los números pares (positivos y negativos) también son un conjunto sin mínimo.

Los elementos mínimos son importantes, pues frecuentemente tienen alguna propiedad especial que nos ayuda a demostrar algo. Una técnica de demostración usual es la siguiente: queremos ver que hay un natural que cumple ciertas propiedades \(P\) y \(Q\). Tomamos todos los naturales que cumplen \(P\), que tendremos que ver que al menos hay uno. Luego, de entre todos ellos, tomamos el mínimo \(m\). A veces, suponer que \(m\) no cumple \(Q\) lleva a la existencia de un \(n<m\) que cumple \(P\). ¡Esto contradice la minimalidad de \(m\)! Por esta razón, \(m\) debe cumplir \(Q\), y por lo tanto es el entero que buscamos. A continuación vemos un ejemplo de esto.

Ejemplo 19

Se tiene una sucesión infinita hacia ambos lados de números naturales \(\ldots,a_{-2}, a_{-1}, a_0, a_1, a_2,\ldots\). Cada número es el promedio de los dos números que tiene a su derecha y a su izquierda, por ejemplo, \(a_1\) es el promedio de \(a_0\) y \(a_2\). Demuestra que todos los números son iguales.

Demostración. De entre todos los números que colocamos, por principio del mínimo hay uno que es el más pequeño, digamos \(a_k\). Veremos que todos los números deben ser iguales a \(a_k\). Los dos números \(a_{k-1}\) y \(a_{k+1}\) tienen promedio \(a_k\). Además, cada uno de ellos es mayor o igual a \(a_k\) pues \(a_k\) es el mínimo. Así, tenemos:

\[a_k=\frac{a_{k-1}+a_{k+1}}{2}\leq \frac{a_k+a_k}{2}=a_k.\]

Como se da la igualdad entre extremos, se debe dar la igualdad en cada paso de la cadena. Si de algún lado tuviéramos que el número es estrictamente más pequeño, por ejemplo, si \(a_{k+1}<a_k\), entonces para compensar y tener promedio \(a_k\) necesitaríamos \(a_{k-1}<a_k\). ¡Pero esto es imposible pues \(a_k\) quedamos que era el más chico de todos!.

Así, \(a_{k-1}=a_{k+1}=a_k\). De aquí es sencillo probar por inducción sobre \(l\) que \(a_{k+l}=a_k\) para todo \(l\geq 0\), y aparte probar por inducción que \(a_{k-l}=a_k\) para todo \(l\geq 0\). Por lo tanto, todos los números son iguales. \(\square\)

Esta misma estrategia es la que se usó para demostrar el algoritmo de la división.