¿Cómo puedo resolver un problema utilizando el teorema del resto Chino y ¿cómo funciona el operador mod es entendido correctamente?

Question

La situación es la siguiente:

$$n = 3a + 2$$

$$n = 7b + 5$$

$$n = 8c + 9$$

Encontrar el $n$ a menos del $100$ y $a$, $b$ y $c$ son enteros positivos.

Sé que esto se puede resolver utilizando el teorema del resto Chino, pero no sé cómo usarlo. Por lo tanto, me gustaría que alguien me pudieran explicar exactamente cómo se $\mod{}$ operador de obras.

Lo único que sé es que $\bmod$ es utilizado para expresar el resto de la división euclidiana. Como este

$5$ dividido por $2$ significa que:

$5\,\bmod\,2 = 1$

Porque el resto es $1$.

Pero, ¿y si la situación es como este?:

$2\,\bmod\,9$

¿Significa esto

$$\frac{2}{9} = 0.2 \times 9 + 2 ?$$

Así que el resto es $2$? No parece correcto como ir hacia atrás, no se producen $2$, en el sentido de $0.2\times 9 + 2$ no $2$.

Cómo acerca de los números negativos

Sin embargo, ¿cómo es trabajar con números negativos? Como:

$-3\bmod 25$

Como se mencionó anteriormente, si tengo que seguir la misma ruta que yo pueda encontrar resultados extraños.

Pero eso es sólo una parte del problema, como la segunda cosa es Cómo entender esta al $\mod{}$ se utiliza de la siguiente manera:

$24\equiv 14 \left ( \bmod 10 \right )$

De lo que yo había entendido lo que significa que ambos comparten el mismo resto que es $4$.

Pero el problema radica en cómo traducir las ecuaciones se me ha dado en la ecuación de arriba, la cual utiliza $\mod{}$?

Por lo tanto, me gustaría que alguien me pudiera ayudar con un claro paso a paso de la solución que puede explicar la forma de construir el $\mod{}$ ecuaciones y cómo resolverlos de la manera más sencilla posible.

Answer 1

Como usted dice; $x\equiv a\bmod p$ le dice que cuando se divide $x$$p$, le da un resto de $a$.

Por eso, $5/2$ le da un resto de $1$; así que esto es equivalente a decir que el $5\equiv 1\bmod 2.$

En cuanto a las expresiones tales como $-3\bmod 25$. Ser conscientes de que un número tener un resto de $-3$ cuando se divide por $25$ es el mismo que el número que han resto $22$; por lo $-3\bmod 25$ es lo mismo que $22\bmod 25.$

---

Aplicando esto a su problema en la mano, $n=3a+2$ es lo mismo que $n\equiv 2\bmod 3.$ Asimismo, $n=7b+5$ es equivalente a $n\equiv 5\bmod 7.$ Finalmente, $n=8c+9$ es equivalente a $n\equiv 9\bmod 8,$ que es el mismo que $n\equiv 1\bmod 8.$, por Lo que estamos interesados en resolver el sistema $$n\equiv 2\bmod 3,\quad n\equiv 5\bmod 7,\quad n\equiv 1\bmod 8.$$ As you rightfully point out, we may use the Chinese remainder theorem and come to a conclusion that this system has a unique solution in the form of $$n\equiv x\bmod3\cdot 7\cdot 8=168,$$ where $x$ es la respuesta que buscamos. Así que vamos sistemática de resolver esto.

La congruencia $n\equiv 1\bmod 8$ implica $n=8c+1.$ Sustituyendo esto en la $n\equiv 5\bmod 7$ da congruencia $$8c+1\equiv 5\bmod 7.$$ Solving this gives $$8c\equiv 4\bmod 7,$$ $$c\equiv 4\bmod 7.$$ This means there exists an integer $d$ such that $c=7d+4.$ Substituting this into our expression involving $n$ gives $n=56d+33.$ Now, substituting this expression into the $n\equiv 2\bmod 3$ congruence gives $$56d+33\equiv 2\bmod 3.$$ Solving this gives $$56d\equiv 2\bmod 3,$$ $$2d\equiv 2\bmod 3,$$ $$d\equiv 1\bmod 3.$$ This means there exists an integer $e$ such that $d=3e+1.$ Substituting this into our expression involving $n$ gives $n=168e+89.$ Now, this means that $n\equiv 89\bmod 168.$ Since this is less than $100$; we are done, concluding that $$x=89.$$

