Una revisión "rápida" camino de la escritura número negativo (es decir $x$) $x \equiv a \pmod b$ $0 \leq a \lt b$

Question

Cual es el mejor método para la escritura de los números negativos en la forma de $a \bmod b$? (donde $a$ $b$ son enteros positivos)

Mientras que utilizando el teorema del resto Chino para calcular la solución de estos lineal de congruencias $$\begin{align}x &\equiv 2 \pmod 3 \\ x &\equiv 3 \pmod 4 \\ x &\equiv 1 \pmod 5\end{align}$$ as the solution I got $x = -109$, now I need to represent this result in the form of $\bmod b$,where $b=60$ (aquí),este caso es muy fácil, porque los números son muy pequeños.

En este me de mantener el control de los múltiplos de $60$ repetidamente y, a continuación, agregue $-109$ a la primera,$109$, en este caso $2\cdot 60 = 120$ y, a continuación, la adición de $-109$ obtenemos $11$,ahora podemos escribir $-109 \equiv 11 \bmod 60$... pero es que esta es la única manera? ya que si el número es grande, la comprobación de los múltiplos puede consumir mucho tiempo.

Por ejemplo aquí, el número es$-19177$, lo que debe expresarse en la forma $a \bmod 4900$, cómo manualmente y encontrar rápidamente "$a$" en tales casos (suponga que los números de arriba-a $6$ dígitos).

Answer 1

Si usted se siente incómodo dividiendo el número negativo $-109$$60$, hacer esto:

(i) Dividir el $109$$60$. El resto es $49$.

(ii) la respuesta es $60-49$.

Este procedimiento casi siempre funciona. El único momento en que no es cuando el resto de dividir su número positivo es $0$. Entonces la respuesta para el número negativo también debe ser $0$.

Ejemplo: Encontrar el resto al $-2011$ se divide por $60$.

(i) Dividir el $2011$$60$. El resto es $31$.

(ii) El resto al $-2011$ se divide por $60$ por lo tanto $60-31$, $29$.

Vamos a ver: $-2011=(60)(-34)+29$.

Nota: aquí Estamos encontrando el resto cuando un número negativo es dividido por una positiva. Por supuesto, si usted está interesado en la división de $-2011$$-60$, sólo el cambio de ambos signos, y proceder "normalmente".

Ejercicio: Probar que el procedimiento anterior es correcta. (Realmente no es difícil.)

El cálculo de Remainers: Supongamos que $a$ $m$ son positivas, y no demasiado grande. Queremos que el resto al $a$ se divide por $m$. Por ejemplo, supongamos $a=4000000$$m=2011$.

(a) se Dividen en función de la calculadora. Mi visor de la calculadora muestra $1989.0602$. (La calculadora sabe un par de dígitos adicionales pero se mantiene oculto.)

(b) Inmediatamente restar la parte entera de la respuesta, que es, $1989$. No copiar cualquier número y las llaves. Si es necesario, use la calculadora de "memoria". Llegué $0.0601691$. Observe que la calculadora acaba de revelar algunos dígitos, que había mantenido oculto. El último dígito no es digno de confianza.

(c) Inmediatamente multiplicar por $m$. Llegué $121.00006$.

(d) Encontrar el más cercano entero del resultado en (c). Si calculadoras siempre eran absolutamente exacto, el número en (c) sería un entero. La inexactitud es debido al error de redondeo. Ese error es pequeño, y encontrar el entero más cercano, elimina el error. A menudo, con bajita $a$, el paso (d) será necesaria, ya que el resultado del paso (c), en la pantalla se verá como un entero.

(e) llegamos a la conclusión de que nuestro resto es $121$. Todo el cálculo se toma un par de segundos, en su mayoría pasaron a teclear los números originales.

En una calculadora científica, el procedimiento debe ser confiable, al menos,$a=10^7$. Incluso funciona muy bien en un primitivo "tienda de comestibles" de la calculadora.

Si $a$ es bastante grande, decir $10^{13}$ o más allá, esta calculadora procedimiento se rompe. No podemos ni siquiera la entrada de todos los dígitos de $a$ en la calculadora! Sin embargo, hay muchos programas de cálculo disponibles, varias de ellas gratuitas, que calculan para una mayor precisión, o incluso "infinito" de precisión.

