Estonian Mathematical Olympiad

Both the pair $(n,n+1)$ and $(n,n+3)$ must contain one odd number. This odd number must be divisible by the square of one of the following numbers: $$15=3\cdot 5,21=3\cdot 7,33=3\cdot 11,35=5\cdot 7,39=3\cdot 13,45=3^2\cdot 5,\dots$$ Their squares are $225$, $441$, $1089$, $1225$, $1521$, $2025$, .... Thus either $n$ or $n+1$ or $n+3$ must be a multiple of one of these squares.

a. We cannot have $n+1=225$ or $n=225$, as neither $224=2^5\cdot 7$ nor $226=2\cdot 113$ is divisible by two prime squares. Similarly, we cannot have $n+1=441$ or $n=441$, as $440=2^3\cdot 5\cdot 11$ and $442=2\cdot 13\cdot 17$. We also cannot have $n+1=3\cdot 225=675$, as $674=2\cdot 337$. But $n=675$ works, as $676=2^2\cdot 13^2$. Thus the desired $n$ is $675$.

b. In the solution to part (a) we saw that both $675$ and $676$ are divisible by two prime squares. Therefore, so must also the numbers $3\cdot 675=2025$ and $3\cdot 676=2028$. Thus $n=2025$ has the desired properties. It remains to show that there are no smaller such numbers. The only option for $n$ or $n+3$ not divisible by $2^2$ or $3^2$ is $1225$, but we cannot have either $n+3=1225$ or $n=1225$, as $1222=2\cdot 13\cdot 47$ and $1228=2^2\cdot 307$. We may now assume that one of $n$ and $n+3$ is divisible by $2^2$ and the other by $3^2$, as they cannot be divisible by the same prime square.

The odd number out of $n$ and $n+3$ is either one of the odd multiples of $225$, which are $225$, $675$, $1125$ and $1575$, one of the odd multiples of $441$, which are $441$ and $1323$, or one of $1089$ and $1521$. For each of them, only one of the numbers differing from it by $3$ is divisible by $2^2$, so it remains to check that these numbers do not contain any other prime factors squared: $$ $$\begin{array}{rl}225& \to 228=2^2\cdot 3\cdot 19,\\ 675& \to 672=2^2\cdot 3\cdot 56,\\ 1125& \to 1128=2^2\cdot 3\cdot 94,\\ 1575& \to 1572=2^2\cdot 3\cdot 131,\\ 441& \to 444=2^2\cdot 3\cdot 37,\\ 1323& \to 1320=2^2\cdot 3\cdot 110,\\ 1089& \to 1092=2^2\cdot 3\cdot 91,\\ 1521& \to 1524=2^2\cdot 3\cdot 127.\end{array}$$