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: enter image description here

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

enter image description here

  • $\begingroup$ The question you posed does not match the statement in the scan from the book at the end of the question. And the answer to your question as posed is that the theorem is false. $\endgroup$ – Marc van Leeuwen Jun 3 '14 at 9:14
  • $\begingroup$ As Marc has shown, your statement of the theorem at the top of your question does not have all the assumptions necessary, and his answer gives a counter-example. So please always state all assumptions governing any statement. It would be good for you to edit your question to include them. $\endgroup$ – user21820 Jun 3 '14 at 9:20

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

  • $\begingroup$ How do you conclude "Therefore there are exactly $g$ solutions for $\text{ind}_r x$"? $\endgroup$ – Shuzheng Jun 3 '14 at 8:09
  • $\begingroup$ @user111854: Please see if my expanded explanation is clear now. $\endgroup$ – user21820 Jun 3 '14 at 8:50
  • $\begingroup$ Thank you, I will read through the details now. However, I thought a mathematical proof should be self-contained ? If so much needs to be added as your answer to a mathematical proof, how can the proof be complete ? $\endgroup$ – Shuzheng Jun 3 '14 at 9:12
  • $\begingroup$ @user111854: Different people have different sized skips in steps. No one would write every single application of an axiom down, such as commutativity or associativity in a field. So it's a matter of (subjective) judgement as to what to leave out. $\endgroup$ – user21820 Jun 3 '14 at 9:13
  • $\begingroup$ @user111854: So is the whole proof clear now? In general it is understood that for any integer $a,b,k,m$ such that $k,m > 0$, we have $ak \equiv b \pmod{mk}$ is equivalent to $a \equiv \frac{b}{k} \pmod{m}$, and many people won't justify related facts like the number of solutions in some range. $\endgroup$ – user21820 Jun 3 '14 at 13:22

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.

  • $\begingroup$ Apparnetly the theorem is under the assumption that there is a primitive root modulo $n$. $8$ doesn't have one. $\endgroup$ – user21820 Jun 3 '14 at 9:05
  • $\begingroup$ @user21820 No such hypothesis is given in the title or following statement of the theorem. I see that the hypothesis does occur in the image at the end of the question, but that does not make it part of the actual question. I will retain this answer as long as OP does not change the question. $\endgroup$ – Marc van Leeuwen Jun 3 '14 at 9:11
  • $\begingroup$ Well he asked for an explanation of the proof in his book, and your answer isn't one. But I certainly agree that we should be clear in stating our questions to include every assumption. $\endgroup$ – user21820 Jun 3 '14 at 9:15
  • $\begingroup$ The theorem says "Let $n$ be a positive integer having a primitive root and support $\gcd(a,n)=1$". $\endgroup$ – Shuzheng Jun 3 '14 at 11:00
  • $\begingroup$ @user111854 That is not what it says in the title, or in the statement just below the title. Please reformulate the question to ask what you actually want to ask. $\endgroup$ – Marc van Leeuwen Jun 3 '14 at 11:56

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.