# primitive roots of primes exercise ( is related to Sophie German theorem)

Let p and q be primes with $q\gt p$ such that p is not a factor of q-1. As q is a prime, we know that for any integer x we can write $x^{q-1}$ in the form $x^{q-1} = kq+1$ for some integer k. Furthermore, since the greatest common divisor of p and (q-1) is 1, we can write

1 = ap + b(q-1)

for some integers a and b.

(a) Show that every integer x can be written in the form $x = y^p + jq$ for some integer y and some integer j.

My approach : since I know that $x^{q-1} = kq+1$ then x is a primitive root mod q ie $x^{\varphi(q)} \equiv 1 \pmod q$.

Since p is a prime too, there must exist a primitive root mod p as well. Let's call it y. hence $y^{\varphi(p)}\equiv 1 \pmod p$.

So from the previous equations i can get $y^{p-1}=hp+1, x^{q-1}=kq+1$ and I have given 1=ap+b(q-1). I thought about putting this into a system but didn't help.

-

So we want to prove that the integer $x$ is congruent to a $p$-th power modulo $q$. This is obvious if $x\equiv 0\pmod{q}$. So we can assume that $x\not\equiv 0\pmod{q}$.

Consider the numbers $1^p, 2^p, 3^p, \dots, (q-1)^p$. If we can show these are all incongruent modulo $q$, it will follow that these numbers travel through all the non-zero residue classes modulo $q$. In particular, it means that one of them is congruent to $x$ modulo $q$.

Suppose that $a^p \equiv b^p\pmod{q}$. If $c$ is the inverse of $b$ modulo $q$, then $(ac)^p\equiv 1\pmod{q}$.

So the order of $ac$ divides $p$. The order cannot be $p$, since $p$ does not divide $q-1$. Thus $ac$ has order $1$, and therefore $ac\equiv 1\pmod{q}$. This implies that $a\equiv b\pmod{q}$. It follows that $1^p,2^p,\dots,(q-1)^p$ are distinct modulo $q$.

Remark: We gave a very basic proof of the result. If we want to use a proof that uses a primitive root, again note that $x\equiv 0\pmod{q}$ is trivial.

Suppose $x\not\equiv 0\pmod{q}$. Let $g$ be a primitive root modulo $q$. Then for some $k$, we have $x\equiv g^k\pmod q$.

We show that $g$ is congruent to a $p$-th power. That will imply that $g^k$ is also congruent to a $p$-th power.

Since $p$ and $q-1$ are relatively prime, there exist integers $s$ and $t$ such that $sp+t(q-1)=1$. Thus $$g=g^1=g^{sp+t(q-1)}=(g^s)^p(g^{q-1})^t\equiv (g^s)^p \pmod{q},$$ so indeed $g$ is a $p$-th power modulo $q$.

-