37th Iranian Mathematical Olympiad

Assume for a contradiction that ${\text{ord}}_m(a)$ has at least two prime factors. Then we can write ${\text{ord}}_m(a)=rs$ where $\gcd (r,s)=1$ and $r$, $s$ are both greater than $1$. Now take a natural solution pair $(k,\ell )$ of the equation $ks+r\ell \equiv 1(\mathrm{mod}\phi (m))$, that definitely exists by Bézout's theorem, and consider $(x,y)=(-a^{ks},-a^{r\ell })$. We claim this choice of $(x,y)$ will contradict the condition of problem. First of all: $$xy\equiv a^{ks+r\ell }\equiv a(\mathrm{mod}m).$$ Where the last equality follows from Euler's Theorem. Now we have to prove a lemma: Lemma. Let $z$, $t$ be natural numbers such that ${\text{ord}}_z(t)$ is odd. Then we have ${\text{ord}}_z(-t)=2{\text{ord}}_z(t)$. Proof. Let ${\text{ord}}_z(t)=w$ then $(-t{)}^w\equiv -1(\mathrm{mod}z)$ and $(-t{)}^{2w}\equiv 1(\mathrm{mod}z)$. So ${\text{ord}}_z(-t)=2q$ is even. Therefore if $q<w$ we have $t^{2q}\equiv 1(\mathrm{mod}z)$ which gives $w\mid 2q$ and since $w$ is odd we have $w\mid q$ which is clearly a contradiction. Using the lemma, it is easy to see that ${\text{ord}}_m(x)=2r$ and ${\text{ord}}_m(y)=2s$ which is clearly a contradiction hence ${\text{ord}}_m(a)$ has at most one prime factor.