Olimpiadas de Matemáticas
Página de preparación y problemas

Volver al Í­ndice
Selector
La base de datos contiene 22 ficheros de apuntes.

Lección 1. Divisibilidad

Definición de divisibilidad, divisor y múltiplo Dados $a,b\in\mathbb{Z}$, diremos que $a$ divide a $b$ (ó que $a$ es un divisor de $b$ ó que $b$ es un múltiplo de $a$) cuando exista $q\in\mathbb{Z}$ de forma que $b=aq$. Lo denotaremos por $a|b$.

A continuación recogemos algunas propiedades elementales de la divisibilidad de números, cuya comprobación es inmediata y se deja como ejercicio. Dados $a,b,c\in\mathbb{Z}$, demostrar que

Algunos casos concretos de divisibilidad conviene tenerlos en cuenta pues dan lugar a algunas confusiones.

Con la propia definición no es fácil saber si un número divide o no a otro ya que tendríamos que ir multiplicándolo sucesivamente por números para ver si nos da el segundo número. Necesitamos un proceso que nos muestre si es divisible o no.

División euclídea Dados $a,b\in\mathbb{Z}$, existen $q,r\in\mathbb{Z}$ tales que $0\leq r\lt b$ y \[a=q\cdot b+r\] Los números $q$ y $r$ son únicos cumpliendo estas relaciones. Al número $q$ se le llama cociente y a $r$ resto de la división euclídea de $a$ entre $b$.
Demostración. Hagamos la demostración cuando $a,b\gt 0$ (los otros casos los dejamos como ejercicio). Consideremos $R=\{a-tb\geq 0:t\in\mathbb{Z}\}$. Claramente $a=a-0b\in R$ luego $R$ no es vacío y tiene un elemento mínimo, que llamaremos $r=\min R$. Como $r\in R$, existirá $q\in\mathbb{Z}$ tal que $r=a-qb$, es decir, $a=qb+r$. Bastará ver que $r\lt b$, pero si $r\geq b$, entonces $0\leq r-b=a-(q+1)b\in R$ contradiciendo que $r$ es el elemento mínimo de $r$. Para probar que $r$ y $q$ son únicos, supongamos que pudiéramos escribir $a=qb+r$ y $a=q'b+r'$ con $0\leq r,r'\lt b$ y demostremos que tiene que ocurrir que $r=r'$ y $q=q'$. Restando las expresiones anteriores obtenemos $0=(q-q')b+(r-r')$, de donde $r-r'|b$, pero $|r-r'|\lt b$, de donde necesariamente $r-r'=0$ y tenemos que $0=(q-q')b$ luego $q-q'=0$ ya que $b\neq 0$.

A partir de la proposición es fácil comprobar que $a$ es divisible entre $b$ si, y sólo si, el resto de la división de $a$ entre $b$ es cero. Además, la división euclídea se puede calcular mediante el algoritmo que todo el mundo aprende en el colegio. Por ejemplo, para dividir $4528$ entre $7$, tenemos que $$\left.\begin{matrix}4&5&8&2&&7&&\\&3&8&&&6&5&4\\&&3&2&&&&\\&&&\underline 4&&&&\end{matrix}\right\}\hspace{0.5cm}\Longrightarrow\hspace{0.5cm}4582=654\cdot 7+4$$ luego el cociente de la división euclídea es $654$ y el resto es $4$.

Visto esto, ¿qué ocurre con la división de números negativos? Observemos que, si dividimos $8$ entre $5$, tenemos cociente $1$ y resto $3$, es decir, $8=1\cdot 5+ 3$. Si intentamos dividir $-8$ entre $5$, podemos estar tentados de escribir $(-8)=(-1)\cdot 5+(-3)$ y decir que el cociente es $-1$ y el resto $-3$ pero ¡el resto tiene que estar entre $0$ y $4$! Para corregir esto, intuitivamente quitamos una unidad al cociente y arreglamos el resto, es decir, $(-8)=(-2)\cdot 5+2$ luego el cociente es $-2$ y el resto $2$.

La noción de divisibilidad nos conduce directamente a preguntarnos cuáles son los divisores de un número. Hasta la próxima sección no vamos a poder responder de forma precisa a esta pregunta; necesitaremos antes una herramienta que nos explique cómo son los divisores comunes a dos números. Observemos que $1$ siempre es un divisor común a cualquier par de números y todo divisor es menor en valor absoluto que cualquiera de los dos números, lo que nos dice que siempre habrá un mayor divisor común.

Definición de máximo común divisor y mínimo común múltiplo Dados $a,b\in\mathbb{N}$, se llama máximo común divisor de $a$ y $b$ al mayor número natural $d$ que cumpla que $d|a$ y $d|b$ y lo denotaremos por $\mathrm{mcd}(a,b)$. Se llama mínimo común múltiplo de $a$ y $b$ al menor número natural $m$ que cumpla que $a|m$ y $b|m$, y lo denotaremos por $\mathrm{mcm}(a,b)$.
Identidad de Bézout Dados $a,b\in\mathbb{Z}$ y $d=\mathrm{mcd}(a,b)$, existen $u,v\in\mathbb{Z}$ tales que \[d=au+bv.\]
Demostración. Lo demostraremos sólo para el caso $a,b\gt 0$ pues los demás casos se deducen fácilmente a partir de este. Consideremos $D=\{as+bt:s,t\in\mathbb{Z}\}$ y $D^+=\{x\in D:x>0\}$. Entonces $D^+$ es no vacío (ya que $a=a\cdot 1+b\cdot 0\in D^+$) y podemos considerar $h=\min D^+>0$, que podremos escribir como $h=au+bv$ para ciertos $u,v\in\mathbb{Z}$. Veamos que $h=d$ y habremos terminado la demostración. Por un lado, tenemos que $d|a$ y $d|b$ por ser un divisor común luego $d|h=au+bv$ luego $d\leq h$ y será suficiente probar que $h|a$ y $h|b$. Si $a$ no fuera divisible por $h$, haciendo la división euclídea de $a$ entre $h$, existirán $q,r\in\mathbb{N}$ tales que $0\lt r\lt h$ y $a=qh+r$ luego $0\lt r=a-qh=(1-qu)a-qbv$ lo que nos llevaría a que $r\in D^+$ y $r\lt h$, contradiciendo que $h$ es el mínimo. Esta contradicción nos dice que $a$ tiene que ser divisible por $h$ y, de la misma forma, se razona que $b$ también tiene que serlo, luego $h$ es un divisor común de $a$ y $b$.

Para concluir las generalidades sobre el máximo común divisor, damos un método bastante rápido para calcularlo. Este método se basa en la siguiente propiedad útil en la práctica, cuya demostración se deja como ejercicio.

Ejercicio propuesto Si tenemos dos números $a,b\in\mathbb{N}$ y hacemos su división, obtenemos $q,r\in\mathbb{N}$ tales que $a=bq+r$ y $0\leq r\lt b$. Demostrar que $\mathrm{mcd}(a,b)=\mathrm{mcd}(b,r)$.
Algoritmo de Euclides Sean $a,b\in\mathbb{Z}$ con $a,b>0$ y definimos la sucesión $\{r_n\}$ como $r_1=a$, $r_2=b$ y tal que, para $n\geq 3$, $r_n$ es el resto de dividir $r_{n-2}$ entre $r_{n-1}$. Entonces, existe un primer término nulo $r_N$ y se cumple que $\mathrm{mcd}(a,b)=r_{N-1}$.
Demostración. Mientras $r_{n-2}$ sea distinto de cero, la condición de que $r_n$ sea el resto de dividir $r_{n-1}$ entre $r_{n-2}$ nos asegura que $r_n\lt r_{n-1}$. Como los restos son todos números naturales, necesariamente habrá un primer término $r_N$ nulo (no puede haber una sucesión descendente infinita de números naturales por el principio del mínimo). Además, el ejercicio anterior aplicado a este caso nos asegura que \begin{eqnarray*} \mathrm{mcd}(a,b)&=&\mathrm{mcd}(r-1,r_2)=\mathrm{mcd}(r_2,r_3)=\ldots=\mathrm{mcd}(r_{N-2},r_{N-1})\\ &=&\mathrm{mcd}(qr_{N-1},r-{N-1})=r_{N-1} \end{eqnarray*} ya que, al ser $r_{N}=0$, la división euclídea nos dice que $r_{N-2}=qr_{N-1}+0$ para algún $q\in\mathbb{N}$.

Por ejemplo, si queremos hallar $\mathrm{mcd}(96,348)$, procedemos de la siguiente manera:

Para calcular el mínimo común múltiplo de dos números no hay un método tan directo. Sin embargo, la siguiente fórmula, válida para cualesquiera $a,b\in\mathbb{Z}$, nos permite calcularlo a partir del máximo común divisor: \[\mathrm{mcd}(a,b)\cdot\mathrm{mcm}(a,b)=a\cdot b.\] Veremos una forma sencilla de demostrarlo cuando hablemos de factorizaciones, aunque quien se atreva que la demuestre ahora.

Ejercicio propuesto Mediante el algoritmo de Euclides, calcular $\mathrm{mcd}(a,b)$ en los siguientes casos:
  1. $a=48$, $b=72$
  2. $a=2463$, $b=1246$
  3. $a=32768$, $b=16554$
  4. $a=14511644$, $b=8292368$


Ir arribaIr al Í­ndiceProblemas de PO-Aritmética