Competition problem — Number theory

Library / /239 of 520

Number theory Difficulty 6.0 National olympiad Prove it

Corollary 8.2. Let $r$ be a primitive root modulo $m$ where $m$ is an integer, $m>1$ . Then $r^{u}$ is a primitive root modulo $m$ if and only if $(u, \phi(m))=1$ .

Solution

Proof. From Theorem 8.4 , we know that
$\begin{aligned} \operatorname{ord}_{m} r^{u} & =\operatorname{ord}_{m} r /\left(u, \operatorname{ord}_{m} r\right) \\ & =\phi(m) /(u, \phi(m)) \end{aligned}$

Consequently, $\operatorname{ord}_{m} r^{u}=\phi(m)$ , and $r^{u}$ is a primitive root modulo $m$ , if and only if $(u, \phi(m))=1$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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