Serbian Mathematical Olympiad

Ответ. For $n=1$ and $n=2$.

For $n=1$, any even $a$ of the form $m^2+1$ works, for example, $a=2$.

For $n=2$, any even $a$ of the form $m^2-1$ works, for example, $a=8$.

Assume that for $n=3$, such a number $a$ exists. Then the number $(a-1)(a^2-1)(a^3-1) = (a-1)^3(a+1)(a^2+a+1)$ must be a perfect square. Since $a^2+a+1 = a(a+1)+1$, the numbers $a+1$ and $a^2+a+1$ are coprime. Because $a+1$ is odd, the numbers $a+1$ and $a-1$ are also coprime. Therefore, both $a+1$ and $(a-1)(a^2+a+1)$ must be perfect squares. In particular, $a + 1$ modulo 3 can only be 0 or 1, and thus $a - 1$ is not divisible by 3. Hence,
$$\begin{align*} \gcd(a - 1, a^2 + a + 1) &= \gcd(a - 1, (a + 2)(a - 1) + 3) = \\ &= \gcd(a - 1, 3) = 1, \end{align*}$$
meaning that both $a-1$ and $a^2+a+1$ must be perfect squares.
However, the latter cannot be a square, since $a^2 < a^2+a+1 < (a+1)^2$. This is a contradiction.

It remains to prove that no such $a$ exists for $n \geq 4$. Suppose such an $a$ exists. Take a natural number $k \geq 2$ such that $2^k \leq n < 2^{k+1}$. Since $a^{2^k} - 1 = (a^{2^k} - 1)(a^{2^k} + 1)$, the number $(a - 1)(a^2 - 1) \dots (a^n - 1)$ can be expressed as the product of $a^{2^k} - 1 + 1$ and several other factors of the form $a^m - 1$, where $1 \leq m \leq n$ and $m \neq 2^k$.
We will show that the factor $a^{2^{k-1}} + 1$ is coprime with all other factors in this decomposition. Suppose $a^{2^{k-1}} + 1$ and $a^m - 1$ share a common divisor $d$. Then $\gcd(a^{2^k} - 1, a^m - 1)$ is divisible by $d$. But $\gcd(a^{2^k} - 1, a^m - 1) = a^{\gcd(2^k,m)} - 1$. Since $m \neq 2^k$ and $m \leq n < 2^{k+1}$, the number $m$ cannot be divisible by $2^k$. Thus, $\gcd(2^k, m)$ is a power of two not exceeding $2^{k-1}$. Therefore, $a^{2^{k-1}-1}$ divides $\gcd(a^{2^k}-1, a^m-1)$, and hence also divides $d$. Because $a$ is even, the numbers $a^{2^{k-1}-1}$ and $a^{2^{k-1}}+1$ have no common divisors other than 1, so $d=1$, as required.
The factor $a^{2^{k-1}} + 1$ is coprime with all other factors in the product, which is a perfect square, so it must itself be a perfect square. Then $a^{2^{k-1}} + 1$ and $a^{2^{k-1}}$ are perfect squares differing by 1, which is impossible. Therefore, our assumption is false, and no such $a$ exists for $n \geq 4$.

For $n=1$ and $n=2$.

For $n=1$, any even number $a$ of the form $m^2 + 1$ works, for example, $a = 2$.

For $n = 2$, any even number $a$ of the form $m^2 - 1$ works, for example, $a = 8$.

Assume that for $n = 3$, such a number $a$ exists. Then the number $(a-1)(a^2-1)(a^3-1) = (a-1)^3(a+1)(a^2+a+1)$ must be a perfect square. Since $a^2+a+1 = a(a+1)+1$, the numbers $a+1$ and $a^2+a+1$ are coprime. As $a+1$ is odd, the numbers $a+1$ and $a-1$ are also coprime. Therefore, both $a+1$ and $(a-1)(a^2+a+1)$ must be perfect squares. In particular, $a+1$ modulo $3$ can only be $0$ or $1$, and thus $a-1$ is not divisible by $3$. Hence,
$$\begin{aligned} \gcd(a-1, a^2+a+1) &= \gcd(a-1, (a+2)(a-1)+3) = \\ &= \gcd(a-1, 3) = 1, \end{aligned}$$
meaning that both $a-1$ and $a^2+a+1$ must be perfect squares. However, the latter cannot be a square, since $a^2 < a^2+a+1 < (a+1)^2$. This is a contradiction.

It remains to prove that no such $a$ exists for $n \ge 4$. Suppose such an $a$ exists. Take a natural number $k \ge 2$ such that $2^k \le n < 2^{k+1}$. Since $a^{2^k} - 1 = (a^{2^{k-1}} - 1)(a^{2^{k-1}} + 1)$, the number $(a-1)(a^2-1)\dots(a^n-1)$ can be expressed as the product of $a^{2^{k-1}} + 1$ and several other factors of the form $a^m - 1$, where $1 \le m \le n$ and $m \ne 2^k$.

We will show that the factor $a^{2^{k-1}} + 1$ is coprime with all other factors in this decomposition. Suppose $a^{2^{k-1}} + 1$ and $a^m - 1$ share a common divisor $d$. Then $\gcd(a^{2^k} - 1, a^m - 1)$ is divisible by $d$. But $\gcd(a^{2^k} - 1, a^m - 1) = a^{\gcd(2^k,m)} - 1$. Since $m \ne 2^k$ and $m \le n < 2^{k+1}$, the number $m$ cannot be divisible by $2^k$. Thus, $\gcd(2^k, m)$ is a power of two not exceeding $2^{k-1}$. Therefore, $a^{2^{k-1}-1}$ divides $\gcd(a^{2^k} - 1, a^m - 1)$, and hence also divides $d$. Because $a$ is even, the numbers $a^{2^{k-1}-1}$ and $a^{2^{k-1}} + 1$ have no common divisors other than $1$, so $d = 1$, as required.

The factor $a^{2^{k-1}} + 1$ is coprime with all other factors in the product, which is a perfect square, so it must itself be a perfect square. Then $a^{2^{k-1}} + 1$ and $a^{2^{k-1}}$ are perfect squares differing by $1$, which is impossible. Therefore, our assumption is false, and no such $a$ exists for $n \ge 4$.