Let $\mathbb{L}$ be a finite field with $q$ elements. Prove that: a) If $q \equiv 3 \pmod 4$ and $n \ge 2$ is a positive integer divisible by $q-1,$ then $x^n=(x^2+1)^n$ for all $x \in \mathbb{L}^{\times}.$ b) If there exists a positive integer $n \ge 2$ such that $x^n=(x^2+1)^n$ for all $x \in \mathbb{L}^{\times},$ then $q \equiv 3 \pmod 4$ and $q-1$ divides $n.$
Problem
Source: Romanian National Olympiad 2024 - Grade 12 - Problem 4
Tags: finite fields, abstract algebra
03.04.2024 16:07
a) Note that $-1$ is not square mod $q$ hence $a:={{x^2+1}\over x}\in L^*$. Also $a^{q-1}=1 \implies a^n=1$. b) If $q=2$ or $q\equiv 1(4)$ then we have $x^2+1=0$ for some $x\in L^*$. Then $x^n\not=(x^2+1)^n$, contradiction. Hence $q\equiv 3(4)$. Now let's consider the range of the function $f:L^*\rightarrow L^*, f(x)=x+1/x$. We have $f(x)=f(y)\iff x=y\vee xy=1$. Hence the values $f(1),f(-1)$ appear only once and on the other entries the function $f$ is $2:1$. Hence $|f(L^*)|=2+{{q-3}\over 2}={{q+1}\over 2}$. It is given that the subgroup $G:=\{t\in L^*: t^n=1\}$ contains $f(L^*)$ hence $|G|>{{q-1}\over 2}\implies G=L^*\implies t^n=1$ on $L^*$. Also note that $L^*$ is cyclic of order $q-1$. Hence $(q-1)|n$ and we are done.
13.06.2024 21:09
(a) By Lagrange, $x^n=(x^2+1)^n=1$ if $x^2+1\neq 0$. Let $\mathbb{L}^\times=:\langle g\rangle$. Let \[ G:=\{a^2\mid a\in\mathbb{L}^\times\}=\langle g^2\rangle. \]Since $-1=g^{\frac{q-1}{2}}$ and $\frac{q-1}{2}$ is odd, $-1\not\in G$. The conclusion follows. $\square$ (b) Let $r<q-1$ be the remainder when $n$ is divided by $q-1$. Assume for the sake of contradiction $r>0$. By Lagrange, $x^r=(x^2+1)^r$ for all $x\in\mathbb{L}^\times$. It follows that the elements of $\mathbb{L}^\times$ are roots of $(x^2+1)^r-x^r$ so $x^{q-1}-1\mid (x^2+1)^r-x^r$. Thus $(x^{q-1}-1)P(x)=(x^2+1)^r-x^r$ for some $P(x)\in\mathbb{L}[x]$ so $\deg P=2r-(q-1)<r$. Consider the term $a_rx^r$ in $(x^2+1)^r-x^r$. If $r$ is odd, $a_r=-1$. Since $r<q-1$, it follows that $P(x)$ has a $x^r$ term. But then $\deg P\geq r$, a contradiction. Thus $r$ is even. Now $a_r=\binom{r}{r/2}-1$. If $a_r\neq 0$, we are done as before. Thus $\binom{r}{r/2}=1$. Now consider the term $\binom{r}{r/2+1}x^{r+2}$ in $(x^2+1)^r-x^r$. We have \[ \binom{r}{r/2+1}=\frac{r/2}{r/2+1}\binom{r}{r/2}=\frac{r/2}{r/2+1}. \]Since $r<q-1$, it follows that $\frac{r/2}{r/2+1}\neq-1$. Since $q-1$ is even, we must have $r\leq q-3$. If $P(x)$ has an $x^{r+2}$ term, we are done as before. Thus the coefficient of $x^{r+2-(q-1)}=x^0$ in $P(x)$ is $\binom{r}{r/2+1}\neq-1$. But now the constant term of $(x^{q-1}-1)P(x)$ is not $1$, a contradiction. Thus $r=0$, as desired. Clearly $q$ cannot be a power of $2$ due to $x=1$. Assume for the sake of contradiction $q\equiv 1\pmod{4}$. Let $\mathbb{L}^\times=:\langle g\rangle$ so $-1=g^{\frac{q-1}{2}}$. Then $\left(g^{\frac{q-1}{4}}\right)^2=-1$ so $\left(\left(g^{\frac{q-1}{4}}\right)^2+1\right)^n=0\neq1=\left(g^{\frac{q-1}{4}}\right)^n$, a contradiction. Thus $q\equiv 3\pmod{4}$. $\square$