Track / Stage 7 / 165 of 300 #1565 of 2000

Problem 1565

National olympiad second round; IMO P1/P4

Number theory Difficulty 7.3 Prove it

Theorem 1 Let $m \notin\{1,2,4\}$ , and there does not exist an odd prime $p$ and $\alpha \in \mathbf{N}^{*}$ , such that $m \in$ $\left\{p^{a}, 2 p^{a}\right\}$ . Then for any $a \in \mathbf{Z},(a, m)=1$ , we have $\delta_{m}(a)<\varphi(m)$ , in this case the primitive root modulo $m$ does not exist.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Prove that if $m=2^{\alpha}, \alpha \in \mathbf{N}^{*}, \alpha \geqslant 3$ , then for any odd number $a$ , set $a=2 k+1$ , then
$\begin{aligned} a^{2^{a-2}} & =(2 k+1)^{2^{a^{-2}}} \equiv 1+2^{a-2} \cdot(2 k)+\mathrm{C}_{2^{a-2}}^{2}(2 k)^{2} \\ & =1+2^{a-1} \cdot k+2^{a-1} \cdot\left(2^{a-2}-1\right) k^{2} \\ & =1+2^{a-1}\left(k+\left(2^{a-2}-1\right) k^{2}\right) \\ & \equiv 1\left(\bmod 2^{a}\right) \end{aligned}$

The last step uses the fact that $k$ and $\left(2^{a^{-2}}-1\right) k^{2}$ have the same parity, thus their sum is even. At this point, the proposition holds. $\square$

If $m$ is not a power of 2, and $m$ is a positive integer that meets the conditions, then we can set $m=r t$ , here $22$ when, $\varphi(n)$ is even, so
$a^{\frac{1}{2} \varphi(r) \varphi(t)} \equiv 1(\bmod r t)$

Thus,
$\delta_{m}(a) \leqslant \frac{1}{2} \varphi(r) \varphi(t)=\frac{1}{2} \varphi(r t)=\frac{1}{2} \varphi(m)<\varphi(m)$

The proposition is proved.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.