Dejemos que $p$ y $q$ sean primos relativos, $n$ número entero positivo.
Dado
- $n\bmod p$ y
- $n\bmod q$
cómo calcular $n\bmod (pq)$ ?
Respuestas
¿Demasiados anuncios?
Desde $p$ y $q$ son relativamente primos, hay enteros $a$ y $b$ tal que $ap+bq=1$ . Puede encontrar $a$ y $b$ utilizando el Algoritmo euclidiano ampliado . Entonces $n\equiv aps+bqr \bmod pq$ si $n\equiv r \bmod p$ y $n\equiv s \bmod p$ .
Como pedja mencionado, esta es una prueba constructiva de la Teorema del resto chino .
jwarzech
Puntos
2769
Por el hecho de que $p,q$ son relativamente primos, podemos encontrar coeficientes $a,b$ tal que:
$$ap + bq = 1$$
Con estos coeficientes podemos reconstruir una solución para n a partir de sus residuos módulo $p$ y $q$ . Di:
$$n \equiv r \mod p$$ $$n \equiv s \mod q$$
Entonces esto funciona: $ n = sap + rbq $ desde:
$$bq \equiv 1 \mod p$$ $$ap \equiv 1 \mod q$$
Por supuesto, la expresión anterior para $n$ puede reducirse en módulo $pq$ sin afectar a los residuos modulo $p$ y $q$ .
David HAust
Puntos
2696
Se puede utilizar la identidad de Bezout $\rm\:a\:p + b\:q = 1\:$ obtenido por el algoritmo euclidiano ampliado. Pero, en la práctica, a menudo es más conveniente utilizar la forma siguiente, por ejemplo, ver mi Puestos fáciles de CRT.
Teorema (Easy CRT) $\rm\ \ $ Si $\rm\ p,\:q\:$ son enteros coprimos entonces $\rm\ p^{-1}\ $ existe $\rm\ (mod\ q)\ \ $ y
$\rm\displaystyle\quad\quad\quad\quad\quad \begin{eqnarray}\rm n&\equiv&\rm\ a\ (mod\ p) \\ \rm n&\equiv&\rm\ b\ (mod\ q)\end{eqnarray} \ \iff\ \ n\ \equiv\ a + p\ \bigg[\frac{b-a}{p}\ mod\ q\:\bigg]\ \ (mod\ p\:\!q)$
Prueba $\rm\ (\Leftarrow)\ \ \ mod\ p\!:\:\ n\equiv a + p\ (\cdots)\equiv a\:,\ $ y $\rm\ mod\ q\!:\:\ n\equiv a + (b-a)\ p/p \equiv b\:.$
$\rm\ (\Rightarrow)\ \ $ La solución es única $\rm\ (mod\ p\!\:q)\ $ ya que si $\rm\ x',\:x\ $ son soluciones entonces $\rm\ x'\equiv x\ $ mod $\rm\:p,q\:$ por lo tanto $\rm\ p,\:q\ |\ x'-x\ \Rightarrow\ p\!\:q\ |\ x'-x\ \ $ desde $\rm\ \:p,\:q\:$ coprime $\rm\:\Rightarrow\ lcm(p,q) = p\!\:q\:.\quad$ QED
