# For distinct primes $p,q$ show $\exists$ a primitive root $b$ of $q$ such that $\gcd(b,p)= 1$

I have two distinct primes $p$ and $q$ with $p<q$.

Let $b$ be a primitive root of $q$ so $b^{\frac{q-1}{t}} \not\equiv 1$ (mod q) for all $t$ a prime factor of $q-1$.

I need to prove $\exists$ a primitive root $b$ of $q$ such that $\gcd(b,p)= 1$

Now I know that as $p$ is prime, $\gcd(b,p)$ can only be $1$ or $p$, and it is only $p$ if $b = a p$ for some $a \in \mathbb{Z}$. But how do I prove this won't be the case, so the $gcd$ is 1.

Let $b$ be a primitive root of unity mod $q$. Consider $b \equiv b+q \mod q$.
• Suppose $\gcd(b, p) \neq 1$, i.e., $p$ divides $b$. What can you say about whether $p$ divides $b+q$? – Dustan Levenstein Nov 28 '13 at 13:03
• $p \nmid (b+q)$ as $p \nmid q$ as $p<q$ where $p,q$ are distinct primes. so does that mean I can take any primitive root $b$ of $q$ and it's $\gcd(b,p)$ = 1? – jakey Nov 28 '13 at 13:09
• No, that means you take either $b$ or $b+q$, depending on whether $p \mid b$ or not. I'm assuming you don't need a reduced representative modulo $q$, since your problem doesn't specify; otherwise my solution doesn't work. – Dustan Levenstein Nov 28 '13 at 13:12