Generalización Selectivo cono Sur

Avatar de Usuario
3,14

OFO - Medalla de Plata-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Medalla de Oro-OFO 2017 OFO - Medalla de Plata-OFO 2018
FOFO 9 años - Jurado-FOFO 9 años
Mensajes: 457
Registrado: Jue 11 Oct, 2012 5:20 pm
Medallas: 6
Nivel: Exolímpico

Generalización Selectivo cono Sur

Mensaje sin leer por 3,14 »

Un número natural [math] es primo sí y solo sí [math]
Demostración
Spoiler: mostrar
Usaremos el siguiente lema:
Lema: [math] sí y solo sí [math].
Demostración del lema: Supongamos en un comienzo que [math] no divide ni a [math] ni a [math]. Por lo tanto, sus restos en la división por [math] son consecutivos y sus cocientes iguales. En ese caso, la resta daría 0, y no 1.
Si [math] divide a [math], entonces ocurrirá lo mismo.
Sin embargo, si [math], esto equivale a que [math] y que [math], por lo que los cocientes son distintos y se llevan en 1. Por lo tanto la condición se cumple (sabiendo que el cociente de una división es la parte entera de la división).
Pasemos ahora a la demostración principal.
La condición del enunciado equivale a que:
[math]
[math]
[math]
Como [math] para [math], entonces:
[math]
Por lo tanto:
[math]
Como todas las restas son positivas, todas deben ser nulas.
Acá se pone en juego el lema de más arriba, por el cual sabemos que como ninguna resta es igual a [math], entonces [math] no debe tener ningún divisor mayor o igual que [math] y menor o igual que [math], y como [math] no es divisor de [math] salvo que [math], entonces [math] es primo si [math].
Como [math] funciona, entonces Todos los primos cumplen.[math]
Aclaración: en la demostración ya asumí que los únicos posibles valores de [math] son [math] y [math], lo cual se puede ver del siguiente modo:
[math]
[math]
[math]
Como [math] no es entero salvo para [math] (que lo eliminamos en un comienzo), entonces:
[math]
[math]
Avatar de Usuario
Prillo

Colaborador-Varias OFO - Jurado-OFO 2015
Mensajes: 401
Registrado: Sab 18 Dic, 2010 8:52 pm
Medallas: 2

Re: Generalización Selectivo cono Sur

Mensaje sin leer por Prillo »

Spoiler: mostrar
[math] es la cantidad de múltiplos de [math] entre [math] y [math] inclusive. O sea, la cantidad de elementos del conjunto [math]. Luego [math] es igual a la cantidad de elementos del multiconjunto [math]. Sea [math]. Contemos cuantas veces aparece [math] en [math]. Aparece una vez por cada [math] que divide a [math], o sea, tantas veces como divisores tiene. Asi si [math] es la cantidad de divisores de [math], [math] aparece [math] veces en [math]. Luego [math] tiene [math] elementos. O sea que [math]. Ahora el problema se sigue facilmente porque [math], y [math] es primo si y solo si [math].
usuario250

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

Re: Generalización Selectivo cono Sur

Mensaje sin leer por usuario250 »

Spoiler: mostrar
notar que [math] es igual a la cantidad de divisores positivos de n de donde el problema es inmediato.
Responder