Existence of primitive root satisfying a certain condition

Question

Let $l$ and $p$ be prime numbers such that $p|l-1$. Suppose there is an integer $r \in \mathbb Z$ such that $r^p \equiv 1 $ mod $l$. Can anyone please help me see why there exists a generator $s$ of $(\mathbb Z/ l \mathbb Z)^{\times}$ such that $r \equiv s^{ \frac{l-1}{p} } $ mod $l$? My attempt is as follows: pick any generator $t$ of $(\mathbb Z/ l \mathbb Z)^{\times}$. Then $t^x=r$ for some $0 < x \leq l-1$ and so $t^{px} \equiv r^p \equiv 1$ mod $l$. Hence, $l-1$ divides $px$ but I am not sure how to proceed.

Answer 1

You have the right idea about how to approach the proof. First, though, for better visual differentiation of $l$ as opposed to $1$, I'm replacing $l$ with $q$. Next, a small but required implicit detail is that $r \not\equiv 1 \pmod{q}$ since that also works with

$$r^p \equiv 1 \pmod{q} \tag{1}\label{eq1A}$$

However, there is no generator $s$ where

$$r \equiv s^{\frac{q-1}{p}} \pmod{q} \tag{2}\label{eq2A}$$

since the smallest positive power $i$ where $1 \equiv s^{i} \pmod{q}$ is $i = q - 1$. Next, here is a useful lemma:

---

Lemma $1$: For any generator $t$ of $(\mathbb Z/ q \mathbb Z)^{\times}$ and integer $j$ where $\gcd(j, q - 1) = 1$, then $u \equiv t^j \pmod{q}$ is also a generator.

Proof: Let $k_1$ and $k_2$ be two different integers where

$$u^{k_1} \equiv u^{k_2} \pmod{q} \implies u^{k_1 - k_2} \equiv 1 \pmod{q} \implies t^{j(k_1 - k_2)} \equiv 1 \pmod{q} \tag{3}\label{eq3A}$$

Since $t$ is a generator, this means

$$j(k_1 - k_2) \equiv 0 \pmod{q - 1} \implies q - 1 \mid j(k_1 - k_2) \tag{4}\label{eq4A}$$

With $\gcd(j, q - 1) = 1$, this means $q - 1 \mid k_1 - k_2$. Thus, the congruences of the powers of $u$ repeat every $q - 1$ values, so the powers of $u^z$ for $0 \le z \lt q - 1$ are the $q - 1$ non-zero modulus values, which means $u$ must generate each one uniquely and, thus, is also a generator.

---

As you started, pick any generator $t$ of $(\mathbb Z/ q \mathbb Z)^{\times}$. Then for some integer $0 \lt x \lt q - 1$ (note: the second inequality should be $\lt$ rather than $\leq$), we get

$$t^x \equiv r \pmod{q}, \; 0 \lt x \lt q - 1 \tag{5}\label{eq5A}$$

so this means

$$t^{px} \equiv r^p \equiv 1 \pmod{q} \tag{6}\label{eq6A}$$

This gives, for some positive integer $m$,

$$px \equiv 0 \pmod{q - 1} \implies px = m(q - 1) \implies x = m\left(\frac{q - 1}{p}\right) \tag{7}\label{eq7A}$$

If $m = 1$, then let $s = t$ and we're done. Otherwise, since $x \lt q - 1$, then $px \lt p(q - 1)$, so $m \lt p$, which gives $2 \le m \le p - 1$. This means $m$ has a multiplicative inverse modulo $p$, call it $n$. Next, for an integer $v$, have

$$u = vp + n \tag{8}\label{eq8A}$$

Let $\gcd(n, q - 1) = d$. If $d = 1$, then set $v = 0$. Otherwise, let $p_i$ for $1 \le i \le a$ for some integer $a \gt 0$ be the set of distinct primes which divide $d$. Then, using the $p$-adic order function, set

$$v = \frac{q - 1}{p^{\nu_p(q - 1)}\left(\prod_{i=1}^{a}p_i^{{\nu_{p_i}(q - 1)}}\right)} \tag{9}\label{eq9A}$$

Note $1 \le u \lt q - 1$. Also, $\gcd(u, q - 1) = 1$ in all cases, since with $v = 0$ it's because $\gcd(n, q - 1) = 1$, while for $v \gt 0$, it's because $p \mid vp$ but $p \not\mid n$, all prime factors of $d$ divide $n$ but not $vp$, and all other prime factors (if any) of $q - 1$ divide $vp$ but not $n$.

From the right side of \eqref{eq7A}, multiply both sides by $u$, and use there exists an integer $b$ where $mn = bp + 1$ since $n$ is the multiplicative inverse of $p$, giving

$$\begin{equation}\begin{aligned} ux & \equiv um\left(\frac{q - 1}{p}\right) \pmod{q - 1} \\ & \equiv (vp + n)m\left(\frac{q - 1}{p}\right) \pmod{q - 1} \\ & \equiv vm(q - 1) + nm\left(\frac{q - 1}{p}\right) \pmod{q - 1} \\ & \equiv (bp + 1)\left(\frac{q - 1}{p}\right) \pmod{q - 1} \\ & \equiv b(q - 1) + \frac{q - 1}{p} \pmod{q - 1} \\ & \equiv \frac{q - 1}{p} \pmod{q - 1} \end{aligned}\end{equation}\tag{10}\label{eq10A}$$

Since $\gcd(u, q - 1)$, there's a multiplicative inverse $y$ of $u$ modulo $q - 1$. Since $\gcd(y, q - 1) = 1$, using Lemma $1$, this means there's a generator $s$ defined by

$$s \equiv t^{y} \pmod{q} \implies s^{u} \equiv t^{yu} \equiv t \pmod{q} \tag{11}\label{eq11A}$$

Using this in \eqref{eq5A}, and using \eqref{eq10A}, gives

$$r \equiv (s^{u})^{x} \equiv s^{ux} \equiv s^{\frac{q - 1}{p}} \pmod{q} \tag{12}\label{eq12A}$$