Competition problem — Number theory

Library / /273 of 520

Number theory Difficulty 6.1 National olympiad Prove it

6. Let $m \geqslant 1, n \geqslant 1$ and $(n, \varphi(m))=1$ . Prove: When $x$ runs through the reduced residue system modulo $m$ , $x^{n}$ also runs through the reduced residue system modulo $m$ .

Solution

6. If $\left(x_{1} x_{2}, m\right)=1, x_{1}^{n} \equiv x_{2}^{n}(\bmod m),\left(x_{1} x_{2}^{-1}\right)^{n} \equiv 1(\bmod m)$ . Let the order of $x_{1} x_{2}^{-1}$ modulo $m$ be $\delta$ , then $\delta \mid(n, \varphi(m))$ , so $\delta=1$ , i.e., $x_{1} \equiv x_{2}(\bmod m)$ .

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.