Track / Stage 6 / 123 of 400 #1123 of 1964

Problem 1123

National olympiad, first round

Number theory Difficulty 6.2 Prove it

6. Let $p>2$ be a prime, and the standard prime factorization of $p-1$ is $q_{1}^{\beta_{1}} \cdots q_{r}^{\beta}$ . Prove:
(i) For any $j(1 \leqslant j \leqslant r)$ , there exists $a_{j}$ whose order modulo $p$ is $q_{j}^{\beta_{j}}$ (do not use the existence of a primitive root modulo $p$ ); $\square$
(ii) $a_{1} \cdots a_{r}$ is a primitive root modulo $p$ ;
(iii) Provide an example to illustrate how to use this method to construct a primitive root modulo 23.

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

6. (i) Let the different exponents that $1,2, \cdots, p-1$ can take be $\delta_{1}, \cdots, \delta_{s}$ . We have $\tau=$ $\left[\delta_{1}, \cdots \delta_{s}\right] \mid p-1$ , and let the prime factorization of $\tau$ be $p_{1}^{q_{1}} \cdots p_{t^{t}}^{q_{1}}$ . There must be $a_{j}$ such that the exponent of $a_{j}$ modulo $p$ is $p_{j}^{q_{j}}$ $(1 \leqslant j \leqslant t)$ . Proving $\tau=p-1$ would establish (i). This can be deduced from the fact that the number of solutions to $x^{\tau}-1 \equiv 0(\bmod p)$ is $p-1$ .
(ii) (i) and Property V of $\S 1$ imply (ii).
(iii) The exponent of 2 is 11, and the exponent of -1 is 2, so -2 is a primitive root modulo 23.

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