Find the smallest integer $n$ for which $n^n$ does not divide $2016!$

Question

The following was a question in the final of the Flanders Mathematics Olympiad 2016:

Find the smallest integer $n$ for which $n^n$ does not divide $2016!$

Points are assigned not only for finding the right answer, but also for formulating a rigorous and mathematically sound proof. To solve this question, I used the following reasoning:

Since $44^2 = 1936 < 2016 < 45^2 = 2025,$ we are looking for a number $n$ larger than 44, since otherwise the factor $n$ occurs at least $n$ times in 2016! (e.g., $1 \cdot 44 = 44,$ $2 \cdot 44 = 88,$ $\ldots,$ $45 \cdot 44 = 1980$). Furthermore, the number $n$ must be prime, since otherwise $n = ab$ with both $a$ and $b$ occurring more than $n$ times in $2016!.$ As such, the smallest integer $n=47.$

I don't feel like this answer is adequate enough, as my reasoning is very intuitive. How can I change this answer into a more rigorous and mathematically sound proof that $n=47$ indeed is the smallest integer for which $n^n$ does not divide $2016!$?

Answer 1

Your argument is close to okay.

Recall the well-known

Lemma. If $p$ is prime, then the exponent $k$ with $p^k\|2016!$ (i.e., with $p^k\mid 2016!$ and $p^{k+1}\nmid 2016!$) is given by $$ 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.$$

Claim 1. For $n=47$ we have $n^n\nmid 2016!$.

Proof. As $n=47$ is prime, we find from the lemma that $n^{42}\|2016!$, and $42<n$. $\square$

Claim 2. If $n=p^a$ is a prime power $<47$ then $n^{47}\mid 2016!$.

Proof. As $n<47$, we must have

• $a=1$ and $p\le 43$
• or $p\le 5$ (because $7^2>47$) and $a\le 5$ (because $2^6>47$)

Case 1: Assume $a=1$ and $p\le 43$. As each $p\le 43$, we find from the lemma and $\lfloor \frac{2016}{p}\rfloor+\lfloor \frac{2016}{{p}^2}\rfloor\ge \lfloor \frac{2016}{43}\rfloor+\lfloor \frac{2016}{43^2}\rfloor=47$ that $p^{47}\mid 2016!$.

Case 2: Assume $p\le 5$ and $a\le 5$. Then $$\left\lfloor\frac{2016}{p}\right\rfloor+ \ldots\ge 403.$$ Thus $p^{17a}\mid p^{47\mid 5}\mid p^{502}\mid 2016!$.

We conclude that $n^{47}=(p^{47a})\mid 2016!$. $\square$

Claim 3. If $n<47$ then $n^n\mid 2016!$.

Proof. Consider the priem factorization $n=p_1^{a_1}\cdots p_m^{a_m}$ of $n$. By claim 2, we have $p_i^{47a_i}\mid 2016!$ for $1\le i\le m$. As the $p_i^{47a_i}$ are pairwise coprime, it follows that $$n^n\mid n^{47}=p_1^{47a_1}\cdot p_m^{47a_m}\mid 2016! $$ $\square$

Claim 1 and claim 3 together express that $47$ is the smallest $n$ with $n^n\nmid 2016!$.

---

Bonus question: If we replace $2016$ with $N$, will the answer always be the smallest prime $p> \sqrt{N}$?

Answer 2

I mean, you have already clearly proven that the number n must be >44. That's a fact.

You have also "proven" that it must be prime (Check lemma 2 to see why I included quotations)

So now we're looking at primes p>44.

You go for 47 and prove that it has this property and know that it is the smallest prime larger than 44.

That seems like a solid proof. It may not seem robust because you are not phrasing it as such. However, the proof seems sound. (other than the issue on lemma 2)

I would suggest throwing some more explanations and maybe proving both of your lemmas (you seem to only explain the proof for n being prime but not actually proving it).

I would try with $$Lemma 1: n>44$$ $$Proof:$$ Assume $$n\leq 44$$ $2016!$ contains factors $n$, $2n$, $3n$, ..., $kn$ $$k= \big\lfloor \frac{2016}{n} \big\rfloor $$ $$k \geq 45$$ thus, 2016! contains at least $n$ factors of $n$ and so $n^n$ divides $2016!$ $$\Rightarrow \Leftarrow$$

Now for the next one $$Lemma 2:$$ $n$ $must$ $be$ $prime$

This proof is not as straightforward as the previous one. In fact I'm not convinced your reasoning is strong enough because $n^n$ not dividing 2016! implies $a^n$ or $b^n$ not dividing 2016! but not necessarily $a^a$ or $b^b$

However, I intuitively understand your point and believe there must be some sort of proof (maybe a case by case one or something like that for lemma 2). I'm just not in the mood to find one myself.

Once you get that part squared away, you know that you're looking for primes >44 and you can conclude that 47 has the property of not dividing 2016! (with some calculations) and is the smallest number because it is also the smallest integer that has the properties of satisfying lemmas 1 and 2.

That's a pretty robust proof