# Number of $k^p \bmod q$ classes when $q\%p > 1$

I want to show that when $p, q$ are primes, $k^p\bmod q$ takes on $q-1$ distinct values (as $k$ ranges over positive integers) if and only if $q \not\equiv 1 \pmod p$. (It is easy to verify this computationally for small primes, eg $p < 100$ and $q < 10000$.) More compactly, the claim is this: For any primes p, q, $|S(p,q)| = q-1$ iff $q \not\equiv 1 \pmod p$, where $S(p,q)=\{ K(p,q,a): a \in\mathbb{Z}^+\}$ and $K(p,q,a)$ is the equivalence class $a^p \bmod q$.

I can show the "only if" part easily (but crudely) [Update: and incorrectly, as noted in Jyrki Lahtonen's comment] for $q>4$ via Euler's theorem by noting that $4^j-1$ is never prime if $j>1$, so that $q \equiv 1 \pmod p \implies q>p \implies \exists k>1$ such that $\phi(q) = q-1 = k\cdot p$, hence (taking $x=4^k$) we have $\exists x\not\equiv 1$ such that $x^p=4^{k\cdot p}=4^{q-1}\equiv 1$, which ensures that $|S(p,q)| < q-1$.

For the "if" part I've been trying to apply Lagrange's theorem for a group with operation $\circ$ with $a\circ b \equiv a^p\cdot b^p\bmod q$ which is easy to show is closed and associative with identity and inverse, but have been going in circles on this part.

What is a better approach for proving the "only if" part? What's a better direction for the "if" part?

-
Why must it be true that $x=4^k$ is not congruent to 1 mod $q$? What about $q=7$, $k=3$, $p=2$? –  Jyrki Lahtonen Aug 13 '11 at 5:09
@Jyrki, I edited the question to take note of that error. Thanks! –  jwpat7 Aug 13 '11 at 5:59
The way to fix this is to replace $4$ with a suitable number. The reason why such numbers exist is described in André's thorough answer. –  Jyrki Lahtonen Aug 13 '11 at 6:00
Still not knowing the meaning of the title... –  awllower Aug 21 '11 at 8:31
@awllower, the "q%p>1" part of the title was used as shorthand for "q != 1 mod p". The "number of classes" part refers to the number of equivalence classes, mod q, of k^p. How would you phrase it? –  jwpat7 Aug 22 '11 at 21:44

First we give a number-theoretic proof for the direction you did not deal with. After that, we give a couple of proofs for the other direction. These are similar to the proof that you described, but fill the gap mentioned in the comment by @Jyrki Lahtonen.

As much as possible, your notation is used. The primality of $p$ is nowhere used, and is not needed. I do not think that assuming primality allows for any real simplification.

Suppose that $q \not \equiv 1 \pmod{p}$, and $a^p \equiv b^p \pmod{q}$. We will show that $a\equiv b \pmod{q}$. We can assume that neither $a$ nor $b$ is congruent to $0$ modulo $q$.

Since $q\not\equiv 1 \pmod{p}$, the numbers $q-1$ and $p$ are relatively prime. By Bezout's Theorem there exist integers $m$, $n$ such that $m(q-1)+np=1$. Thus $$a=a^1=a^{m(q-1)+np}=a^{(q-1)m}a^{pn}\qquad\qquad\text{(Equation 1)}$$ By Fermat's Theorem, $a^{(q-1)m} \equiv 1\pmod{q}$. From Equation $1$, we conclude that $$a\equiv (a^p)^n \pmod{q}.$$ Similarly, $$b \equiv (b^p)^n \pmod{q}.$$

It follows that if $a^p \equiv b^p \pmod{q}$ then $a \equiv b \pmod{q}$.

Note: The integers $m$ and $n$ are not both positive. As usual, we interpret a negative power as the inverse modulo $q$ of the corresponding positive power.

The other direction: Suppose that $q \equiv 1 \pmod{p}$. We show that there exist $a$, $b$ which are incongruent modulo $q$ such that $a^p \equiv b^p \pmod{q}$. As in your proof, let $pk=q-1$.

Let $b=1$. We show that there exists $a$ not congruent to $1$ modulo $q$ such that $a^p \equiv 1^p \pmod{q}$.

By Fermat's Theorem, the natural candidates for $a$ have shape $c^k$, with $c$ not congruent to $0$ modulo $q$. This is because $(c^k)^p =c^{kp}=c^{q-1}\equiv 1 \pmod{p}$.

So all we need to do is to show that there exists $c$ not congruent to $0$ such that $c^k$ is not congruent to $1$ modulo $q$.

(i): If we are allowed to use a little information about fields, this is immediate. For the equation $x^k=1$ has at most $k$ solutions in the integers modulo $q$. Since $k \le (q-1)/2$, there are indeed many $c$ with the desired property.

If we are not allowed to use that fact, we can prove it. The fact that in our field (or indeed any field) a polynomial of positive degree $k$ has at most $k$ roots can be proved by induction on degree. If we don't want to use field-theoretic language, the induction step is that if $r$ is a root modulo $q$ of the polynomial $P(x)$, then there is a polynomial $Q(x)$ with integer coefficients such that $P(x)\equiv (x-r)Q(x) \pmod{q}$. The proof is essentially the same as the high school proof of the Remainder Theorem. Divide $P(x)$ by $x-r$ in the usual way, and prove that the remainder is congruent to $0$ modulo $q$ by putting $x=r$.

(ii): If we are allowed to use the fact that $q$ has a primitive root, meaning, in group-theoretic terms, that the multiplicative group modulo $q$ is cyclic, any primitive root of $q$ can be taken as $c$.

-
+1: It is a bit difficult to judge here, which bits of theory the OP would be familiar with. This is a valiant effort to cover all the simple bases. I don't see the need to make your answer CW (you were first anyway). Your call, of course. –  Jyrki Lahtonen Aug 13 '11 at 8:03
@Jyrki Lahtonen: I don't understand this CW business. Is it that I made too many edits? If so, I should probably leave the site, since I will always seek to make improvements. Has the question become CW? I certainly did not intend it to be. –  André Nicolas Aug 13 '11 at 11:20
Very unfortunate :-( I also edit a lot. But there is a 10 edit limit. After that an answer becomes CW. IIRC you have a grace period of 5 minutes to edit as many times as you can, but I'm not sure. I think the reason for the rule is some artificial scenario, where somebody could try to draw more attention to his/her answer by editing a comma every now and then. May be a moderator can reset it? May be we should ask about this in Meta? I made my answer a CW as well, as yours should get the priority. –  Jyrki Lahtonen Aug 13 '11 at 12:13
According to an answer by Jeff Atwood a moderator may be able to help. I will attempt to flag one here. –  Jyrki Lahtonen Aug 13 '11 at 12:58
I flagged the moderators. May be they will de-wikify this for you! –  Jyrki Lahtonen Aug 13 '11 at 13:08

Hint (if you have covered group homomorphisms): When $p$ is not a factor of $q-1$, then $(q-1,p)=1$. By Lagrange's theorem there are no elements of order $p$ in the multiplicative group $G=\mathbf{Z}_q^*$. Therefore the homomorphism $f:x\mapsto x^p$ from $G$ to itself is injective (check that this is a homomorphism). As $G$ is finite then $f$ must also be ...

Hint2 (for the other direction given that theremay be a problem): If your book has covered the fact that $\mathbf{Z}_q^*$ is a cyclic group (or that $\mathbf{Z}_q$ is a field), you can use that to show that the mapping is not surjective, when $p\mid q-1$.

-

Here is another way of proving the theorem, formulated as a theorem in the book Number Theory For beginners, by A.Weil.

Theorem XI.I Let $p$ be a prime, $m$ an integer >0, and â^an integer prime to $p$; put $d=(m,p-1)$. Then the congruence $x^m \equiv a\pmod p$ has either $d$ solutions modulo $p$ or no solution; it has a solution if and only if the congruence $y^d \equiv a\pmod p$ has a solution; this is so if and only if $a^{(p-1)/d} \equiv 1\pmod p$, and there are exactly $(p-1)/d$ such values of $a$ modulo $p$.

Except for some changes of the notations, this theorem can be viewed as a more detailed description of the situations in question, by the only use of the theory of groups(hence it is for the beginners). In particular, the last assertion is precisely what the OP wanted to prove.

-
In addition, the letters ought to be transformed by: $m=>p, p=>q$. Then one verifies at once that, if and only if $d=1$, the number of classes $k^p$ modulo $q$ is q-1. Perhaps this was already stated in the above(and somewhat too long) comments, so that no one cared to bother me? If so, I delete it... –  awllower Aug 21 '11 at 14:03
thanks for the answer, @awllower. I agree with what you say, except that the theorem's last assertion is stronger than what I wanted to show -- it also characterizes the number of classes when q == 1 mod p. For my purposes (given p, finding q so that k^p falls into q-1 classes, so that computed numbers can quickly/efficiently be recognized as probable p'th powers) I don't care about that case, although other people could very well care about it. –  jwpat7 Aug 22 '11 at 21:02
Thanks for the explanation of your purport, @jwpat7. –  awllower Aug 23 '11 at 2:14