¿Cuáles son las propiedades del módulo

Question

Es el módulo $\%$ conmutativa, asociativa, o etc? Por ejemplo, puedo hacer esto:

Aquí es una ecuación que estoy usando: $$h_1 = (a \cdot a \cdot c_1 + a \cdot c_2 + c_3) \bmod a$$

Pongo a un lado el módulo, por lo que fácilmente se puede reorganizar la ecuación: $$a \cdot c_2 + c_3 = h_1 - a \cdot a \cdot c_1$$

He aquí otra ecuación: $$h_2 = (a\cdot a \cdot c_2 + a \cdot c_3 + c_4) \bmod a = ( a \cdot (a \cdot c_2 + c_3) + c_4 ) \bmod a$$

Esto es lo que me sale después de la sustitución: $$h_2 = (a \cdot ( h_1 - a \cdot a \cdot c_1) + c_4 ) \bmod a$$

Problemas?

Answer 1

El módulo de operación como usted tiene ciertamente no es conmutativa: la salida es dictada por el segundo término. E. g., $ 7\% 3 = 1$ (porque el resto cuando se divide $7$$3$$1$), pero $3\%7 = 3$ (porque el resto cuando se divide $3$$7$$3$).

Tampoco es asociativa: $(7\%5)\%3 = 2\%3 = 2$, pero $7\%(5\%3) = 7\%2 = 1$.

Realmente no distribuir, pero no tiene una propiedad similar. Es decir, $$(x+y)\% a = \Bigl((x\%a)+(y\%a)\Bigr) \%a.$$ (Por ejemplo, $(2+2)\%3 = 4\%3 = 1$, pero $(2\%3)+(2\%3) = 2+2 = 4$, por lo que es necesario el módulo de operación de nuevo para conseguir la igualdad.

Usted puede hacer las sustituciones. Si $x\%a = b$, entonces para cualquier expresión polinómica con coeficientes enteros, $p(x)$$x$,$p(x)\%a = p(b)\%a$.

El módulo de operación es torpe en general. Lo que usted realmente desea utilizar está congruencias (también conocido como la aritmética modular), que son mucho mejor educados y permiten mucha (pero no todas) de las habituales manipulaciones a las que estamos acostumbrados.

Answer 2

Sí. Suponga $\rm\ \ h_1 = (a^2 c_1 + a c_2 + c_3\ mod\ a)\ $

entonces $\rm\: mod\ a\!:\:$ $\rm\: h_1 \equiv a^2 c_1 + a c_2 + c_3\:$

por lo tanto $\rm\ \ \ a c_2 + c_3\equiv h_1 - a^2 c_1\:$

por lo tanto $\rm\ \ \ a(a c_2 + c_2) + c_4 \equiv a ( h_1 - a^2 c_1) + c_4$

por lo tanto $\rm\ \ \ ((a c_2 + c_2) + c_4\ mod\ a) = (( h_1 - a^2 c_1) + c_4\ mod\ a)$

En general, como aquí, es un inconveniente para realizar aritmética utilizando sólo las formas normales (como mínimo de equivalencia representantes de la clase). En su lugar, convertir a general de clases de equivalencia, el uso general de la aritmética modular y, si es necesario, volver a convertir a formas normales reps sólo al final de la computación. Por ejemplo, para calcular el $\rm\:1/2\:\ mod\:\ 2n\!+\!1\:$ es más fácil elegir cualquiera incluso rep $1,\:$ $\rm\:2n\!+\!2\equiv 1,\:$ por lo tanto $\rm\:1/2\equiv (2n\!+\!2)/2\equiv n\!+\!1.$

Este es familiar a partir de la fracción de la aritmética. Sería incómodo tener que hacer todo fracción aritmética sólo con fracciones en forma normal (= el más bajo de los términos). Por ejemplo, cuando la suma de fracciones es conveniente escala ellos tienen un denominador común, para luego hacer la suma de estos no-menor plazo de fracciones, entonces, si es necesario, normalizar el resultado a su mínima expresión.

La razón por la que la equivalencia de la clase de aritmética resulta más suave que la congruencia mod m no es sólo una relación de equivalencia, sino que es, además, una aritmética de la congruencia de la relación, es decir, que respeta las operaciones aritméticas. Esto implica que todos los de la aritmética de enteros leyes (estructura de anillo) se conservan en la aritmética modular. Por lo tanto podemos aplicar todos nuestros perfeccionado aritmética de la intuición cuando se realiza la congruencia aritmética, por ejemplo, el uso de identidades, tales como el teorema del binomio, diferencias de cuadrados de la factorización, etc.