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

Question

Let p and q be primes with q>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^ϕ(q)≡1(mod q). Since p is a prime too, there must exist a primitive root mod p as well. Let's call it y. hence y^ϕ(p)≡1(mod 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.

Answer 1

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