Divisibilidad

[Vladislao]

Esto pretende ser un apunte introductorio a los conceptos de divisibilidad clásicos en Olimpíadas.

El símbolo [math]\mathbb{Z} denota al conjunto de los números enteros (por ejemplo [math]-2, [math]0, [math]19 son enteros). El símbolo [math]\mathbb{N} denota el conjunto de los enteros positivos (mayores que [math]0). Cuando se diga "entero positivo" o "natural" se entenderá que el número en cuestión está en [math]\mathbb{N}, y cuando se diga que es entero se entenderá que está en [math]\mathbb{Z}.

Definición: Dados dos números enteros [math]a y [math]b diremos que [math]a divide a [math]b si el cociente [math]\frac{b}{a} es también un número entero. Por ejemplo [math]7 divide a [math]91 ya que [math]\frac{91}{7}=13 que es un número entero.

La notación estándar para decir "[math]a divide a [math]b" consiste en escribir [math]a\mid b (en látex sería escribir a\mid b). Cuando [math]a no divida a [math]b (es decir cuando el cociente [math]\frac{b}{a} no sea entero) escribimos [math]a\nmid b (en látex a\nmid b).

Es claro que [math]1\mid x para todo entero [math]x, y que [math]0\nmid x para todo entero [math]x\neq 0 (ya que la división por [math]0 no está siquiera definida). Por conveniencia vamos a definir que [math]0\mid 0.

Propiedad 1: Dados [math]a y [math]b enteros, [math]a\mid b si y sólo si existe un entero [math]k tal que [math]b=ak.

Demostración: Es claro que si [math]a\mid b entonces [math]\frac{b}{a} es un entero. Llamemos a este entero [math]k, entonces [math]\frac{b}{a}=k, de donde [math]b=ak. Recíprocamente, si [math]k es un entero y [math]b=ak, entonces ciertamente [math]\frac{b}{a}=k, y como [math]k es un entero, [math]\frac{b}{a} es un entero de donde resulta que [math]a\mid b. [math]\blacksquare

Propiedad 2: Si [math]a\mid b y [math]k es cualquier entero, entonces [math]a\mid kb.

Demostración: Si [math]a\mid b entonces [math]\frac{b}{a} es un entero. Entonces, si [math]k es cualquier entero [math]k\cdot \frac{b}{a} es también entero. Resulta que [math]\frac{kb}{a} es entero, y por lo tanto [math]a\mid kb. [math]\blacksquare

Nota: La recíproca no vale. Es decir, si [math]a\mid kb, no es cierto que deba ser [math]a\mid b. Un ejemplo sencillo es [math]a=2, [math]b=3 y [math]k=4.
Nota 2: Es evidente que cualquiera sea [math]a, siempre ocurre que [math]a\mid 0, ya que [math]0 es "múltiplo de todos los enteros".

Propiedad 3: Sea [math]k cualquier entero. Si [math]a\mid b y [math]a\mid c, entonces [math]a\mid b+ck.

Demostración: Si [math]a\mid c, por la Propiedad 2, resulta que [math]a\mid ck, de donde [math]\frac{ck}{a} es un entero. Además, si [math]a\mid b, entonces [math]\frac{b}{a} es entero. Luego, si sumamos los enteros [math]\frac{ck}{a} y [math]\frac{b}{a}, se obtiene otro entero [math]N=\frac{ck}{a}+\frac{b}{a}, de donde, [math]N = \frac{ck+b}{a}. Como [math]N es entero, se tiene que [math]a\mid ck+b, como queríamos. [math]\blacksquare

Observación: Es claro que [math]a\mid a. Esto, por la Propiedad 2, implica que para todo entero [math]k se cumple que [math]a\mid ka. Luego, si [math]a\mid b, por la Propiedad 3, se tiene que [math]a\mid b+ka. Este resultado sencillo es lo suficientemente útil como para que lo remarquemos:

Propiedad 4: Si [math]k es un entero cualquiera y [math]a\mid b, entonces [math]a\mid b+ak.

