Application of Fermat's Little Theorem and Lagrange

Question

This is the final part of a modular arithmetic question on a previous exam. The question is:

Assume that $k$ is a natural number with $(k,p-1)=1$. Let $l$ be an integer. Show that $$x^k \equiv l\,\mathrm{mod}\,p$$ has at most $1$ solution.

I’m struggling a bit with this. I wrote $1=ak+(p-1)b$ for integers $a$ and $b$. Then $$x\equiv x^{ak+(p-1)b}\equiv x^{ak}\cdot x^{(p-1)b}\equiv l^a\,\mathrm{mod}\,p .$$ I’m not sure whether this is the correct way to approach the problem. In previous parts of the question, I’ve used Fermat’s Little Theorem and the order of $a\,\mathrm{mod}\,q$, so I know I need to use this somewhere here. Can someone please guide me in the right direction?

Answer 1

That is a beautiful argument, and it seems correct. The only thing missing is that you assume $$x^{(p-1)b}\equiv_p 1$$ which is true only if $\gcd(x,p)=1$, in which case you have found the unique solution $x\equiv_pl^a$. If $\gcd(x,p)\neq 1$ there may be no solution.

Answer 2

Well, actually you already finished the exercise by yourself:

Suppose you have $x,y$ solutions to $x^k\equiv l\equiv y^k$. By your reasoning, you get that $$ x\equiv l^a \equiv y \pmod p $$ so they are the same solution.