When I first submitted this question some days ago (prior to the publication of the BMO problems) a user solved it but the whole thread go deleted by the mods. Please, feel free to rewrite the solution again.

You've got to be kidding me. Let $t$ be a root of $x^2 - ax + 1$. If $x^2 - ax + 1$ splits in $\mathbb{F}_p[x]$, then $t \in \mathbb{F}_p$; otherwise $t \in \mathbb{F}_{p^2}$. Either way, $t \in \mathbb{F}_{p^2}$. Then $a = t + \tfrac{1}{t}$. We obtain the $\mathbb{F}_{p^2}$ equality chain \[\left(t + \frac{1}{t}\right)^3 - 3\left(t + \frac{1}{t}\right) + 1 = 0 \implies t^3 + \frac{1}{t^3} + 1 = 0 \implies t^9 = 1.\]Thus the (multiplicative) order of $t$ divides 9, so it is one of 1, 3, or 9. If it is one of 1 or 3, then $t^3 = 1$, meaning $t^3 + \tfrac{1}{t^3} + 1 = 3 = 0$, so $p = 3$. Otherwise, the order of $t$ is 9. However, $t$ belongs to $\left(\mathbb{F}_{p^2}\right)^{\times}$, a group with $p^2 - 1$ elements. (It is also cyclic, but we don't need that.) Then by Lagrange, $9 \mid p^2 - 1$, so $p \equiv \pm 1 \pmod{9}$. (If we know that the group is cyclic, we can directly deduce $9 \mid p^2 - 1$.) To conclude, either $p = 3$ or $p \equiv \pm 1 \pmod{9}$. I find it ridiculous this problem was given in an actual high school olympiad, because (1) this $t + \tfrac{1}{t}$ trick has become quite standard [one easy application is to determine $\left(\tfrac{2}{p}\right)$], and (2) we essentially need to deal with the field of $p^2$ elements, a concept not normally included in the olympiad canon.

artofproblemsolving.com/community/c6h1412003p7937406

Let $t$ be a root of $x^2 - ax + 1$. If $x^2 - ax + 1$ splits in $\mathbb{F}_p[x]$, then $t \in \mathbb{F}_p$; otherwise $t \in \mathbb{F}_{p^2}$. Either way, $t \in \mathbb{F}_{p^2}$. How can you get this?

There is a more elementary approach to it?

An equivalent elaim: If $a,b$ are co-prime integers, and $p\ne3$ is a prime divisor of $a^3-3ab^2+b^3$ then $p\equiv\pm1\pmod9$. For the sake of contradiction, suppose that there is a prime $p$ and two integers $a,b$ such that $p|a^3-3ab^2+b^3$, $p\ne3$, $p$ is not a common divisor of $a,b$ but $p\not\equiv\pm1\pmod9$. Take the smallest such $p$. Obviously $p\ne2$, so $p\ge5$. Using Thue's lemma, we can replace $a$ and $b$ by smaller numbers: we show that there are some integers $c,d$, not both zero, such that $|c|,|d|<\sqrt{p}$ and $p|c^3-3cd^2+d^3$. Next, we divide $c$ and $d$ by their greatest common divisor. Let $g=gcd(c,d)$, $e=c/g$ and $d/g$. notice that $c^3-3cd^2+d^3\ne0$ and $g^3\le|c^3-3cd^2+d^3|<4p^{3/2}<p^3$, so $g$ is not divisible by $p$. Then the have $p|e^3-3ef^2+f^3$. Considering $e$ and $f$ modulo $3$ and $9$, we can see that $e^3-3ef^2+f^3\equiv\pm1\pmod{9}$ or $e^3-3ef^2+f^3\equiv\pm3\pmod{27}$. Hence there is another prime divisor $q\ne3$ of $\frac{e^3-3ef^2+f^3}{p}$ with $q\not\equiv\pm1\pmod9$. It is easy to prove that $|e^3-3ef^2+f^3|<3p^{3/2}$. Then $$ q \le \frac{|e^3-3ef^2+f^3|}{p} < \frac{3^{3/2}}{p} = 3\sqrt{p}. $$If $p<9$ then $q<p$, contradiction. The primes $p=2,5,7$ must be checked manually.

