Menor entero positivo que da resto 5 cuando se divide por 6, resto 2 al dividirlo por 11, y el resto de los 31 cuando se divide por 35?

Question

¿Cuál es el menor entero positivo que le da el resto 5 cuando se divide por 6, da resto 2 al dividirlo por 11 y 31 cuando se divide por 35?

También, existen métodos estándar para resolver problemas como estos?

Answer 1

El sistema de ecuaciones $$ \left\{\begin{array}{ll} n \equiv 5 &\pmod{6} \\ n \equiv 2&\pmod{11} \\ n\equiv 31 &\pmod{35}\end{array}\right. $$ es equivalente a $n\equiv m\pmod{2\cdot 3\cdot 5\cdot 7\cdot 11}$ por el teorema del resto Chino.
Si $m_6, m_{11}, m_{35}$ es el entero más pequeño que las soluciones de los sistemas de $$ \left\{\begin{array}{ll} n \equiv 1 &\pmod{6} \\ n \equiv 0&\pmod{11} \\ n\equiv 0 &\pmod{35}\end{array}\right. \quad\left\{\begin{array}{ll} n \equiv 0 &\pmod{6} \\ n \equiv 1&\pmod{11} \\ n\equiv 0 &\pmod{35}\end{array}\right.\quad \left\{\begin{array}{ll} n \equiv 0 &\pmod{6} \\ n \equiv 0&\pmod{11} \\ n\equiv 1 &\pmod{35}\end{array}\right.$$ luego tenemos a $m\equiv 5m_6+2m_{11}+31 m_{35}\pmod{2310}$, e $m_6,m_{11},m_{35}$ no son difíciles de calcular. Por ejemplo, $m_6$ es un múltiplo de a$11\cdot 35$$\equiv 1\pmod{6}$, pero $$ k\cdot 11\cdot 35 \equiv 1\pmod{6} $$ es equivalente a $k\equiv 1\pmod{6}$, por lo tanto $m_6=11\cdot 35=385$. De manera similar se puede encontrar$m_{11}=210$$m_{35}=1716$, a continuación, volver a combinarlos con el fin de encontrar $m=\color{red}{101}$.

Answer 2

Si entiendo correctamente, usted quiere resolver el simultáneas congruencias $$x \equiv 5 \pmod 6$$ $$x \equiv 2 \pmod{11}$$ $$x \equiv 31 \pmod{35}$$ The moduli, $6, 11, 35$, are coprime, so the standard method comes from the Chinese remainder theorem.

Set $r_1 = 5$, $r_2 = 2$, $r_3 = 31$ (these are the remainders), $m_1 = 6$, $m_2 = 11$, $m_3 = 35$, $M = m_1 \times m_2 \times m_3 = 2310$.

Now we need to find $b_1, b_2, b_3$ such that $$b_i \frac{M}{m_i} \equiv 1 \pmod{m_i}.$$ For example, $b_1 = 1$ since $2310$ divided by $6$ is $385$ and $1 \los tiempos de 385 \equiv 1 \pmod 6$. I leave you to find $210b_2 \equiv 1 \pmod{11}$ and $66b_3 \equiv 1 \pmod{35}$.

Once you have your $b_i$, the answer is $$x = \sum_{i = 1}^3 r_i b_i \frac{M}{m_i} \mod{2310} = 101.$$ (he adaptado esta de http://oeis.org/wiki/Chinese_remainder_theorem)

Sólo para comprobar de nuevo, ir a Wolfram Alpha y escriba ChineseRemainder[{5, 2, 31}, {6, 11, 35}].

Answer 3

En lugar de aplicar mecánicamente la CRT fórmula, el siguiente método es generalmente más rápido y mucho más simple (aquí tan simple que puede ser calculada con la puramente mental aritmética).

${\rm mod}\ 35\!:\ {-}4\equiv n\iff n = -4+35j$

${\rm mod}\ 11\!:\ 2\equiv n = -4\!+\!35\,\color{#c00}j\equiv -4+2j\iff 6\equiv 2j\iff j\equiv3\iff \color{#c00}{j = 3+11k} $

Así tenemos a $\ n = -4+35(\color{#c00}{3+11k}) = 101+11\cdot 35k $

${\rm mod}\ 6\!:\ {-}1\equiv n\equiv 101+11\cdot 35\cdot\color{#0a0}k\equiv -1+k\iff k\equiv 0\iff\color{#0a0}{ k = 6m}$

Por lo tanto, tenemos $ \ n = 101+11\cdot 35\cdot\color{#0a0}{6m}$

---

Comentario $ $ Sólo cantidades muy pequeñas estaban involucrados porque hemos resuelto la congruencias con mayor módulos de primero, de modo que, al final, cuando los números son más grandes, esto se compensa por la computación en pequeños módulos. Podemos simplificar la aritmética mediante el uso de restos de menos magnitud, por ejemplo, se utilizó $\,-4\equiv 31\pmod{35}$. Tenga en cuenta que nosotros no necesita computar cualquier inversos (manteniendo el número tan pequeño como sea posible, se aumenta la probabilidad de que esto ocurra).

Este método también funciona incluso si los módulos no son pares coprime, aunque en este caso general, puede haber cero o varias soluciones. Además, se lleva a la conocida criterio para la existencia de una solución en el caso general - que caracteriza a la omnipresente Prüfer dominios. Generalizan en común muchos sistemas de numeración y se caracteriza por un muy gran número de propiedades interesantes, por ejemplo, Gauss, Lema de los contenidos, lcm y distribuye más de gcd (y al revés), contiene = divide por la aleta. gen. ideales, etc. Por lo tanto es bien vale la pena invertir el esfuerzo necesario para dominar este punto de vista de la CRT.

Answer 4

Si usted no está familiarizado o cómodo con el Teorema del Resto Chino puede hacer esto:

$x = 6j + 5$

$x = 11k + 2$

Por lo $6j + 5 = 11k +2$

$j = (11k - 3)/6 \in \mathbb Z$

$j = k + \frac 56k -1/2 \in \mathbb Z$

Por lo $\frac 56 k = M + 1/2$ para algunos entero $M$.

$3$ es el más pequeño de tal número, pero cualquier $6N + 3$ va a trabajar.

Por lo $6j + 5 = 11(6N + 3) +2 = 66N + 35$ (e $j = 11N + 5$ pero eso no es importante)

Por lo $x = 66*N + 35$

También sabemos $x = 35m + 31$

Por lo $66*N + 35 = 35m + 31$

$(66N + 4)/35= m \in \mathbb Z$

Por lo $N + \frac{31}{35}N + \frac 4{35} \in \mathbb Z$

La solución más sencilla es $N = 1$ pero cualquier $N = 1 + 35P$ va a hacer.

Por lo $x = 66(1 + 35P) + 35 = 35*66P + 101$.

$101$ es el número más pequeño que funciona.

Pero e $35*66P + 101$, también trabajo.

Answer 5

¿Cuál es el menor entero positivo que le da el resto 5 cuando se divide por 6

Es algo que puede ser escrito como $(6n+5)$

Da resto 2 al dividirlo por 11

Y también escrito como $(11m + 2)$

Permite hacer una pausa aquí:

Partimos de la suposición de 5. y decimos "que funciona de la primera regla, pero no el segundo."

Entonces decimos: 12 - 11 = 1.

Si queremos agregar de 12 a nuestras supongo que vamos a obtener un resto de que es uno más que el anterior supongo. Para obtener a partir de un resto de 5 a un resto de 2 necesitamos restar $3\cdot12, 5-36=-31.$

$-31?$ , Así que es un poco raro, y lo es, pero le permite aferrarse a ella ahora.

A continuación, el mínimo común múltiplo de 6 y 11 es de 66.

$66k - 31$ tiene restos de 5,2 cuando se divide por 6 y 11 respectivamente. Permite escribir como $66 (k-1) + 35$ debido a que los números positivos son más bonitas. Que $k$ es arbitraria... podemos fácilmente decir $66 k + 35$.

3ª regla: 31 cuando se divide por 35.

$\frac {(66 k + 35)}{35}$ da un resto de $31k$

$k = 1$, y nuestro número es $101$