Nacional 2018 P1 N3

[Monazo]

Sea $p$ un número primo y $r$ el resto de la divisón de $p$ por $210$. Se sabe que $r$ es un número compuesto y que se puede escribir como suma de dos cuadrados perfectos distintos de cero. Hallar todos los primos menores que $2018$ que satisfacen estas condiciones.

[Turko Arias]

Spoiler: mostrar

Sea $(r, 210)=d$, tenemos que $p=210q+r$ para algún entero positivo $q$, con lo que, si $d$ no es $1$, $p$ sería divisible por $d$ y por ende no sería primo ($d$ no puedes ser igual a $p$ ya que en ese caso quedaría $r=p$ con lo que $r$ no sería compuesto). Notamos que $\varphi(210)=\varphi(2.3.5.7)=\varphi(2)\varphi(3)\varphi(5)\varphi(7)=48$. Por otro lado chequeamos en nuestra tabla de números primos (es un Certamen Nacional así que todos tenemos una ) que hay $42$ números primos menores que $210$ coprimos con $210$, pero $r$ es compuesto, con lo que quedan $6$ valores posibles para $r$, que son $1, 121, 143, 169, 187$ y $209$. Como $r$ es compuesto, descartamos el $1$, y como $r$ es suma de cuadrados perfectos, por esta fantástica propiedad podemos descartar al $143$, al $187$ y al $209$. Por otro lado, la propiedad nos habla de suma de cuadrados NO NEGATIVOS, por lo que el $121$ en principio podría servir, pero a mano verificamos que no hay dos cuadrados no nulos que sumen $121$. Luego, el único valor posible es $r=169$, ya que $169=12^2+5^2$. Chequeamos ahora nuevamente en nuestra lista de primos (que en serio hay que tener una impresa para el Nacional ) si alguno de los números de la forma $210q+169$ menores que $2018$ es primo:
$379 \checkmark \\
589 \\
799 \\
1009 \checkmark \\
1219 \\
1429 \checkmark \\
1639 \\
1849 $

Y eso es todo amigos

[usuario250]

Para los 6 valores posibles de r, se podría haber hecho un tanteo medio rápido de cuál es la factorización por primos de cada r, teniendo en cuenta que 210 = 2*3*5*7, entonces ni 2, ni 3, ni 5, ni 7 divide a r y solo queda buscar las posibles factorizaciones por primos para números menores a 210 que no contengan los primos antes mencionados (y que no sean números primos ).

Spoiler: mostrar

Sea $(r, 210)=d$, tenemos que $p=210q+r$ para algún entero positivo $q$, con lo que, si $d$ no es $1$, $p$ sería divisible por $d$ y por ende no sería primo ($d$ no puedes ser igual a $p$ ya que en ese caso quedaría $r=p$ con lo que $r$ no sería compuesto). Notamos que $\varphi(210)=\varphi(2.3.5.7)=\varphi(2)\varphi(3)\varphi(5)\varphi(7)=48$. Por otro lado chequeamos en nuestra tabla de números primos (es un Certamen Nacional así que todos tenemos una ) que hay $42$ números primos menores que $210$ coprimos con $210$, pero $r$ es compuesto, con lo que quedan $6$ valores posibles para $r$, que son $1, 121, 143, 169, 187$ y $209$. Como $r$ es compuesto, descartamos el $1$, y como $r$ es suma de cuadrados perfectos, por esta fantástica propiedad podemos descartar al $143$, al $187$ y al $209$. Por otro lado, la propiedad nos habla de suma de cuadrados NO NEGATIVOS, por lo que el $121$ en principio podría servir, pero a mano verificamos que no hay dos cuadrados no nulos que sumen $121$. Luego, el único valor posible es $r=169$, ya que $169=12^2+5^2$. Chequeamos ahora nuevamente en nuestra lista de primos (que en serio hay que tener una impresa para el Nacional ) si alguno de los números de la forma $210q+169$ menores que $2018$ es primo:
$379 \checkmark \\
589 \\
799 \\
1009 \checkmark \\
1219 \\
1429 \checkmark \\
1639 \\
1849 $

Y eso es todo amigos