2
$\begingroup$

Let $a$ be a primitive root modulo $mn$. Show that $a$ is also primitive root modulo $m$ and $n$.
Showing $(a,mn)=1\Longrightarrow (a,m)=(a,n)=1$ is not a problem. The problem is showing $a^{\varphi (m)} \equiv 1\pmod{m}$ where $\varphi (m)$ is the least natural number for which the congruence holds.
Initial thought:
Let $A :=\{x|a^x\equiv 1\pmod{m}\}\subset\mathbb{N}$, obviously $A\neq\emptyset$ so it contains the smallest element $r$. Must show that $r=\varphi (m)$. Supposing for a contradiction that $r<\varphi (m)$ I would need it somehow to contradict the fact that $$a^{\varphi (mn)}\equiv 1\pmod{mn} $$ where $\varphi (mn)$ is the least for which said congruence holds.

How should one go about finding a contradiction?

$\endgroup$
2
$\begingroup$

First, assume that it is not a primitive root $\pmod m$. Then we have that there exists such $r < \phi (m)$ $$a^r \equiv 1 \pmod m$$

Now use that $$\phi (mn) = \phi (m)\phi (n) \frac{ d}{\phi (d)} \ge \phi(m) \phi (n)> r \phi (n)$$

From here.

$\endgroup$
0
$\begingroup$

Because a primitive root modulo $mn$ exists, it is necessary and sufficient that $mn\in\{2,4,p^k,2p^k\}, p>2, k\in\mathbb{N}$. The interesting cases are $mn\in\{p^k,2p^k\}$.

  1. Let $mn=p^k$ and $x$ a primitive root modulo $p^k$. It follows that $x$ is a primitive root modulo $p$. Then, modulo $p^2$, at least one of $x$, $x+p$ is a primitive root. It turns out $x$ is a primitive root modulo $p^2$, for otherwise $x$ is not a primitive root modulo $p$ and therefore not a primitive root modulo $p^k$.
    Provided $x$ is a primitive root modulo $p^2$, it's also a primitive root modulo $p^r,r>2$.

  2. Let $mn=2p^k$. The only interesting case is $(m,n)>1$ that is $m=2p^s$ and $n=p^t$ such that $s+t=k$. The assertation holds for $n$ and consequently for $m$, otherwise we would have $r<\varphi (2p^s) =\varphi (p^s)$: $$x^r\equiv 1\pmod{2p^s}\Longrightarrow x^r\equiv 1\pmod{p^r} $$ which then, in turn, implies $x$ is not a primitive root modulo $p^k$ and consequently not a primitive root modulo $2p^k=mn$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.