We know that method of finding $k^{th}$ root moduo $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$ be 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}$$

  • $\begingroup$ This works much more generally - see my answer. $\endgroup$ – Bill Dubuque Dec 31 '16 at 22:49
  • $\begingroup$ @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. $\endgroup$ – Anurag A Jan 1 '17 at 3:14
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Jan 1 '17 at 3:18
  • $\begingroup$ @BillDubuque That makes perfect sense. $\endgroup$ – Anurag A Jan 1 '17 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.


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.