# 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}$. – Alamos May 2 '15 at 19:13
• Prior comment is a special case of the Congruence Power Rule $\ d\equiv c\,\Rightarrow d^n\equiv c^n\ \$ – Bill Dubuque May 2 '15 at 20:03

## 1 Answer

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$.