Nacional 2018 P1 N3

Avatar de Usuario
Monazo

OFO - Medalla de Plata
Mensajes: 50
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 1
Nivel: 1

Nacional 2018 P1 N3

Mensaje sin leer por Monazo » Dom 11 Nov, 2018 8:13 am

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.

Avatar de Usuario
Turko Arias

Colaborador OFO - Medalla de Plata
Mensajes: 234
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 2
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Nacional 2018 P1 N3

Mensaje sin leer por Turko Arias » Vie 30 Nov, 2018 11:39 pm

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 :lol: :lol: :lol: ) 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 :roll: :roll: :roll: ) 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 :D
1  

usuario250

OFO - Jurado
Mensajes: 188
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: Nacional 2018 P1 N3

Mensaje sin leer por usuario250 » Lun 03 Dic, 2018 3:22 am

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 :P).
Turko Arias escribió:
Vie 30 Nov, 2018 11:39 pm
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 :lol: :lol: :lol: ) 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 :roll: :roll: :roll: ) 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 :D

Responder