CantonMathGuy wrote: You've got to be kidding me. Let $t$ be a root of $x^2 - ax + 1$. If $x^2 - ax + 1$ splits in $\mathbb{F}_p[x]$, then $t \in \mathbb{F}_p$; otherwise $t \in \mathbb{F}_{p^2}$. Either way, $t \in \mathbb{F}_{p^2}$. It still not clear for me. For example, consider $x^2 - 4x + 1$, it has no root either in $\mathbb{F}_{5}$ or $\mathbb{F}_{25}$, otherwise $\phi(25) = 6k$ which is obviously false. Then, there is no $t$ such that $t +\frac{1}{t}= 4$ $(mod\; 25 )$. Can you (or anyone else who understood) explain better this part?

Lyte188 wrote: CantonMathGuy wrote: You've got to be kidding me. Let $t$ be a root of $x^2 - ax + 1$. If $x^2 - ax + 1$ splits in $\mathbb{F}_p[x]$, then $t \in \mathbb{F}_p$; otherwise $t \in \mathbb{F}_{p^2}$. Either way, $t \in \mathbb{F}_{p^2}$. It still not clear for me. For example, consider $x^2 - 4x + 1$, it has no root either in $\mathbb{F}_{5}$ or $\mathbb{F}_{25}$, otherwise $\phi(25) = 6k$ which is obviously false. Then, there is no $t$ such that $t +\frac{1}{t}= 4$ $(mod\; 25 )$. Can you (or anyone else who understood) explain better this part? He works in the field $x+y\sqrt{t}$ modulo $p$.

