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}$?

  • 1
    $\begingroup$ $(c+q)^n\equiv c^n\pmod{q}$. $\endgroup$ – Alamos May 2 '15 at 19:13
  • $\begingroup$ Prior comment is a special case of the Congruence Power Rule $\ d\equiv c\,\Rightarrow d^n\equiv c^n\ \ $ $\endgroup$ – Bill Dubuque May 2 '15 at 20:03

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


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.