Espero que esto ayude. Sientete libre de preguntar me preguntas si usted todavía está confundido.

Answer 2

El $\textrm{mod}$ notación no es un operador que le da una sola salida.

No leer como si fuera un código de computadora. Sólo quiero leer el $\textrm{mod}$ notación en inglés. $\text{mod}\;n$ significa que la anterior ecuación o fórmula está bajo módulo de $n$. En el contexto de los números enteros, consideramos que cada número entero por su Euclidiana resto cuando se divide por $n$.

$\equiv$ es una notación para las relaciones de equivalencia. Por favor, lea sus presentaciones en internet.

Por ejemplo, nos dicen que el 13 es equivalente (o congruentes, algunos incluso dicen igual, dependiendo del contexto) 23 módulo 10, que se denota por a $13\equiv23\;\textrm{mod}\;10$ porque tienen el mismo resto al dividir por 10, que es de 3. Número negativo suele leer "a la inversa". Por ejemplo, $13\equiv-7\;\textrm{mod}\;10$.

Como para su rompecabezas en el principio, usted no tiene que usar Teorema del Resto Chino. Creo Teorema del Resto Chino es un poco de un salto cuando usted apenas está aprendiendo el mod de la notación. Tratar de resolver el rompecabezas de sí mismo sin el teorema y compartir donde usted es el primero.

Answer 3

Lo único que sé es que $\textrm{mod}$ es utilizado para expresar el resto de la división euclidiana. Como este

$\textrm{5 divided by 2}$ significa que:

$5\,\textrm{mod}\,2 = 1$

Porque el resto es $1$.

Hasta ahora tan bueno. También tenga en cuenta que $2 \times 2 + 1 = 5$.

Pero, ¿y si la situación es como este?:

$2\,\textrm{mod}\,9$

¿Significa esto?:

$\frac{2}{9}= 0.2\times 9 + 2$

Así que el resto es $2$?. No parece correcto como ir hacia atrás, no se producen $2$, en el sentido de $0.2\times 9 + 2$ no $2$.

Aquí tienes fuera de la pista. El "significado" es $0 \times 9 + 2 = 2$. Limitando nuestra atención a los números enteros es una especie de punto de moduli y restos.

Cómo acerca de los números negativos

Sin embargo, ¿cómo es trabajar con números negativos? Como:

$-3\,\text{mod}\,25$

Como se mencionó anteriormente, si tengo que seguir la misma ruta que yo pueda encontrar resultados extraños.

No es broma. $-1 \times 25 + 22 = -3$. Estoy repitiendo lo que otros ya han dicho?

Pero eso es sólo una parte del problema, como la segunda cosa es Cómo entender esta al $\textrm{mod}$ se utiliza de la siguiente manera:

$24\equiv 14 \left ( \textrm{mod 10} \right )$

De lo que yo había entendido lo que significa que ambos comparten el mismo resto que es $4$.

Eso es correcto, y es cierto para cualquier entero positivo tener un dígito menos significativo de $4$ base $10$. También de cualquier número entero negativo de tener un dígito menos significativo de $6$ base $10$.

Imagen de la recta numérica real con el infinito negativo muy lejos a la izquierda, mucho más allá del alcance de su visión, y el infinito positivo muy lejos a la derecha, también más lejos que se puede ver.

Ahora la imagen de puntos para todos los múltiplos de su módulo, como $10$. Un resto de $4$ significa que cualquier número de la unidad de cuatro pasos a la derecha de $10$, y un resto de $-6$ significa que cualquier número seis de la unidad de pasos a la izquierda.