Demostración: Surge de la observación que hicimos. [math]\blacksquare

Vamos a realizar una definición necesaria para enunciar y probar la siguiente Propiedad, la cual es tremendamente importante.

Definición: Dado un número real [math]x definimos al "valor absoluto de [math]x" como el valor sin signo de [math]x (por ejemplo, el valor absoluto de [math]-3 es [math]3 y el valor absoluto de [math]27 es [math]27). Denotamos al valor absoluto de [math]x como [math]|x|.

Observación: Si [math]x y [math]y son números reales se cumple que [math]|xy|=|x||y|.

Propiedad 5: Dados [math]a y [math]b enteros con [math]a\neq 0, si [math]a\mid b, entonces ocurre exactamente una de las siguientes cosas:

i) [math]b=0.

ii) [math]|a|\leq |b|.

Demostración: Vamos a observar que SIEMPRE ocurre una de esas dos cosas. En efecto, si [math]a\mid b, entonces por la Propiedad 1, [math]b=ak para algún entero [math]k. Luego, si [math]k=0, entonces [math]b=0 y se cumple la primera afirmación. Si [math]k\neq 0, entonces [math]|k|\geq 1 (ya que [math]k es menor o igual a [math]-1 o mayor o igual a [math]1). Luego, resulta que [math]|b| = |ak| = |a||k| \geq |a|\cdot 1 = |a|, de donde [math]|b|\geq |a|, como queríamos. [math]\blacksquare

Definición: Dados dos números [math]a y [math]b definimos al máximo común divisor de [math]a y [math]b como el máximo número que divide simultáneamente a [math]a y a [math]b. Denotamos a este número como [math]\text{mcd}(a,b).

Definición: Dos números [math]a y [math]b se dicen coprimos si [math]\text{mcd}(a,b)=1.

Propiedad 6: Sean [math]a y [math]b enteros coprimos entre sí. Si [math]a \mid bc entonces [math]a\mid c.

Demostración: No la haremos.

Como corolario de la Propiedad 6 resulta:

Propiedad 7: Si [math]p es un número primo y [math]p\mid bc, entonces [math]p\mid b o [math]p\mid c (pueden ocurrir ambas cosas).

Demostración: Supongamos que [math]p\mid bc, y que [math]p\nmid b, vamos a ver que [math]p\mid c. En efecto, si [math]p\nmid b entonces, al ser [math]p primo resulta que [math]p y [math]b son coprimos entre sí, luego, por la Propiedad 6 resulta que [math]p\mid c, y estamos. [math]\blacksquare

Con estas herramientas ya estamos en condiciones de afrontar la mayoría de los problemas. Especial atención a las últimas 4 propiedades, que son fundamentales para resolverlos de manera sencilla.

Dejo un par de ejercicios:

1) Probar que si [math]a\mid b y [math]b\mid a, entonces [math]a=b ó [math]a=-b.

2) Probar que si [math]k\mid a-1 y [math]k\mid a^2+a+1, entonces [math]k\mid 3. Concluir que para todo entero [math]a se cumple que [math]\text{mcd}(a-1,a^2+a+1) sólo puede ser [math]1 o [math]3.

3) Hallar todos los enteros [math]n tales que [math]\frac{19n-2}{2n+3} es un entero.

4) Probar que si [math]a\mid b y [math]b\mid c entonces [math]a\mid c. ¿Vale que si [math]a\mid c y [math]a\mid b entonces [math]b\mid c?

5) Hallar todos los pares de enteros [math]a,b\geq 2 tales que [math]ab\mid a+b.

[tuvie]

Propongo una solución posible para el 5), que fue el que más me gustó. Después si puedo subo una de cada uno de los restantes:

Spoiler: mostrar

