Homomorphism definida por una función

Question

Deje $f: \mathbb{Z}_{143} \to\mathbb Z_{11} \times\mathbb Z_{13}$ ser un homomorphism y definir $f$ $f(x) = (x\mod11, x \mod13).$ Determinar un valor de $x\in \mathbb{Z}_{143}$ such that $f(x) = (7,4).$

Yo tengo ese $x\mod 11 = 7$ y $x\mod13=4$ por lo que esto implica $x = 7 + 11q$ $x = 4 + 13r$ algunos $q$$r$. Por lo tanto la combinación de los dos tengo $4+13r = 7 + 11q$ por lo tanto $3 = 13r - 11q.$

Aquí es donde me quedé atrapado (necesidad de revisar la teoría de los números de nuevo y Euclides de Alejandría).

¿Cómo puedo encontrar mi $q$ $r$ y completa el problema?

Answer 1

En este tipo de simultánea congruencias, el teorema del resto Chino es tu amigo. Pero usted debe, por supuesto, conocer una versión que muestra la forma más eficaz de llegar a una solución.

Para obtener una no demasiado grande respuesta para $x$, sugiero poner $y=x-4$ y resolver para $y$ primero, que ahora se dará a $y\equiv3\pmod{11}$$y\equiv0\pmod{13}$. Por lo que necesita un múltiplo $13k$ $13$ que da resto $3$ modulo $11$; desde $13$ da resto $2$, que necesita para resolver $2k\equiv3\pmod{11}$ que usted puede hacer casi a la vista por $k=7$ (o $k=-4$). Consigue $y=91$ $x=95$ (o $y=-52$$x=-48$).

En general después de la simplificación de la necesidad de resolver un congrence del tipo $ax=b\pmod{n}$ algunos $a,b,n$ (aquí se $(a,b,n)=(2,3,11)$). La forma sistemática de hacer esto es calcular los $d=\gcd(a,n)$, mientras que la búsqueda (un coeficiente de Bezout) $s$ tal que $d\equiv sa\pmod n$; ahora bien $d$ divide $b$ $x=(b/d)s$ es una solución, o $d$ no divide $b$ y no habrá ninguna solución, ya que la mayor reducción del modulo$~d$ da lo imposible congruencia $0x\equiv b\pmod d$.

Answer 2

Generalmente calculamos $gcd$ $13,11$ como sigue :

$13=1.11+2$

$11=5.2+1$

$2=2.1+0$

Ahora, como usted sabe, $(13,11)=1$ está seguro de que no existe $m,n\in \mathbb{Z}$ tal que $13m+11n=1$

Ahora, $1=11-5.2=11-5(13-11)=11+5.11-5.13=6.11-5.13$

Si usted tiene $1=6.11-5.13$, se puede encontrar $r,q$ tal que $3=13r-11q$???

simplemente multiplicando por 3 a ambos lados $3=18.11-15.13=13(-15)-11(-18)$

Answer 3

Quieres una solución para el sistema de congruencias

$$\begin{align*}x&=7\pmod {11}\\ x&=4\pmod{13}\end{align*}$$

Imitar (uno de) el Teorema del Resto Chino de pruebas: queremos encontrar a $\;t\in\Bbb Z\;$ s.t. $\;7+11t=4\pmod {13}\;$ desde entonces $\;x:=7+11t\;$ resuelve nuestro problema (por qué?):

$$11t=4-7=-3=10\pmod{13}\implies$$

$$\implies t=10\cdot 11^{-1}\pmod{13}=10\cdot 6=60=8\pmod{13}$$

Así que tome $\;x=11\cdot 8+7=95\;\ldots$