IMO Team Selection Contest

As $a^p \equiv 1 \pmod{q}$ while $a \neq 1 \pmod{q}$, the case $q = 2$ is impossible. Thus, the desired equation is equivalent to
$$(1 + a^0)(1 + a^1)(1 + a^2)\dots(1 + a^{p-1}) \equiv 2 \pmod{q}. \quad (13)$$
Removing parentheses in the l.h.s. of (13) gives all monomials of the form $a^{i_1+\dots+i_k}$ where $\{i_1, \dots, i_k\} \subseteq \{0, 1, \dots, p-1\}$. As $a^p \equiv 1 \pmod{q}$, the sums in the exponents can be replaced with their remainders modulo $p$. We claim that each possible remainder is produced the same number of times provided that we leave out the empty set and the whole set $\{0, 1, \dots, p-1\}$. Indeed, for each tuple $(i_1, \dots, i_k)$ where $0 < k < p$, we can find $l$ such that $kl \equiv 1 \pmod{p}$ and form a new tuple $(i_1 + l, \dots, i_k + l)$ for which $(i_1 + l) + \dots + (i_k + l) \equiv i_1 + \dots + i_k + 1 \pmod{p}$. Clearly different tuples lead to different new tuples. Thus, for any remainder $i$, there are at least as many tuples with sum congruent to $i+1$ as tuples with sum congruent to $i$. Doing this $p$ times, we get back to the beginning and hence there are equal number of tuples giving each remainder.
Let this constant number of tuples be $c$. Then (13) is equivalent to
$$a^0 + a^{0+1+\dots+(p-1)} + c(a^0 + a^1 + \dots + a^{p-1}) \equiv 2 \pmod{q}.$$
As $p = \frac{(p-1)p}{2} = 0 + 1 + \dots + (p-1)$, we have $a^{0+1+\dots+(p-1)} \equiv 1 \pmod{q}$. Moreover, as $(a^0 + a^1 + \dots + a^{p-1})(a-1) = a^p - 1 \equiv 0 \pmod{q}$ while $a-1 \neq 0 \pmod{q}$, we also have $a^0 + a^1 + \dots + a^{p-1} \equiv 0 \pmod{q}$. Consequently, (13) is equivalent to $1+1 \equiv 2 \pmod{q}$ which holds trivially.

Like in Solution 1, prove that $q$ is odd. By assumptions, the order of $a$ modulo $q$ divides $p$ and does not equal 1. Hence the order of $a$ modulo $q$ must be $p$. Thus $1, a, a^2, \dots, a^{p-1}$ are pairwise incongruent modulo $q$. This implies that the residue classes of $1, a, a^2, \dots, a^{p-1}$ are all distinct roots of the polynomial $x^p - 1$ in $\mathbb{Z}_q$. Thus in $\mathbb{Z}_q$ we have $x^p - 1 = (x-1)(x-a)(x-a^2)\dots(x-a^{p-1})$. After substituting $x = -1$ and dividing all factors in the r.h.s. except the first one by $-1$, we obtain an equivalent congruence $-2 \equiv -2(1+a)(1+a^2)\dots(1+a^{p-1}) \pmod{q}$. As $q \neq 2$, division by $-2$ is possible and gives the desired congruence.

Rewrite each factor $1 + a^i$ in the form $\frac{1-a^{2i}}{1-a^i}$. Since $p-1$ is even and $a^p \equiv 1 \pmod q$, we obtain
$$\begin{aligned} & (1 - a^2)(1 - a^4)\dots(1 - a^{2(p-1)}) \\ &= (1 - a^2)(1 - a^4)\dots(1 - a^{p-1})(1 - a^{p+1})(1 - a^{p+3})\dots(1 - a^{2p-2}) \\ &\equiv (1 - a^2)(1 - a^4)\dots(1 - a^{p-1})(1 - a^1)(1 - a^3)\dots(1 - a^{p-2}) \\ &= (1 - a^1)(1 - a^2)\dots(1 - a^{p-1}) \pmod{q}. \end{aligned}$$
As $a^p \equiv 1 \pmod q$, the least exponent $i$ for which $a^i \equiv 1 \pmod q$ must divide $p$; as $a \not\equiv 1 \pmod q$, the least exponent must equal $p$. Therefore none of the factors $1-a^1, 1-a^2, \dots, 1-a^{p-1}$ is divisible by $q$. This means that the congruence above can be reduced by these factors, i.e.,
$$\frac{(1 - a^2)(1 - a^4)\dots(1 - a^{2(p-1)})}{(1 - a^1)(1 - a^2)\dots(1 - a^{p-1})} \equiv \frac{(1 - a^1)(1 - a^2)\dots(1 - a^{p-1})}{(1 - a^1)(1 - a^2)\dots(1 - a^{p-1})} \pmod{q}.$$
This proves the claim.