# Finding the $k^{th}$ root modulo m

We know that method of finding $$k^{th}$$ root modulo $$m$$, i.e. if $$x^k\equiv b\pmod m,\tag {\clubsuit}$$ with $$\gcd (b,m)=1$$, and $$\gcd(k,\varphi(m))=1$$, then $$x\equiv b^u\pmod m$$ is a solution to $$(\clubsuit)$$, where $$ku-v\varphi(m)=1$$. Because $$\begin{array} {}x^k &\equiv \left(b^u\right)^k\pmod m\\ &\equiv b^{uk}\pmod m\\ &\equiv b^{1+v\varphi (m)}\pmod m\\ &\equiv b\cdot b^{v\varphi(m)}\pmod m\\ &\equiv b\cdot \left(b^{\varphi (m)}\right)^v\pmod m\\ &\equiv b\pmod m \end{array}$$

Thus $$x\equiv b^u\pmod m$$ is a solution to $$(\clubsuit)$$.

Here we use $$\gcd(b,m)=1$$, since we used Euler's theorem that $$b^{\varphi(m)}\equiv1\pmod m$$.

But I am asked to prove that if $$m$$ is the product of distinct primes, then $$x\equiv b^u \pmod m$$ is always a solution, even if $$\gcd (b,m)\gt1.$$

What I did, is say $$m=p_1p_2$$. Then $$\varphi(m)=(p_1-1)(p_2-1)$$ $$\begin{array} {}b^{uk}&\equiv b\cdot b^{\varphi (m)}\pmod m\\ &\equiv b\cdot b^{(p_1-1)(p_2-1)}\pmod m \end{array}$$

Now, we just have to compute $$b^{(p_1-1)(p_2-1)}\pmod {p_i}$$. Here I got stuck, because I really can't use the little theorem for every $$p_i$$'s, since some $$p_i$$ can exist in $$b$$.

Can someone help me?

In your case of $m=p_1p_2$. If $\gcd(b,m)>1$, then $\gcd(b,m) \in \{p_1,p_2,m\}$. Without the loss of generality, say $\gcd(b,m)=p_1$. Then \begin{align*} b^{ku} & \equiv b \, . b^{(p_1-1)(p_2-1)}\\ & \equiv 0 \pmod{p_1} & (\because \gcd(b,m)=\gcd(b,p_1)=p_1)\\ & \equiv b \pmod{p_1} \end{align*} Likewise \begin{align*} b^{ku} & \equiv b \, . b^{(p_1-1)(p_2-1)}\\ & \equiv b .1 \pmod{p_2} & (\because \gcd(b,p_2)=1 \text{ so Fermat's little theorem works})\\ & \equiv b \pmod{p_2} \end{align*} Thus $$b^{ku} \equiv b \pmod{p_1p_2}$$

• This works much more generally - see my answer. Commented Dec 31, 2016 at 22:49
• @BillDubuque my intent was not to say this idea works only for two primes. This was just for demo purposes and to answer OP's question. Commented Jan 1, 2017 at 3:14
• The point of my comment was to inform readers of the relationship between our answers (which may not be immediately obvious), i.e that the above generalizes widely. Commented Jan 1, 2017 at 3:18
• @BillDubuque That makes perfect sense. Commented Jan 1, 2017 at 3:45

$b^{\large ku}\!\equiv b\pmod{\!pq}\,$ is case $\,i,j,k=1\,$ of this generalization of the Fermat Euler $\color{blue}{\rm (E)}$ theorem.

${\bf Theorem}\,\ \ n^{\large k+\phi}\equiv n^{\large k}\pmod{\!p^i q^j}\ \$ if $\,p\ne q\,$ are prime, $\ \color{#0a0}{\phi(p^i),\phi(q^j)\mid \phi},\,$ $\, i,j \le k\ \ \$

${\bf Proof}\,\ \ p\nmid n\,\Rightarrow\, {\rm mod\ }p^{\large i}\!:\ n^{\large \phi}\!\equiv 1\,\Rightarrow\, n^{\large k + \phi}\equiv n^{\large k},\$ by $\,\ n^{\large \color{#0a0}\phi} = (n^{\color{#0a0}{\large \phi(p^{\Large i})}})^{\large \color{#0a0}\ell}\overset{\color{blue}{\rm (E)}}\equiv 1^{\large \ell}\equiv 1$

$\qquad\quad\ \ \color{#c00}{p\mid n}\,\Rightarrow\, {\rm mod\ }p^{\large i}\!:\ n^{\large k}\!\equiv 0\,\equiv\, n^{\large k + \phi}\$ by $\ n^{\large k} = n^{\large k-i} \color{#c00}n^{\large i} = n^{\large k-i} (\color{#c00}{mp})^{\large i}$ and $\,k\ge i$

So $\ p^{\large i}\mid n^{\large k+\phi}\!-n^{\large k}.\,$ By symmetry $\,q^{\large j}$ divides it too, thus so too does their lcm $= p^{\large i} q^{\large j}\,\$ QED

Remark $\$ The above proof immediately extends to an arbitrary number of primes, see this answer. See also Carmichael's Lambda function, a generalization of Euler's phi function.