74th Romanian Mathematical Olympiad

a) As the multiplicative group ${\mathbb{L}}^{\ast }$ has order $q-1$, we have for any $x\in {\mathbb{L}}^{\ast }$, $x^{q-1}=1$, and as $n$ is a multiple of $q-1$, we get $x^n=1$, for any $x\in {\mathbb{L}}^{\ast }$. Because $4$ is not a divisor of the order $q-1$ of the group ${\mathbb{L}}^{\ast }$, there are no elements of order $4$ in ${\mathbb{L}}^{\ast }$, so $x^2\ne -1$ for any $x\in {\mathbb{L}}^{\ast }$. Thus $x^2+1\ne 0$, so $(x^2+1{)}^n=1$, for all $x\in {\mathbb{L}}^{\ast }$. In conclusion $x^n=(x^2+1{)}^n$, for $x\in {\mathbb{L}}^{\ast }$.

b) If $\text{char}(\mathbb{L})=2$, we would conclude $1=1^n=(1^2+1{)}^n=0$, a contradiction. So $q$ is odd. In case $q\equiv 1(\mathrm{mod}4)$, consider a generator $a$ of the group ${\mathbb{L}}^{\ast }$, and consider $b=a^{\frac{q-1}{4}}$. Thus $b$ has order $4$ in ${\mathbb{L}}^{\ast }$, that is $b^2\ne 1=(b^2{)}^2$. This implies $b^2=-1$ and $b^n=(b^2+1{)}^n=0$, a contradiction. Consequently $q\equiv 3(\mathrm{mod}4)$. Consider the sets $A=\{x+x^{-1}\mid x\in {\mathbb{L}}^{\ast }\}$ and $H=\{x\in {\mathbb{L}}^{\ast }\mid x^n=1\}$. Because ${\mathbb{L}}^{\ast }$ is abelian, $H$ is a subgroup of ${\mathbb{L}}^{\ast }$. By the hypothesis, for any $y\in A$ there is $x\in {\mathbb{L}}^{\ast }$ with $y=x+x^{-1}=x^{-1}(x^2+1)$, such that $y^n=x^{-n}(x^2+1{)}^n=1$. As a conclusion, $A\subseteq H$. Define $f:{\mathbb{L}}^{\ast }\to A$ by $f(x)=x+x^{-1}$. By the definition of $A$, $f$ is onto ${\mathbb{L}}^{\ast }={\bigcup }_{y\in A}{f}^{-1}(y)$ that is $q-1=|{\mathbb{L}}^{\ast }|={\sum }_{y\in A}|f^{-1}(y)|$. Let $u,v\in {\mathbb{L}}^{\ast }$ such that $f(u)=f(v)$, implying $$u+u^{-1}=v+v^{-1}⟺u-v=v^{-1}-u^{-1}⟺(u-v)(uv-1)=0⟺v\in \{u,u^{-1}\}.$$ As $u=u^{-1}⟺u^2=1⟺u\in \{1,-1\}$, we get $|f^{-1}(2\cdot 1)|=|f^{-1}(f(1))|=1$, $|f^{-1}(2\cdot (-1))|=|f^{-1}(f(-1))|=1$ and $|f^{-1}(y)|=2$, for all $y\in A\setminus \{2\cdot 1,2\cdot (-1)\}$. Collecting, we get $$q-1=|{\mathbb{L}}^{\ast }|=1+1+2\cdot (|A|-2)=2\cdot |A|-2,$$ thus $|A|=\frac{q+1}{2}$. As $A\subseteq H$, we get $|H|\ge \frac{q+1}{2}>\frac{1}{2}\cdot |{\mathbb{L}}^{\ast }|$. But $H$ is a subgroup of ${\mathbb{L}}^{\ast }$, so $H={\mathbb{L}}^{\ast }$. As a consequence, $x^n=1$, for any $x\in {\mathbb{L}}^{\ast }$. Thus we proved that for the generator $a$ with $\text{ord}(a)=q-1$ we have $a^n=1$, implying that $q-1$ is a divisor of $n$.