Encontrar el $k^{th}$ raíz módulo m

Question

Sabemos que el método de encontrar $k^{th}$ raíz modua $m$ es decir, si $$x^k\equiv b\pmod m,\tag {$ \N - Clubsuit $}$$ con $\gcd (b,m)=1$ y $\gcd(k,\varphi(m))=1$ entonces $x\equiv b^u\pmod m$ es una solución a $(\clubsuit)$ , donde $ku-v\varphi(m)=1$ . Porque $$\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}$$

Así, $x\equiv b^u\pmod m$ es una solución a $(\clubsuit)$ .

Aquí utilizamos $\gcd(b,m)=1$ ya que utilizamos el teorema de Euler de que $b^{\varphi(m)}\equiv1\pmod m$ .

Pero se me pide que demuestre que si $m$ sea el producto de primos distintos, entonces $x\equiv b^u \pmod m$ es siempre una solución, incluso si $\gcd (b,m)\gt1.$

Lo que hice, es decir $m=p_1p_2$ . Entonces $\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}$$

Ahora, sólo tenemos que calcular $b^{(p_1-1)(p_2-1)}\pmod {p_i}$ . Aquí me quedé atascado, porque realmente no puedo usar el pequeño teorema por cada $p_i$ ', ya que algunos $p_i$ puede existir en $b$ .

¿Puede alguien ayudarme?

Answer 1

En su caso de $m=p_1p_2$ . Si $\gcd(b,m)>1$ entonces $\gcd(b,m) \in \{p_1,p_2,m\}$ . Sin pérdida de generalidad, digamos $\gcd(b,m)=p_1$ . Entonces \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*} Asimismo, \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*} Así, $$b^{ku} \equiv b \pmod{p_1p_2}$$

Answer 2

$b^{\large ku}\!\equiv b\pmod{\!pq}\,$ es el caso $\,i,j,k=1\,$ de esta generalización de la Fermat Euler $\color{blue}{\rm (E)}$ teorema.

${\bf Theorem}\,\ \ n^{\large k+\phi}\equiv n^{\large k}\pmod{\!p^i q^j}\ \ $ si $\,p\ne q\,$ son primos, $ \ \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},\ $ por $\,\ 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}\ $ por $\ n^{\large k} = n^{\large k-i} \color{#c00}n^{\large i} = n^{\large k-i} (\color{#c00}{mp})^{\large i}$ y $\,k\ge i$

Así que $\ p^{\large i}\mid n^{\large k+\phi}\!-n^{\large k}.\,$ Por simetría $\,q^{\large j}$ lo divide también, por lo que también lo hace su lcm $ = p^{\large i} q^{\large j}\,\ $ QED

Nota: $\ $ La prueba anterior se extiende inmediatamente a un número arbitrario de primos, véase esta respuesta. Ver también La función Lambda de Carmichael, una generalización de La función phi de Euler.