# Why is $c+q$ still a primitive root modulo $q$?

Question: Let $p$ and $q$ be distinct odd prime numbers.

By considering primitive roots, we need to show $\exists c\in\mathbb{Z}$ with the property that:

$\bullet$ $c^n\equiv 1\pmod{p}$ whenever $n$ is a multiple of $p-1$, and

$\bullet$ whenever $n$ is not divisible by $q-1$, then $c^n\not\equiv 1\pmod{q}$

I am only interested with the beginning of this answer.

Answer: We let $c$ be a primitive root modulo $q$.

We are going to use Fermat's little theorem so we need $(c,p)=1$

If $(c,p)\neq 1$, then we have $p\mid c$, but then we have $(c+q, p)=1$

and since $c+q$ is a primitive root modulo $q$, we can replace $c$ with $c+q$ for $(c,p)=1$ for using Fermat's little theorem.

I understand the general method and argument, but...

Contention: Why is $c+q$ still a primitive root modulo $q$?

When is this generally true? Is there an identity for when things remain a primitive root?

Why is $(c+q)^{\phi(q)}\equiv 1\pmod{q}$?

• $(c+q)^n\equiv c^n\pmod{q}$. Commented May 2, 2015 at 19:13
• Prior comment is a special case of the Congruence Power Rule $\ d\equiv c\,\Rightarrow d^n\equiv c^n\ \$ Commented May 2, 2015 at 20:03
• Key Idea: all of the (modular) definitions of "$c$ is a primitive root $\!\bmod{\!q}$" are statements concerning powers $\, c^n\pmod{\! q}.\,$ Replacing $\,c\,$ by $\,c_1 \equiv c\pmod{\!q}\,$ doesn't alter the truth of such statements since $\,c_1\equiv c\Rightarrow\ c_1^n\equiv c^n\pmod{\!q}\,$ by the Congruence Power Rule. In particular this is true for your $\, c_1 = c + q\ \$ Commented Nov 1, 2020 at 1:08

Being a primitive root modulo $q$ is a condition "modulo $q$." And, $c$ and $c+ q$ are congruent modulo $q$.
In other words, being a primitive root depends on the residue class modulo $q$, and $\overline{c}= \overline{c+q}$.
If you want to be explicit you can note $(c+ q)^n = c^n + \sum_{i=1}^n q^i c^{n-i}\binom{n}{i}$, and $\sum_{i=1}^n q^i c^{n-i}\binom{n}{i}$ is divisible by $q$.