5.1: Aritmética Modular

Última actualización
Guardar como PDF

Page ID: 111486

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

La Aritmética Modular se ocupa de cálculos que implican suma y multiplicación en\(\mathbb{Z}\) módulo\(b\), denotados por\(\mathbb{Z}_{b}\), es decir, cálculos con módulo de residuos\(b\) (Ver definición 1.6). Una forma común de ver esto es considerar los enteros\(x\) y\(y\) que difieren por un múltiplo de b como equivalentes (ver ejercicio 5.1). Escribimos\(x \sim y\). Se prueba entonces que la suma y multiplicación habituales está bien definida para estas clases de equivalencia. Esto se hace en el ejercicio 5.2.

Supongamos que se nos da una operación\(\ast\) sobre un conjunto\(G\) y que\((G, \ast)\) satisfaga ciertos requisitos -es decir, que se forma como grupo- que incluyen tener un elemento de identidad\(e\). El orden de un elemento\(g\) es el entero positivo más pequeño\(k\) tal que\(g \ast g \cdots g\), repetidos\(k\) veces y generalmente escrito\(g^k\), es igual\(e\). Se puede demostrar que los elementos\(\{e, g, g^2, g^{k-1}\}\) también forman un grupo. Para dar seguimiento a esto nos llevaría demasiado lejos un campo. Algunos detalles se dan en Capítulo??. La historia completa se puede encontrar en [10], [11], o [13].

En el caso que nos ocupa,\(\mathbb{Z}^b\), donde tenemos una estructura con dos operaciones, a saber, suma con elemento de identidad\(0\) y multiplicación con elemento de identidad\(1\). Por lo tanto, podríamos definir el orden de un elemento\(\mathbb{Z}^b\) con respecto a la suma y con respecto a la multiplicación. Como ejemplo, consideramos el elemento\(3\) en\(\mathbb{Z}^7\):

\[\begin{array}{ccc} {3+3+3+3+3+3+3 = _{7} 0}&{\mbox{and}}&{3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 = _{7} 1} \nonumber \end{array}\]

El primero da\(7\) como el orden aditivo de\(3\), y el segundo da\(6\) para el orden multiplicativo. Para nuestros propósitos actuales, sin embargo, es suficiente trabajar únicamente con la versión multiplicativa.

Definición 5.1

El orden de un módulo\(b\), escrito como\(\mbox{Ord}^{\times}_{b} (a)\), es el número positivo más pequeño\(k\) tal que\(a^{k} = _{b} 1\). (Si no existe tal\(k\), la orden es\(\infty\).)