Como para el ejercicio, trate de resolver con sólo dos congruencias en lugar de tres. Por ejemplo, trate de ver si se puede solucionar $n = 3a + 2$ $n = 7b + 5$ sin tener que preocuparse por si esto también resuelve $n = 8c + 9$. En el espacio entre el $0$ $21$ (que es igual a $3 \times 7$) no debe ser una respuesta, y otra entre el$21$$42$, y así sucesivamente y así sucesivamente.

Answer 4

Dado $k$ ser cualquier número entero que sea, ¿cuántos de los números primos son de la forma $4k + 1$? $4k - 1$? $6k + 1$? etc. A menudo en la teoría de los números que mirar los números de la forma $mk + r$ donde $m$ es un módulo, generalmente positiva, y $r$ es un resto, generalmente satisfactorio $-m < r < m$.

A continuación, el valor exacto de $k$ no es tan importante, o puede ser ignorada temporalmente. Y así no es la forma abreviada conveniente $n \equiv r \bmod m$ o $n \equiv r \pmod m$ (un poco más de tinta, pero cero más bytes en su TeX fuente). Esto significa $n = mk + r$ pero no estamos demasiado preocupados con $k$, al menos por ahora.

Entonces, para solucionar $$n \equiv 2 \bmod 3$$ $$n \equiv 5 \bmod 7$$ $$n \equiv 9 \bmod 8$$ we can, um, wait a minute, let's rephrase that last one as $$n \equiv 1 \bmod 8$$ Now we have a system of simultaneous congruences, and since the moduli are coprime, we're not worried about contradictory congruences (e.g., $1 \bmod 2$ and $2 \bmod 4$).

Since I'm not going to be tested on this, I can just ask Wolfram Alpha: ChineseRemainder[{2, 5, 1}, {3, 7, 8}]. Besides, the steps to solving simultaneous congruences are covered in other Math.SE questions and answers.

Wolfram Alpha tells me the answer is 89. It checks out: $$89 = 3 \times 29 + 2$$ $$89 = 7 \times 12 + 5$$ $$89 = 8 \times 11 + 1$$ Well, that last one needs to be adjusted: $c = 10$ rather than 11.

While 89 is the only positive number less than 100 satisfying the simultaneous congruences, it is only one of infinitely many solutions without the restriction. To find the other solutions, multiply the moduli (in this case 168) and add or subtract as many times as you wish. Then for example $$257 = 3 \times 85 + 2$$ $$257 = 7 \times 36 + 5$$ $$257 = 8 \times 32 + 1$$ $-79$ also checks out, but mind your direction.

---

And by the way, 89 is a prime of the following forms: $6k - 1$ (same thing as $6k + 5$), $4k + 1$, $8k + 1$, and others of decreasing number-theoretic interest.

If I may pique your interest in algebraic number theory, that $89 \equiv 1 \bmod 8$ means that 2 is not prime in $\mathcal O_{\mathbb Q(\sqrt{89})}$, and indeed $$(-1)\left(\frac{9}{2} - \frac{\sqrt{89}}{2}\right)\left(\frac{9}{2} - \frac{\sqrt{89}}{2}\right) = 2.$$

Answer 5

$a \equiv b \mod n$ (nótese la equivalencia signo, $\equiv$ tiene tres bares, no$2$) $a$ $b$ ambos tienen el mismo resto al dividir por $n$.

Así, por ejemplo, si$5 \equiv 1 \mod 2$, pero también se $5 \equiv 7 \mod 2$.

Un par de cosas a considerar:

1) $a \equiv b \mod n \iff \frac {a-b}n \in \mathbb Z \iff a = b + kn$ para algunos entero $k$. Y $a \equiv 0 \mod n\iff n|a$.

