Una propiedad elemental de la divisibilidad

Voy a discutir en este post una propiedad de la divisibilidad que surge cuando la suma de dos números es múltiplo de un primo. Se le podría llamar propiedad de transferencia de la divisibilidad. Incluyo dos instancias de uso en el problem solving de olimpiada.

Una propiedad de transferencia

Considere la suma $a+b$ de dos números enteros y supongamos que es múltiplo de un primo $p$. Puede suceder que ninguno de los sumandos sea múltiplo de $p$. Pero si alguno lo es, entonces también lo es el otro. Formalmente, la propiedad se puede establecer así:

$a,b\in\mathbb{Z},p$ primo, $p|a+b\Rightarrow (p|a\Leftrightarrow p|b)$

La demostración es casi obvia: la suma es múltiplo de $p$ y uno de los sumandos también  ($a+b=rp$ y $a=sp$); por tanto, al despejar el otro sumando y factorizar $p$  ($b=rp-a=rp-sp=(r-s)p$) el resultado se hace evidente.

Instancia de uso

Sean $x,y\in\mathbb{Z}$. Demostrar que $2x+3y$ es múltiplo de 17 si y sólo si $9x+5y$ es múltiplo de 17.

Demostración

Una forma de demostrarlo es evocando la propiedad de transferencia de la divisibilidad en la suma. Con esa idea, lo que hay que buscar es una combinación lineal de las dos expresiones que sea múltiplo de 17.

Para ello, sea $f=2x+3y$ y $g=9x+5y$. Entonces buscamos números enteros $m,n$ de tal manera que $mf+ng$ sea múltiplo de 17. No es difícil ver que $m=4,n=1$ hacen el truco. Es decir, $4f+g=17(x+y)$. Ahora sí, lo que resta es argumentar que --como 4 es primo con 17-- si una de las expresiones es múltiplo de 17, entonces la otra tambien.

Segunda instancia de uso

Considere la sucesión infinita $1,3,5,9,\ldots,2^n+1+\ldots$. Encontrar --con prueba-- todos elementos de la sucesión que son múltiplos de 5.

Demostración

Si consideramos la posición de los elementos de la sucesión desde cero, entonces es claro que los elementos en las posiciones $2,6,10$ son múltiplos de 5. Ello nos lleva a la conjetura de que son múltiplos de 5 los elementos en las posiciones $n=2+4r$, para $r=0,1,2\ldots$.

Para la prueba, definamos $f(r)=2^{4r+2}+1$. Vamos a tratar de expresar $f(r+1)$ en términos de $f(r)$ --más algo que esperamos sea múltiplo de 5-- con la idea de aplicar la propiedad de transferencia de la divisibilidad.

$$f(r+1)=2^{4r+4+2}+1=2^4\cdot2^{4r+2}+1$$

$$=2^4(2^{4r+2}+1-1)+1=2^4f(r)-2^4+1=2^4f(r)-15$$

En resumen, $f(r+1)=2^4f(r)-15$. Así que --aplicando la propiedad de transferencia de la divisibilidad-- si $f(r)$ es múltiplo de 5, entonces $f(r+1)$ también lo es.

Pero $f(0)$ es múltiplo de 5. Por tanto, también lo es $f(1)$ --y con ello también lo es $f(2)$, etc. (el efecto dominó ¿no es cierto?).

En resumen, la respuesta es que todos los números de la forma $2^{2+4r}+1$ son múltiplos de 5. 

Epílogo

Ya sé que es más fácil resolver el segundo problema con aritmética modular. Sólo que ello implica poner a funcionar una herramienta poderosa y cara (su adquisición cuesta tiempo y esfuerzo). Y por esa razón, los aficionados principiantes a las matemáticas de concurso no cuentan con ella.

No obstante --y pensándolo bien-- éste podría ser el momento para una exhibición de la eficacia de la aritmética modular. Quedaría a cargo del novicio decidir si está dispuesto a pagar el costo de su aprendizaje...

Para ilustrar considere este otro problema de la misma familia:

Encontrar todos los valores de $n$ para los cuales $2^n+1$ es múltiplo de 11. 

Solución

Lo que queremos son los $n$ que satisfacen la ecuación de congruencias $2^n\equiv -1\pmod {11}$. Busquemos entonces el 1 y el -1.

El 1 lo encontramos en $2^0$ y el -1 en $2^5$. Por tanto, los múltiplos de 11 son los de la forma $2^{5(2r+1)}+1$ --con $r=0,1,2\ldots$. (El $2r+1$ surge del hecho que $2^{5k}$ puede ser -1 o +1 dependiendo de si la $k$ es impar o par, por ello se necesita que k sea impar.)

Los saluda

jmd