Answer 2

Para responder a su pregunta: dividir y conquistar.

Hacer la división entera! Es realmente muy sencillo, incluso con la mano, incluso con grandes números. Usted puede obtener una buena estimación bastante fácilmente, y a partir de ahí, en el peor de los casos.

En primer lugar, para encontrar el resto de $a$ modulo $b$ al $a$ es positivo, sólo divide $a$$b$.

Para escoger una al azar ejemplo yo estoy haciendo ahora, supongamos que usted desea encontrar el resto $a=5,831,273$ modulo $b=3,871$.

Claramente, $1000\lt \frac{a}{b} \lt 2000$; es más cercano a $2000$$1000$; multiplicando $3871\times 1500$ para la primera una primera aproximación, obtenemos $5,806,500$, que es bastante cerca. A continuación,$a\equiv a-5806500 = 24,773 \pmod{b}$, que todavía es demasiado grande. Ahora dividimos $24,773$$3871$: es en algún lugar entre el $6$ y $8$ ($3871$ se entre $3000$ y $4000$, $24,773$ es un poco más de $24,000$; esto es como la estimación de $24$ dividido por $3$ o $4$). Tratando de $7$,$3871\times 7 = 27097$, demasiado; ahora tenemos a $a\equiv 24,773 \equiv 24,773 - 27097 = -2324\pmod{b}$. Un paso más lo hace: agregar $3871$ conseguir $a\equiv 1547 \pmod{b}$. Esto lo hacía a mano, con una simple calculadora en mano, me gustaría simly calcular $\frac{a}{b}\approx 1506.4$ a averiguar que necesito para calcular $a - 1506b$ para obtener el resto.

Si $a$ es negativo, luego hacer lo mismo para $-a$; una vez que usted sabe que $-a\equiv c \pmod{b}$$0\leq c \lt |b|$, $a\equiv -c \equiv |b|-c\pmod{b}$ y listo, solo un paso más de positivos $a$.

Answer 3

En términos más simples, la forma de mostrar que $-109 \equiv 11 \pmod{60}$ es agregar $60$ $-109$repetidamente hasta obtener un resultado que no es negativo; que el resultado va a ser $-109 + 2 \cdot 60 = 11$.

Por supuesto, en la práctica, la adición repetida podría ser tedioso, así que utilizamos la multiplicación y la división como un acceso directo: divida $-109$$60$, y se obtiene aproximadamente $-1.8167$. Ronda que hacia abajo, y usted consigue $-2$. Multiplique eso por $60$ y restar de $-109$ conseguir $-109 - (-2 \cdot 60) = -109 + 2 \cdot 60 = 11$.

Por supuesto, que exactamente lo mismo de lo que usted podría hacer para reducir un número positivo grande modulo $60$ o, de hecho, el modulo de cualquier número. Sólo recuerde siempre ronda a la baja, si el resultado de la división es positivo o negativo.

Answer 4

En respuesta a la pregunta agregada: la manera de conseguir la $11$ es por la divisoria $-109$ por $60$; $11$ es el resto (el cociente es $-2$).

Answer 5

SUGERENCIA $\rm\qquad\ A\equiv\: a\ \ \ \Rightarrow\ \ \: {-}A\equiv\: -a\:,\ \ $ $\rm\:\ \ {-}a\ \equiv\ m-a\quad (mod\ m)$

Prueba de $\rm\ \ m\ |\ A-a\ \Rightarrow\ m\ |\: {-}A+a\:,\:$ $\rm\ m\ |\: {-}a-(m-a)\: =\: -m $

E. g. $\rm\ mod\ 10:\ \: 103\ \equiv\ 3\:\ \Rightarrow\ {-}103\ \equiv\: -3\ \equiv\: 10-3\ \equiv\ 7\ \ (mod\ 10)$

Nota también se $\rm\ 0 < a < m\ \Rightarrow\ 0 < m-a < m\:,\:$ es decir $\rm\ a\:$ reducción $\rm\:\Rightarrow\ m-a\ $ reducción $\rm\ (mod\ m)\:.$