Encontrar el entero más pequeño $n$ que $n^n$ no divide $2016!$

Question

La siguiente es una pregunta que estaba en la final de la Flandes Olimpiada de Matemáticas de 2016:

Encontrar el entero más pequeño $n$ que $n^n$ no divide $2016!$

Se asignan puntos, no sólo para encontrar la respuesta correcta, sino también para la formulación de un riguroso y matemáticamente a prueba de sonido. Para resolver esta cuestión, he utilizado el siguiente razonamiento:

Desde $44^2 = 1936 < 2016 < 45^2 = 2025$, estamos buscando un número $n$ mayores de 44 años, ya que de lo contrario el factor de $n$ se produce, al menos, $n$ veces en el 2016! (por ejemplo,$1\times 44 = 44$, $2 \times 44 = 88$, ..., $45 \times 44 = 1980$). Además, el número de $n$ debe ser un primo, ya que de lo contrario $n = a \times b$ y el tanto $a$ $b$ se producen más de $n$ veces $2016!$. Como tal, el entero más pequeño $n=47$.

Yo no siento que esta respuesta es suficiente, ya que mi razonamiento es muy intuitivo. ¿Cómo puedo cambiar esta respuesta en un más riguroso y matemáticamente a prueba de sonido que $n=47$, de hecho es el entero más pequeño para que $n^n$ no divide $2016!$?

Answer 1

Su argumento está cerca de bien.

Recordemos el conocido

Lema. Si $p$ es primo, entonces el exponente $k$ $p^k\|2016!$ (es decir, con $p^k\mid 2016!$$p^{k+1}\nmid 2016!$) está dada por $$ k=\left\lfloor\frac{2016}{p}\right\rfloor+\left\lfloor\frac{2016}{p^2}\right\rfloor+\left\lfloor\frac{2016}{p^3}\right\rfloor +\ldots.$$

Reivindicación 1. Para $n=47$ tenemos $n^n\nmid 2016!$.

Prueba. Como $n=47$ es primo, nos encontramos en el lema que $n^{42}\|2016!$, e $42<n$. $\square$

Reivindicación 2. Si $n=p^a$ es una fuente primaria de energía $<47$$n^{47}\mid 2016!$.

Prueba. Como $n<47$, debemos tener

• $a=1$ $p\le 43$
• o $p\le 5$ (debido a $7^2>47$) y $a\le 5$ (debido a $2^6>47$)

Caso 1: Supongamos $a=1$$p\le 43$. Como cada una de las $p\le 43$, podemos encontrar desde el lexema y $\lfloor \frac{2016}{p}\rfloor+\lfloor \frac{2016}{{p}^2}\rfloor\ge \lfloor \frac{2016}{43}\rfloor+\lfloor \frac{2016}{43^2}\rfloor=47$ que $p^{47}\mid 2016!$.

Caso 2: Supongamos $p\le 5$$a\le 5$. Entonces $$\left\lfloor\frac{2016}{p}\right\rfloor+ \ldots\ge 403.$$ Por lo tanto $p^{17a}\mid p^{47\mid 5}\mid p^{502}\mid 2016!$.

Llegamos a la conclusión de que $n^{47}=(p^{47a})\mid 2016!$. $\square$

Reivindicación 3. Si $n<47$$n^n\mid 2016!$.

Prueba. Considerar la priem factorización $n=p_1^{a_1}\cdots p_m^{a_m}$$n$. Por la reivindicación 2, tenemos $p_i^{47a_i}\mid 2016!$$1\le i\le m$. Como el $p_i^{47a_i}$ son parejas coprime, se sigue que $$n^n\mid n^{47}=p_1^{47a_1}\cdot p_m^{47a_m}\mid 2016! $$ $\square$

Reivindicación 1 y la reivindicación 3 juntos expresar que $47$ es el más pequeño de $n$$n^n\nmid 2016!$.

---

Pregunta extra: Si reemplazamos $2016$$N$, la respuesta siempre es la más pequeña prime $p> \sqrt{N}$?

Answer 2

Quiero decir, que ya han demostrado claramente que el número n debe ser >44. Eso es un hecho.

También ha "demostrado" que debe ser un primo (Marque lema 2 para ver por qué he incluido las citas)

Así que ahora estamos viendo los números primos p>44.

Vaya para el 47 y demostrar que tiene esta propiedad y sabemos que es el más pequeño de los primos de más de 44.

Que parece una prueba sólida. No parece sólida, porque no fraseo como tal. Sin embargo, la prueba parece de sonido. (aparte de la cuestión en el lema 2)

Yo sugeriría a tirar algunos más explicaciones y tal vez demostrando tanto de su lema (parece que sólo explican la prueba para n primos, pero en realidad no probarlo).

Me gustaría tratar con $$Lemma 1: n>44$$ $$Proof:$$ Suponga $$n\leq 44$$ $2016!$ contiene factores $n$, $2n$, $3n$, ..., $kn$ $$k= \big\lfloor \frac{2016}{n} \big\rfloor $$ $$k \geq 45$$ por lo tanto, 2016! contiene, al menos, $n$ factores de $n$ $n^n$ divide $2016!$ $$\Rightarrow \Leftarrow$$

Ahora a por la siguiente $$Lemma 2:$$ $n$ $$ $$ $prime$

Esta prueba no es tan sencillo como el anterior. De hecho, no estoy convencido de que tu razonamiento es bastante fuerte, debido a que $n^n$ no dividir 2016! implica $a^n$ o $b^n$ no dividir 2016! pero no necesariamente $a^a$ o $b^b$

Sin embargo, yo intuitivamente entender su punto y creo que deben haber algún tipo de prueba (tal vez se de el caso de uno o algo así por lema 2). Simplemente no estoy de humor para encontrar uno mismo.

Una vez que parte el cuadrado de la distancia, usted sabe que usted está buscando primos >44 y se puede concluir que el 47 tiene la propiedad de no dividir 2016! (con algunos cálculos) y es el número más pequeño, porque también es el entero más pequeño que tiene las propiedades de la satisfacción de los lemas 1 y 2.

Eso es bastante robusto a prueba de

Answer 3

Para mí es claro que n=3 es suficiente. $3^3 = 27$, y el 27 de no dividir 2016. 4 ¿se divida, por lo que 3 es el entero más pequeño que con esa propiedad. Ahora es cuestión de probar esta sin usar una calculadora.