Track / Stage 6 / 160 of 400 #1160 of 1964

Problem 1160

National Olympiad, first round

Number theory Difficulty 6.2 Prove it

Let $p$ be a prime, $\delta_{p}(a)=h$ . Prove:
(i) If $2 \mid h$ , then $a^{h / 2} \equiv -1 \pmod{p}$ ;
(ii) If $4 \mid h$ , then $\delta_{p}(-a)=h$ ;
(iii) If $2 \mid h, 4 \nmid h$ , then $\delta_{p}(-a)=h / 2$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

10. (i) From $p \nmid a^{h / 2}-1, p \mid a^{h}-1=\left(a^{h / 2}-1\right)\left(a^{h / 2}+1\right)$ , we get the result.
(ii) From (i), we have $(-a)^{h / 2} \equiv a^{h / 2} \equiv-1(\bmod p)$ . Let $h^{\prime}=\delta_{p}(-a)$ . We have $h / 2=$ $\delta_{p}\left(a^{2}\right)=\delta_{p}\left((-a)^{2}\right)=h^{\prime} /\left(h^{\prime}, 2\right)$ . From this and $h^{\prime} \neq h / 2$ , we get $h^{\prime}=h$ .
(iii) In this case, $(-a)^{h / 2} \equiv-a^{h / 2} \equiv 1(\bmod p)$ . From this and the argument in (ii), we get $h^{\prime}=h / 2$ .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.