2) Para cualquier número natural $n$, podemos dividir los números enteros, $\mathbb Z$, exactamente $n$ diferentes subconjuntos, o "clases". Clase $[0] = \{...., -2n, -n, 0, n, 2n, 3n,...\}=\{kn + 0|k\in \mathbb Z\}$; estos son todos los enteros que han resto $0$ cuando se divide por $n$. Clase $[1] = \{...,-2n, -n+1, 1, n+ 1, 2n+1,...\}=\{kn + 1|k\in \mathbb Z\}$; estos son todos los enteros que han resto $1$ cuando se divide por $n$. Y así sucesivamente. Clase $[i] = \{...,-2n, -n+i, i, n+ i, 2n+i,...\}=\{kn + i|k\in \mathbb Z\}$. Hay exactamente $n$ de estas clases. $a \equiv b \mod n$ significa que tanto $a$ $b$ pertenecen a la misma una de estas clases.

Las clases en 2) se llama equivalencia clases porque cuando se hace la aritmética básica en lo que respecta al resto cuando se divide por $n$, si los dos números tienen el mismo resto que son ... bueno... equivalente que es.

Proposición: Si $a \equiv b \mod n$$a \pm k \equiv b \pm k$$k*a \equiv k*b \mod n$$a^k \equiv b^k \mod n$. También si $c \equiv d \mod n$$a+c \equiv b+d \mod n$$ac \equiv bd\mod n$.

Ex: $5 \equiv 12 \mod 7$ $5k \equiv 12k \mod 7$ porque $12k = 7k + 5k \equiv 5k \mod 7$.

Para resolver una ecuación como $3x \equiv 6 \mod 9$ puede tener múltiples soluciones. $x$ $2$ porque $3*2 = 6\equiv 6 \mod 9$. Pero $x$ también puede ser $5$ porque $3*5 = 15 \equiv 6 \mod 9$. $x$ también podría ser $8$ becase $3*8 = 24\equiv 6 \mod 9$. La siguiente solución es$x = 11$$3*11=33\equiv 6 \mod 9$. Pero porque $2 \equiv 11 \mod 9$, $2$ y $11$ se considera que la misma solución, porque la $2$ $11$ son equivalentes (modulo $9$).

Así que resulta que hay tres clases de soluciones: $x \equiv 2 \mod 9$ o $x\equiv 5 \mod 9$ o $x \equiv 8 \mod 9$.

Por lo que el Teorema del Resto Chino dice:

Si usted tiene un sistema de ecuaciones:

$x \equiv a_1 \mod n_1$

$x \equiv a_2 \mod n_2$ ....

Y todas las $n_i$ son relativamente primos (no tienen factores en común), a continuación,

$x \equiv b \mod n_1n_2n_3....n_m$ tiene un modulo específico de la clase de mod $n_1n_2n_3...n_m$.

Ejemplo:

Si $x \equiv 1 \mod 2$

$x \equiv 1 \mod 3$

$x \equiv 0 \mod 5$

$x \equiv ???? \mod 30$ tiene una única solución (de las clases a las $[0]$$[29]$). Esa solución es $x \equiv 25 \mod 30$.

====

Así que a tu pregunta:

$n = 3a + 2 \iff n \equiv 2 \mod 3$.

$n = 7b + 5 \iff n \equiv 5 \mod 7$

$n = 8c + 9 \iff n \equiv 9 \equiv 1 \mod 8$.

Como $3,7, 8$ son relativamente primos, hay una solución modulo $3*7*8= 168$.

$n\equiv 3a + 2 \equiv 7b + 5 \mod 21$ tiene un valor posible (modulo $21$)

$3a + 2$ pueden $2,5,8,...., 20$. Y $7b + 5$ pueden $5,12, 19$. La única opción en común es $n \equiv 3a +2 \equiv 7b + 5\equiv 5 \mod 21$. Por lo $n = 21d + 5$ algunos $d$.

Ahora también contamos $n \equiv 8(c-1) +1 \mod 21*8$$n \equiv 21d + 5\mod 21*8$.

Por lo $8(c-1)+1$ pueden $1, 9,17,.....$ $21d+5$ pueden $5, 26, 47, 68, 89, 110, 131, 152$. El único en común es $89$.

Por lo $n \equiv 3a + 2 \equiv 7b + 5 \equiv 8(c-1) + 1 \equiv 89 \mod 168$

Y $a = \frac {87}3; b = \frac {84}7; c = \frac {80}8$.