Hay un no-fuerza bruta manera de encontrar a $x$ tal que $45\leq x < 200$, $x\equiv 0 \pmod{5}$ , $x\equiv1 \pmod{8}$, $x\equiv1 \pmod{12}$?

Question

Como dice el título, me pregunto si hay un no de fuerza bruta para determinar $x$ tal que $$45\le x<200,$$ $$x\bmod5\equiv0,$$ $$x\bmod8\equiv1,$$ $$x\bmod12\equiv1$$ Sé que puedo simplemente enumerar todos los números enteros en $[45, 200)$ para obtener la respuesta (145), pero me pregunto si hay una solución más elegante.

Answer 1

Sólo utilizar el teorema del resto Chino: $$x\equiv1\bmod12\implies x\equiv1\bmod3$$ $$x\equiv1\bmod8\land x\equiv1\bmod3\implies x\equiv1\bmod24$$ $$x\equiv1\bmod24\land x\equiv0\bmod5\implies x\equiv 25\bmod120$$ A continuación, añadir 120 repetidamente a 25 hasta obtener un número dentro del rango deseado, produciendo $x=145$.

Answer 2

Bien:

• Dado que el número es $0$ mod $5$, no tenemos que comprobar todos los números enteros en $[45,200)$, pero sólo los múltiplos de $5$: $45, 50, 55, \ldots$

• Pero también sabemos $x \mod{8} = 1$, lo que sucede en uno de cada 8 múltiplos de $5$. Por lo $x \mod 40 = 25$. Ahora sólo tenemos que comprobar $65, 105, 145, 185$.

• La tercera declaración, $x \mod 12 = 1$, es el mismo que$x \mod 3 = 1$$x \mod 4 = 1$. La última cosa que ya sabemos de $x \mod 8 = 1$. Así que combinamos los hechos $x \mod 40 = 25$ $x \mod 3 = 1$ conseguir $x \mod 120 = 25$. Ahora la única posibilidad es $145$.

Si a usted le gustaría saber la justificación matemática de estos pasos, es conocido como el teorema del resto Chino.

Answer 3

A partir de los últimos dos congruencias, $x\equiv 1 \pmod{24}$

A continuación, $x\equiv 1 \equiv 25 \equiv 49 \equiv...$

Sólo seguir adelante hasta encontrar algo congruente a $0 \pmod{5}$ que está dentro de su rango de interés.

O usted podría tomar nota de que $25$ obras, y de ese modo, se $25 + 120k$ para cualquier entero $k$.

Answer 4

Sugerencia: Utilice el Teorema del Resto Chino. En el caso de la aritmética modular, este teorema es la siguiente:

Teorema Suponga que tiene un sistema de congruencias: $$\begin{cases} x \equiv a_1 \ \mbox{mod} \ b_1 \\ \vdots \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \vdots \\ x\equiv a_n \ \mbox{mod} \ b_n \end{cases}$$ where $b_i$ are pairwise coprime. Then there is a unique $c$ such that $$x\equiv c \ \mbox{mod} \ \prod_{j=1}^nb_j$$

Hace esta sugerencia ayudar?