Notemos que el problema nos dice que [math]a,b\geq{2}, por lo tanto [math]ab\leq{a+b}\Leftrightarrow{ab-b=b(a-1)}\leq{b}. Entonces, simplificando [math]b ya que es distinto de [math]0 por la condición del enunciado, nos queda [math]{a-1}\leq{1}, entonces utilizando el [math]2 para el lado izquierdo nos queda [math]a\leq 2. Entonces [math]2\leq{a}\leq{2}\implies{a=2}. Utilizando un método análogo, se obtiene [math]b=2. Entonces la única posibilidad que tenemos que probar es [math](2,2) que efectivamente funciona. Entonces el único par [math](a,b) que funciona es [math](a,b)=(2,2)

[ktc123]

Otra posible para el 5

Spoiler: mostrar

Tenemos que [math]ab\mid a+b\Rightarrow ab\mid a(a+b)=a^2+ab, de donde [math]ab\mid a^2\Rightarrow b\mid a. Análogamente llegamos a que [math]a\mid b y concluímos que [math]a=b. Entonces [math]a^2\mid 2a, que es lo mismo que [math]a\mid 2, y recordando los requisitos del enunciado la única pareja que anda es [math](a,b)=(2,2)

[JPablo]

1)

Spoiler: mostrar

Si [math]a\mid b entonces [math]\left | a \right |\leq \left | b \right | y si [math]b\mid a entonces [math]\left | a \right |\geq \left | b \right |.

Por lo tanto [math]\left | a \right |=\left | b \right | de donde [math]a=b o [math]a=-b. [math]\blacksquare

2)

Spoiler: mostrar

Por la Propiedad 3 que demostró Vladislao se tiene que [math]k\mid \left (a-1 \right )\left ( a+1 \right )=a^{2}-1 y por la Propiedad 3 se tiene que [math]k\mid \left (a^{2}+a+1 \right )-\left ( a^{2}-1 \right )=a+2. Usando de nuevo esta propiedad, tenemos que

[math]k\mid \left (a+2 \right )-\left ( a-1 \right )=3.

Sea [math]d el [math]\text{mcd} de [math]a-1 y [math]a^{2}+a+1. Como [math]d\mid a-1 y [math]d\mid a^{2}+a+1 entonces, por lo ya demostrado, [math]d\mid 3. Eso significa que [math]d debe ser algún divisor positivo de [math]3, por lo tanto [math]d=1 o [math]d=3. [math]\blacksquare

3)

Spoiler: mostrar

Sea [math]u un entero tal que [math]2u+3\mid 19u-2. Todos los valores que encontremos para [math]u serán los valores que puede adoptar [math]n, porque si [math]\frac{19n-2}{2n+3} es entero entonces [math]2n+3\mid 19n-2.

Lo primero que tenemos es la trivialidad [math]2u+3\mid 2u+3. Luego, por la Propiedad 2 [math]2u+3\mid 10\left (2u+3 \right )=20u+30. Por la Propiedad 3 tenemos que [math]2u+3\mid \left (20u+30 \right )-\left ( 19u-2 \right )=u+32. Por la Propiedad 2 [math]2u+3\mid 2\left (u+32 \right )=2u+64. Por la Propiedad 3 tenemos que

[math]2u+3\mid \left (2u+64 \right )-\left ( 2u+3 \right )=61

Por lo tanto [math]2u+3 debe ser algún divisor de [math]61, que es un número primo, y por lo tanto [math]2u+3=-1, [math]2u+3=1, [math]2u+3=61 o [math]2u+3=-61. Resolviendo cada ecuación obtenemos los valores [math]u=-2;-1;29;-32 respectivamente. Y esos son todos los posibles valores de [math]n.

4)

Spoiler: mostrar

Si [math]a\mid b entonces para algún entero [math]k se cumple que [math]b=ak. Si [math]b\mid c entonces para algún entero [math]h se cumple que [math]c=bh. Luego [math]c=akh y por lo tanto [math]a\mid c.

Con respecto a la segunda parte, esto no vale. Un contraejemplo: [math]a=7, [math]c=49 y [math]b=21. [math]\blacksquare

5)

Spoiler: mostrar

Ya lo resolvieron