HMMT February

Solution:

We see that the smallest such $n$ must be a prime power, because if two numbers are distinct mod $n$, they must be distinct mod at least one of the prime powers that divide $n$. For $k \geq 2$, if $a \uparrow \uparrow k$ and $a \uparrow \uparrow (k+1)$ are distinct $\bmod p^{r}$, then $a \uparrow \uparrow (k-1)$ and $a \uparrow \uparrow k$ must be distinct $\bmod \phi\left(p^{r}\right)$. In fact they need to be distinct $\bmod \frac{\phi\left(p^{r}\right)}{2}$ if $p=2$ and $r \geq 3$ because then there are no primitive roots mod $p^{r}$.

Using this, for $1 \leq k \leq 5$ we find the smallest prime $p$ such that there exists $a$ such that $a \uparrow \uparrow k$ and $a \uparrow \uparrow (k+1)$ are distinct $\bmod p$. The list is: $3, 5, 11, 23, 47$. We can easily check that the next largest prime for $k=5$ is $139$, and also any prime power other than $121$ for which $a \uparrow \uparrow 5$ and $a \uparrow \uparrow 6$ are distinct is also larger than $139$.

Now if $a \uparrow \uparrow 6$ and $a \uparrow \uparrow 7$ are distinct $\bmod p$, then $p-1$ must be a multiple of $47$ or something that is either $121$ or at least $139$. It is easy to see that $283$ is the smallest prime that satisfies this.

If $n$ is a prime power less than $283$ such that $a \uparrow \uparrow 6$ and $a \uparrow \uparrow 7$ are distinct $\bmod n$, then the prime can be at most $13$ and clearly this doesn't work because $\phi\left(p^{r}\right) = p^{r-1}(p-1)$.

To show that $283$ works, choose $a$ so that $a$ is a primitive root $\bmod 283, 47, 23, 11, 5$ and $3$. This is possible by the Chinese Remainder theorem, and it is easy to see that this $a$ works by induction.