Proof of k'th power theorem: $x^k \equiv a \pmod n$ has a solution $\iff$ $a^{\phi(n)/\gcd(k, \phi(n))} \equiv 1 \pmod n$.

Question

Proof of k'th power theorem: $x^k \equiv a \pmod n$ has a solution $\iff$ $a^{\phi(n)/\gcd(k, \phi(n))} \equiv 1 \pmod n$, where $n$ has a primitive root.

I have proven the following theorem myself:

However, I can't follow the steps in the "Conversely"-part below. I see that $r$ is an primitive root modulo $n$ and $r^{(ind_r a)} \equiv a \pmod n$.

But why does $\gcd(k, \phi(n)) \mid (ind_r a)$ imply that there are $\gcd(k, \phi(n))$ (in total) solutions to $k (ind_r x) \equiv (ind_r a) \pmod{\phi(n)}$ ? I see that theorem 2.77 is related to this linear congruence, but I don't see how the solutions come into play.

Also why are solutions to $k (ind_r x) \equiv (ind_r a) \pmod{\phi(n)}$ also solutions to $x^k \equiv a \pmod n$ ?

Answer 1

Let $g = \gcd(k,φ(n))$ and $k = gm$ and $φ(n) = gd$

If $k(ind_r x) \equiv ind_r a \pmod{φ(n)}$:

  $x^k \equiv r^{k(ind_r x)} \equiv r^{ind_r a} \equiv a \pmod{n}$ [answering your 2nd question]

  $gm(ind_r x) + p (gd) = ind_r a$ for some integer $p$

  Thus $ind_r a = q g$ for some integer $q$

  Thus $m(ind_r x) + p d = q$

  Thus $m(ind_r x) \equiv q \pmod{d}$

  Thus $ind_r x \equiv q m^{-1} \pmod{d}$ because $\gcd(m,d) = 1$

  [Now we simply work backwards to check that the final equation above is equivalent to the original.]

  Therefore there are at most $g$ solutions for $ind_r x$ in the range $[0..gd-1]$

  Let $s \in [0..d-1]$ such that $s \equiv q m^{-1} \pmod{d}$

  Let $S = \{ s + d t : t \in [0..g-1] \} \subseteq [0..gd-1]$

  For any integer $t \in [0..g-1]$:

    If $ind_r x = s + d t$:

      $m(ind_r x) \equiv ms \equiv q \pmod{d}$

      Thus $k(ind_r x) \equiv ind_r a \pmod{gd}$

  Therefore $S$ is a set of $g$ solutions for $ind_r x$

  Therefore there are exactly $g$ solutions for $ind_r x$ in the range $[0..gd-1]$

Answer 2

The theorem is false, so one shouldn't be able to prove it. Take $n=8$, so $\phi(n)=4$, and $a=3$, $k=2$. Then $x^k\equiv a\pmod n$ becomes $x^2\equiv3\pmod8$ which has no solution. However $a^{\phi(n)/\gcd(k, \phi(n))} \equiv 1 \pmod n$ becomes $3^{4/2}=3^2\equiv1\pmod8$, which is true.

Answer 3

Let me try to answer your question by giving what I hope is a clear proof of your proposition. Assume that $n$ has a primitive root, and that $k$ is arbitrary but $a$ is relatively prime to $n$ and we seek solutions $x$, also relatively prime to $n$, to the congruence $$x^k \equiv a \pmod n.$$ The number of integers relatively prime to $n$ is $\phi(n)$ and they form a group under multiplication modulo $n$. This group is assumed to by cyclic, generated by a primitive root which I denote $g$. I also set $m=\phi(n)$ to simplify notation. Then if $a=g^l$ the problem is to find integer $t$ such that $$(g^t)^k \equiv g^l \pmod n$$ this means $$g^{kt-l}\equiv 1 \pmod n$$ and this is equivalent to $m |kt-l$. So we essentially have to solve the problem of finding all solutions $t$ to $$kt\equiv l \pmod m$$ clearly if this has a solution then $(k,m) | l$.

So now conversely, assume that $(k,m) | l$, then we have a congruence $$\frac{k}{(k,m)}t\equiv \frac{l}{(k,m)}\pmod{\frac{m}{(k,m)}}$$ and this has a solution since $\frac{k}{(k,m)}$ and $\frac{m}{(k,m)}$ are relatively prime. This solution will also solve the congruence modulo $m$. It remains to find the number of distinct solutions modulo $m$. So assume $$kt\equiv l \pmod m$$ and $$ks\equiv l \pmod m$$ thus, $k(t-s)\equiv 0 \pmod m$ and this implies that $\frac{m}{(k,m)}|t-s$. So consider $$t+\alpha \frac{m}{(k,m)} \ \ \ \text{for}\ \ \alpha=0,1,\ldots ,(k,m)-1$$ $$k\left(t+\alpha \frac{m}{(k,m)} \right)=kt+\alpha \frac{k}{(k,m)}m \equiv kt \equiv l \pmod m$$ So these represent all $(k,m)$ distinct modulo $m$ solutions corresponding to $(k,m)$ distinct modulo $n$ solutions $g^t$ of the original question.