The field $\mathbb F_{25}$ does not represent the "field" of integers modulo $25$ (which can't be a field!); instead, it is the unique (up to isomorphism) degree-two extension of $\mathbb F_5$. More specifically, since $x^2 - 4x + 1$ has no root in $\mathbb F_5$, this polynomial is irreducible, and so the quotient $\tfrac{\mathbb F_5[x]}{(x^2 - 4x + 1)}$ is a field. We can describe this field symbolically as follows: if $\alpha$ (formally!) satisfies $\alpha^2 - 4\alpha + 1=0$, then the elements of this field are the $25$ elements of the form $a\alpha + b$, where $a,b\in\{0,1,2,3,4\}$. It turns out that there is only one finite field of $25$ elements up to isomorphism; we denote this field by $\mathbb F_{25}$. This construction generalizes to finite fields of arbitrary prime power. (EDIT: sniped, oh well)

Thank you @djmathman and @rcorrea, your comments gave me a good direction for starting to study abstract algebra and what so ever.

Solution from Twitch Solves ISL: Write $a = x + \frac 1x$ for some $x \in {\mathbb F}_{p^2}$. Claim: The element $x$ has order $9$. Proof. Because \begin{align*} 0 &= \left( x + \frac 1x \right)^3 - 3 \left( x + \frac 1x \right) + 1 \\ &= x^3 + x^{-3} + 1 = \frac{x^6+x^3+1}{x^3}. \end{align*}This implies $x^9=1$, so $x$ has order dividing $9$. However, $x^3 \neq 1$ since $p > 3$. Therefore, $x$ has order exactly $9$. $\blacksquare$ Thus $9 \mid p^2-1$ so we're done.

v_Enhance wrote: Solution from Twitch Solves ISL: Write $a = x + \frac 1x$ for some $x \in {\mathbb F}_{p^2}$. Claim: The element $x$ has order $9$. Proof. Because \begin{align*} 0 &= \left( x + \frac 1x \right)^3 - 3 \left( x + \frac 1x \right) + 1 \\ &= x^3 + x^{-3} + 1 = \frac{x^6+x^3+1}{x^3}. \end{align*}This implies $x^9=1$, so $x$ has order dividing $9$. However, $x^3 \neq 1$ since $p > 3$. Therefore, $x$ has order exactly $9$. $\blacksquare$ Thus $9 \mid p^2-1$ so we're done. Can you just tell me where can I get material about the notations and theorems that you used in this solution? I don't really understand what are you intentions. Seems that I just have flashes of understanding what you saying. Thanks for reading!

v_Enhance wrote: Write $a = x + \frac 1x$ for some $x \in {\mathbb F}_{p^2}$. . Why are we allowed to do that ? I thought that we could only work with integers in such fields, or am I wrong somewhere?

@above it is because the equation $x + \frac{1}{x} = a \iff x^2-ax+1 = 0$ is a quadratic equation, and every quadratic with coefficients in $\mathbb{F}_p$ has roots in $\mathbb{F}_{p^2}$

Could you proof that Statement please, would be really Kind.

$\mathbb{F}_{p^2}$ is defined as follows: Take $\alpha$ to be a root of an irreducible quadratic (say $x^2 + qx + r$) in $\mathbb{F}_p[x]$. Then $\mathbb{F}_{p^2}$ is the set $$\{ a+b\alpha \, \mid \, a, b, \in \mathbb{F}_p\}$$ Clearly, in this definition it makes no difference if we replace $\alpha$ with $\alpha - \frac{q}{2}$, which means that we can assume $\alpha$ is the root of $x^2 + r$ for some $r$, i.e. $\alpha^2 = s$ for some quadratic non-residue $s$ mod $p$. Then we can just use the quadratic formula. Take any quadratic $x^2 + bx+c$ in $\mathbb{F}_p[x]$. If its discriminant $b^2-4c$ is a quadratic residue mod $p$, then the quadratic formula gives us two roots in $\mathbb{F}_p$. Otherwise, $\frac{b^2-4c}{s}$ is a quadratic residue mod $p$, say $e^2 \equiv \frac{b^2-4c}{s}$. Then notice that $$\frac{-b \pm \alpha e}{2}$$ are the roots of the quadratic, and lie in $\mathbb{F}_{p^2}$. Note this proof won't work if $p=2$ since we divide by $2$ a couple of times, but we can just check it manually then.

v_Enhance wrote: Solution from Twitch Solves ISL: Write $a = x + \frac 1x$ for some $x \in {\mathbb F}_{p^2}$. Claim: The element $x$ has order $9$. Proof. Because \begin{align*} 0 &= \left( x + \frac 1x \right)^3 - 3 \left( x + \frac 1x \right) + 1 \\ &= x^3 + x^{-3} + 1 = \frac{x^6+x^3+1}{x^3}. \end{align*}This implies $x^9=1$, so $x$ has order dividing $9$. However, $x^3 \neq 1$ since $p > 3$. Therefore, $x$ has order exactly $9$. $\blacksquare$ Thus $9 \mid p^2-1$ so we're done. Or just why can you follow that $9 \mid p^2-1$?

pls help, I need it for school tomorow

Lukas8r20 wrote: pls help, I need it for school tomorow I don't really understand what you are asking, but the step that he concludes the divisibility relation follows since Lagrange's theorem on Group Theory. I mean, order of $x$ is $9$ (related to the field in question) implies in $9$ divides the order of the field. Is that what you want?

Old question.

First, I claim that there exists a solution $x \in \mathbb{F}_{p^2}$ to $x+\tfrac{1}{x}=a \iff x^2-ax+1=0$. By the quadratic formula, if $a^2-4$ is a QR then in fact $x \in \mathbb{F}_p$, otherwise $a^2-4$ is an NQR and we still have $x \in \mathbb{F}_{p^2}$. Thus we may substitute $a=x+\tfrac{1}{x}$, whence $$0=a^3-3a+1=x^3+1+\frac{1}{x^3} \implies x^6+x^3+1=0,$$where all equalities are in $\mathbb{F}_{p^2}$. This implies that the order of $x$ in $\mathbb{F}_{p^2}$ is $9$, since $p \neq 3$. This then implies $9 \mid p^2-1$, so we're done. $\blacksquare$

Set $a = x + \frac 1x$, so that the equation becomes $$x^6+x^3+1 \equiv 0 \pmod p.$$This requires the order of $x$ mod $p$ to be precisely equal to $9$. On the other hand, $x = \frac{a \pm \sqrt{a^2-4}}2$ is an element of $\mathbb F_{p^2}$, so $9 \mid p^2-1$ and we have the result.

We show the stronger condition that $x^3 - 3x + 1$ has one root in $\mathbb F_p$ if $p = 3$, three roots in $\mathbb F_p$ if $p \equiv \pm 1 \pmod{18}$, and no roots in $\mathbb F_p$ otherwise. When $p = 3$, the only root is $x = 2$, from now on, assume $p \neq 3$. Throughout, let $\omega$ be a root of $\Phi_{18}$ and $\sigma$ be the Frobenius automorphism sending $x$ to $x^p$. Solving the cubic shows $x^3 - 3x + 1$ has roots $-(\omega + \omega^{-1})$, $-(\omega^5 + \omega^{-5})$, and $-(\omega^7 + \omega^{-7})$. Since $\operatorname{Gal}(\mathbb F_p(\omega)/\mathbb F_p) = \{\operatorname{id},\sigma,\dots,\sigma^{\operatorname{ord}_{18}(p)}\}$, the degree of the field extension $\mathbb F_p(\omega)/\mathbb F_p$ is $1$ if $p \equiv 1 \pmod{18}$, $2$ if $p \equiv -1 \pmod{18}$, and $3$ or $6$ otherwise. We show $\omega + \omega^{-1} \not\in \mathbb F_p$ if $p \not\equiv \pm 1 \pmod{18}$, which is enough since $\mathbb F_p(\omega)$ is Galois. We have \[3 \ge [\mathbb F_p(\omega) : \mathbb F_p] = [\mathbb F_p(\omega) : \mathbb F_p(\omega + \omega^{-1})][\mathbb F_p(\omega + \omega^{-1}) : \mathbb F_p] \ge 2[\mathbb F_p(\omega + \omega^{-1}) : \mathbb F_p],\]so $\mathbb F_p(\omega + \omega^{-1})/\mathbb F_p$ is nontrivial and $\omega + \omega^{-1} \not\in \mathbb F_p$. We show $\omega + \omega^{-1} \in \mathbb F_p$ if $p \equiv \pm 1 \pmod{18}$, which is enough since $\mathbb F_p(\omega)/\mathbb F_p$ is Galois. If $p \equiv 1 \pmod{18}$, $\omega \in \mathbb F_p$ and we are done. If $p \equiv -1 \pmod{18}$, the minimal polynomial of $\omega$ is \[(x - \omega)(x - \sigma(\omega)) = x^2 - (\omega + \omega^p)x + \omega^{p + 1} = x^2 - (\omega + \omega^{-1})x + 1.\]But the minimal polynomial has coefficients in $\mathbb F_p$, so $\omega + \omega^{-1}$ is in $\mathbb F_p$.

relevant: IMC 2020 P6

Set $a=t+\tfrac1t$ for $t$ in $\Bbb F_{p^2}$ so $t^3+1+\tfrac1{t^3}=0$ or $t^6+t^3+1=0$. If $t$ is a root of $x^3-1$ and $x^6+x^3+1$ then $x$ is a root of $3$ so $p=3$. Otherwise $t$ has order $9$, so since $t^{p^2-1}=1$ we have $9\mid p^2-1$ or $p\equiv\pm1\pmod9$.

OronSH wrote: Set $a=t+\tfrac1t$ for $t$ in $\Bbb F_{p^2}$ so $t^3+1+\tfrac1{t^3}=0$ or $t^6+t^3+1=0$. If $t$ is a root of $x^3-1$ and $x^6+x^3+1$ then $x$ is a root of $3$ so $p=3$. Otherwise $t$ has order $9$, so since $t^{p^2-1}=1$ we have $9\mid p^2-1$ or $p\equiv\pm1\pmod9$. very nice!