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