Teoría de números (nivel 1) 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
- Si $a|b$, entonces $|a|\leq |b|$.
- Si $a|b$ y $b|c$, entonces $a|c$.
- Si $a|b$ y $a|c$, entonces $a|(b+c)$.
- Si $a|b$, entonces $a|bx$ para cualquier $x\in\mathbb{Z}$.
Algunos casos concretos de divisibilidad conviene tenerlos en cuenta pues dan lugar a algunas confusiones.
- Todos los números enteros dividen a cero, mientras que cero solo se divide a sí mismo. Esto se deduce directamente de la definición.
- $1$ y $-1$ dividen a cualquier número pero los únicos números que dividen a $1$ y $-1$ son ellos mismos. Es fácil probarlo a partir de las propiedades anteriores.
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}$, siendo $b\neq 0$, 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 necesariamente $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$.
Es fácil comprobar que $a$ es divisible entre $b$ si, y solo 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 aprendemos 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}\quad\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$. Veamos qué pasa si cambiamos $8$ o $5$ de signo.
- Para 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$! Esto se puede corregir de forma muy sencilla: 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$.
- Dividir $8$ entre $-5$ es mucho más sencillo ya que $8=1\cdot 5+ 3$ se transforma fácilmente en $8=(-1)\cdot(-5)+3$, luego el cociente es $-1$ y el resto es $3$.
La cuestión de los signos puede parecer muy artificial al principio, pero hace que los restos se repitan periódicamente para todos los enteros y será fundamental a la hora de entender las congruencias más adelante.
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 solo 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:
- Dividimos $348$ entre $96$ y obtenemos $348=3\cdot96+60$: el resto es $60$.
- Dividimos $96$ entre $60$ y obtenemos $96=1\cdot60+36$: el resto es $36$.
- Dividimos $60$ entre $36$ y obtenemos $60=1\cdot36+24$: el resto es $24$.
- Dividimos $36$ entre $24$ y obtenemos $36=1\cdot24+12$: el resto es $12$.
- Dividimos $24$ entre $12$ y obtenemos $24=2\cdot12+0$: el resto es $0$. Como este último resto es el primer resto cero, llegamos a que $\mathrm{mcd}(348,96)=12$, el último resto no nulo.
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:
- $a=48$, $b=72$
- $a=2463$, $b=1246$
- $a=32768$, $b=16554$
- $a=14511644$, $b=8292368$
Ir arribaIr al índiceInformar Problemas que puedes resolver con lo aprendido en esta lecciónProblema 103★★☆☆☆
Encontrar todos los números naturales \(n\in\mathbb{N}\) tales que \(3^n+5^n\) es múltiplo de \(3^{n-1}+5^{n-1}\).
Pista. Demostrar que, si esto ocurre, entonces \(3^n+5^n=4(3^{n-1}+5^{n-1})\).
PistaSolución 1Solución. Observemos en primer lugar que
\[3(3^{n-1}+5^{n-1})=3^n+3\cdot 5^n<3^n+5^n<5\cdot 3^{n-1}+5^n=5(3^{n-1}+5^{n-1})\]
luego, si \(3^n+5^n\) es múltiplo de \(3^{n-1}+5^{n-1}\), entonces tiene que ser \(3^n+5^n=4(3^{n-1}+5^{n-1})\). Ahora bien, esto nos lleva a que \(5^n-4\cdot 5^{n-1}=4\cdot 3^{n-1}-3^n\), es decir, \(3^{n-1}=5^{n-1}\), igualdad que sólo se tiene para \(n=1\). Deducimos que el único natural para el que se cumple es \(n=1\) (observemos que, en tal caso, \(3^n+5^n=8\) y \(3^{n-1}+5^{n-1}=2\)).
Informar InfoOlimpiada Matemática Española (fase local), 2005 problema 6
Si crees que el enunciado contiene un error o imprecisión, puedes notificarlo pulsando en el siguiente botón:
Informar de error en enunciadoSi conoces una competición en la que apareció este problema o bien crees que la información que aquí aparece es incorrecta, puedes notificarlo pulsando en el siguiente botón:
Informar de procedencia del problemaProblema 65★★☆☆☆
Sean $x,y,z$ números enteros. Demostrar que si $6$ divide a $x+y+z$, entonces también divide a $x^3+y^3+z^3$.
Pista. Probar que $a^3-a$ para cualquier número entero $a$.
PistaSolución 1Solución. Veamos que, para cualquier $a\in\mathbb{Z}$, se cumple que $6$ divide a $a^3-a$. Para probar esto, observemos que $a^3-a$ siempre es par (ya que $a^3$ y $a$ tienen la misma paridad) y también es múltiplo de $3$ ya que $a^3-a=(a-1)a(a+1)$ es el producto de tres enteros consecutivos. Por tanto, hemos probado que $a^3-a$ es múltiplo de 6. Usando esto,
$$x^3+y^3+z^3-(x+y+z)=(x^3-x)+(y^3-y)+(z^3-z)$$
ha de ser múltiplo de 6 y, como $x+y+z$ lo es, también tiene que serlo $x^3+y^3+z^3$.
Informar InfoSi crees que el enunciado contiene un error o imprecisión, puedes notificarlo pulsando en el siguiente botón:
Informar de error en enunciadoSi conoces una competición en la que apareció este problema o bien crees que la información que aquí aparece es incorrecta, puedes notificarlo pulsando en el siguiente botón:
Informar de procedencia del problemaProblema 254★★☆☆☆
Sean $a$ y $b$ enteros. Demostrar que la ecuación
\[(x-a)(x-b)(x-3)+1=0\]
admite a lo sumo una solución entera.
Pista. Observa que $x-a$, $x-b$ y $x-3$ tienen que ser divisores de $-1$.
PistaSolución 1Solución. La ecuación se puede escribir como $(x-a)(x-b)(x-3)=-1$. Por tanto, si $x$ es una solución entera, entonces $x-a$, $x-b$ y $x-3$ son números enteros que dividen a $-1$, luego han de ser iguales a $\pm 1$. En particular, de la condición $x-3=\pm 1$ deducimos que las únicas posibles raíces enteras de la ecuación son $x=2$ y $x=4$. Probaremos por reducción al absurdo que no pueden ser las dos a la vez soluciones.
Si $x=2$ es solución, sustituyendo en la ecuación original obtenemos que $(2-a)(2-b)=1$ y, si $x=4$ es solución, entonces $(4-a)(4-b)=-1$. Si ambos valores de $x$ son soluciones, entonces $4-a$ y $2-a$ son iguales a $\pm 1$ y, como se diferencian en $2$ unidades, tiene que ser $4-a=1$ y $2-a=-1$, es decir, $a=3$. Sustituyendo $a=3$ en $(2-a)(2-b)=1$, tenemos que $2-b=-1$ y, por tanto, $b=3$. No obstante, $a=b=3$ no cumple $(4-a)(4-b)=-1$ y hemos llegado a una contradicción.
Informar InfoOlimpiada Matemática Española (fase nacional), 2005 problema 1
Si crees que el enunciado contiene un error o imprecisión, puedes notificarlo pulsando en el siguiente botón:
Informar de error en enunciadoSi conoces una competición en la que apareció este problema o bien crees que la información que aquí aparece es incorrecta, puedes notificarlo pulsando en el siguiente botón:
Informar de procedencia del problemaProblema 279★★☆☆☆
Demostrar que los binomios $25x+31y$ y $3x+7y$ son múltiplos de 41 para los mismos valores enteros de $x$ e $y$.
Pista. Observa que $3(25x+31y)-25(3x+7y)$ siempre es múltiplo de 41.
PistaSolución 1Solución. Consideremos la siguiente identidad
\[3(25x+31y)-25(3x+7y)=-82y,\]
que se obtiene al eliminar $x$ mediante una combinación de los dos binomios. Observemos que $-82y$ es múltiplo de 41, luego tenemos dos implicaciones:
- Si $25x+31y$ es múltiplo de 41 también lo será $25(3x+7y)$ y, como $25$ y $41$ son primos entre sí, también lo será $3x+7y$.
- Si $3x+7y$ es múltiplo de 41, también lo será $3(25x+31y)$ y, como $3$ y $41$ son primos entre sí, también lo será $25x+31y$.
Hemos demostrado que $25x+31y$ es múltiplo de 41 si, y sólo si, $3x+7y$ es múltiplo de 41, que es lo que se pide en el enunciado.
Nota. También se podría haber eliminado $y$ obteniendo la igualdad
\[7(25x+31y)-31(3x+7y)=82x,\]
y el razonamiento a partir de aquí es similar.
Informar InfoOlimpiada Matemática Española (fase nacional), 1988 problema 3
Si crees que el enunciado contiene un error o imprecisión, puedes notificarlo pulsando en el siguiente botón:
Informar de error en enunciadoSi conoces una competición en la que apareció este problema o bien crees que la información que aquí aparece es incorrecta, puedes notificarlo pulsando en el siguiente botón:
Informar de procedencia del problemaProblema 354★★★☆☆
Dado un entero $n\geq 2$, demostrar que existe un conjunto $S$ de $n$ números enteros tales que $(a-b)^2$ divide a $ab$ para cualesquiera $a,b\in S$.
Pista. Si $a$ y $b$ cumplen la propiedad del enunciado, entonces también la cumplen $a+c$ y $b+c$ siempre que $c$ sea un múltiplo de $ab$.
PistaSolución 1Solución. Construyamos el conjunto $S$ por inducción sobre $n$. Para el caso base $n=2$, basta tomar el conjunto $S=\{1,2\}$. Supongamos entonces que $\{a_1,\ldots,a_n\}$ es un conjunto de $n$ elementos tales que $(a_i-a_j)^2$ divide a $a_ia_j$ para cualesquiera subíndices $i$ y $j$; si construimos un conjunto $S$ de $n+1$ elementos que también cumple esta propiedad habremos demostrado el enunciado.
La idea clave es darse cuenta de que si $a$ y $b$ son tales que $(a-b)^2$ divide a $ab$, entonces $a+c$ y $b+c$ también cumplen esta propiedad siempre que $c$ sea un múltiplo de $ab$. Por tanto, si consideramos el producto $c=a_1\cdots a_n$, el conjunto $S_1=\{c,a_1+c,a_2+c,\ldots,a_n+c\}$ tiene $n+1$ elementos (son todos distintos) y cumple la propiedad del enunciado. Comprobémoslo:
- Tomando $a=a_i+c$ y $b=a_j+c$, se tiene que $(a-b)^2=(a_i-a_j)^2$ divide a $a_ia_j$ por hipótesis de inducción, luego también divide a $ab=a_ia_j+c(a_i+a_j)+c^2$ (ya que $c$ es múltiplo de $a_ia_j$).
- Tomando $a=c$ y $b=a_i+c$, se tiene que $(a-b)^2=a_i^2$ divide a $ab=a_ic+c^2$ ya que $a_i$ divide a $c$.
Informar InfoSi crees que el enunciado contiene un error o imprecisión, puedes notificarlo pulsando en el siguiente botón:
Informar de error en enunciadoSi conoces una competición en la que apareció este problema o bien crees que la información que aquí aparece es incorrecta, puedes notificarlo pulsando en el siguiente botón:
Informar de procedencia del problema