Primos y divisibilidad: dos problemas

Voy a comentar en este post las soluciones de los problemas 1 y 2 del primer selectivo para la preselección OMM Tamaulipas 2014. Espero que sirva como feedback para los preseleccionados que no los resolvieron o los resolvieron de otra forma. (Vaya una felicitación para Camilo por su excelente elección de los problemas.)

Problema 1. Sean m,n enteros positivos tales que $m^2+n^2$ es múltiplo de 3. Pruebe que m y n son también múltiplos de 3.

Comentario:

El problema es una proposición de la forma "si... entonces...", es decir, una proposición condicional: si A entonces B, donde A es la condición o hipótesis y B es la tesis o conclusión. Tenemos aquí un ejemplo de que, más acá (es decir, antes) de la teoría de números, está la lógica proposicional.

La solución ateórica

Sin embargo, se puede resolver usando una "lógica natural", preguntándose ¿para que casos la suma de cuadrados deja residuo cero en la división entre 3?

m   n  $m^2+n^2$
0   0   0+0=0
0   1   0+1=1
0   2   0+1=1
1   0   1+0=1
1   1   1+1=2
1   2   1+1=2
2   0   1+0=1
2   1   1+1=2
2   2   1+1=2

Y se ve que el único caso en que la suma de cuadrados es divisible entre 3 es cuando ambos números son divisibles entre 3. Ésta es la solución ateórica.

Bueno, por lo menos esa es la forma en que el entrenador quisiera que razonaran sus alumnos. Sin embargo, hay todavía un más acá de la solución ateórica: ¿tiene el aprendiz la competencia de razonar por casos? ¿puede hacer la lista de todos los posibles? y, en general ¿cuenta el alumno con las estrategias básicas del problem solving? Veamos ahora

La solución teórica

Si se conoce la lógica proposicional, la solución más fácil (y más eficiente) es demostrando la contrapositiva o contrapuesta: si alguno de los números no es múltiplo de 3 entonces la suma de cuadrados no es múltiplo de 3.

Para ello supongamos que m deja residuo 1 o 2 en la división entre 3. Entonces su cuadrado deja residuo 1 en la división entre 3 (ejercicio para el lector). Pero entonces, $1+n^2=0$ no tiene solución (porque necesitaríamos un -1 --algo imposible de lograr con un cuadrado).

Problema 2. Encontrar todos los números primos p,q tales que su suma y su diferencia también son números primos.

Solución

Recordemos que solamente hay un primo par (el 2). Entonces, si ambos primos (p y q) fuesen impares, su suma y su diferencia serían ambas pares. Es decir, no pueden ser ambas números primos. Se concluye que alguno de los primos p o q debe ser el 2.

Con esta inferencia inicial el resto es fácil. Supongamos que p=2. Entonces tenemos que q-2, q y q+2 son primos. Y tenemos una sucesión aritmética de números primos impares de diferencia 2. Pero la única que existe es la 3,5,7 (ejercicio para el lector). Acabamos (como dice Germán).

Los saluda
jmd

PD1: Puede parecer elemental pero puede ser de alguna utilidad para el novicio --para quien nada es lo suficientemente elemental-- el incluir en estas postdatas la prueba de que

La única sucesión aritmética de primos de diferencia 2 es la 3,5,7.

Prueba: Sea p-2,p,p+2 una sucesión aritmética de primos. Claramente uno de ellos es el 3 (pues uno de ellos es múltiplo de 3). Se trata pues de la sucesión 3,5,7.

PD2: En la sucesión p-2,p,p+2 uno de los números es múltiplo de 3 pues  p deja 0,1,2 de residuo en la división entre 3. Si 0, acabamos; si 1, el múltiplo de 3 es el p+2; si 2, lo es el p-2.

PD3: La única sucesión aritmética de primos de diferencia 2 es la 3,5,7. Porque, como se vio en PD2, en p-2,p,p+2, uno es múltiplo de 3. Y si no fuera el 3 ya no sería primo.

PD4: ¿Vieron que nada es lo suficientemente elemental? (Por ejemplo, la sucesión no puede tener más de 3 elementos --se deja como ejercicio para el lector.)