5.7: Aritmética Modular

Última actualización
Guardar como PDF

Page ID: 112893

$ \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 utiliza solo un número fijo de resultados posibles en todos sus cómputos. Por ejemplo, solo hay 12 horas en la esfera de un reloj. Si la hora ahora son las 7, 20 horas después serán las 3; ¡y no decimos las 27 en punto! Este ejemplo explica por qué la aritmética modular es referida por algunos como aritmética de reloj.

Ejemplo$\PageIndex{1}\label{eg:modarith-01}$

Supongamos que la hora actual es 2:00 p.m. Escribe esto como 14:00. Sesenta y cinco horas después, serían las 79:00. Ya\[79 = 24\cdot3+7, \nonumber\] que serán las 7:00 o las 7 a.m.

ejercicio práctico$\PageIndex{1}\label{he:modarith-01}$

Designar Domingo, Lunes, Martes,..., Sábado como Día 0, 1, 2,..., 6. Si hoy es lunes, entonces es el Día 1. ¿Qué día de la semana será dentro de dos años? Supongamos que hay 365 días en un año.

En el ejemplo del reloj, esencialmente consideramos las 27 en punto igual que las 3 en punto. Ellos clave es, sólo nos interesa el resto cuando un valor se divide por 12.

Definición: módulo congruente

Dejar$n\geq2$ ser un entero fijo. Decimos los dos enteros$m_1$ y$m_2$ son módulo congruente, denotado\[m_1 \equiv m_2 \pmod{n} \nonumber\] si y sólo si$n\mid (m_1-m_2)$. El entero$n$ se llama el módulo de la congruencia.

¿Qué tiene que ver esta noción de congruencia con los restos? El siguiente resultado describe su conexión.

Teorema$\PageIndex{1}\label{thm:samer}$

Dejar$n\geq2$ ser un entero fijo. Para dos enteros cualesquiera$m_1$ y$m_2$,\[m_1\equiv m_2 \mbox{ (mod~$n$)} \quad\Leftrightarrow\quad m_1\bmod n = m_2\bmod n. \nonumber\]

Observación

No confundas las dos notaciones. La notación “(mod$n$)” después$m_1\equiv m_2$ indica una relación de congruencia, en la que “mod$n$” están encerrados por un par de paréntesis, y la notación se coloca al final de la congruencia. En contraste, el “mod” entre$m_1$ y$n$, sin paréntesis, es una operación binaria que arroja el resto cuando$m_1$ se divide por$n$.

Prueba

($\Rightarrow$) Asumir$m_1\equiv m_2$ (mod$n$). La definición de congruencia implica que tenemos$n\mid(m_1-m_2)$. De ahí,\[m_1-m_2 = nq \nonumber\] para algún entero$q$. Vamos$m_1=nq_1+r_1$ y$m_2=nq_2+r_2$ para algunos enteros$q_1, q_2, r_1, r_2$, tal que$0\leq r_1,r_2<n$. Entonces\[nq = m_1-m_2 = n(q_1-q_2)+r_1-r_2. \nonumber\] Desde$r_1-r_2=n(q-q_1+q_2)$, concluimos que$n\mid r_1-r_2$. Sin embargo, eso$0\leq r_1,r_2<n$ implica$|r_1-r_2|<n$. Por lo tanto, debemos tener$r_1-r_2=0$, o$r_1=r_2$. De ello se deduce que$m_1\bmod n = m_2\bmod n$.

($\Leftarrow$) Asumir$m_1\bmod n = m_2\bmod n$. Según el Algoritmo de División, el resto en una división entera es único. Así,$m_1=nq_1+r$ y$m_2=nq_2+r$ para algunos enteros$q_1, q_2, r$ tales que$0\leq r<n$. Entonces\[m_1-m_2 = (nq_1+r)-(nq_2+r) = n(q_1-q_2). \nonumber\] Por lo tanto,$n\mid(m_1-m_2)$.

Corolario$\PageIndex{2}\label{cor:mod0div}$

Dejar$n\geq2$ ser un entero fijo. Entonces\[a\equiv0 \pmod{n} \quad\Leftrightarrow\quad n\mid a. \nonumber\]

Teorema 5.7.1 nos dice$m_1\equiv m_2$ (mod$n$) si y solo si$m_1$ y$m_2$ comparten el mismo resto cuando se dividen por$n$. Dado cualquier entero$m$,\[m\bmod n \in\{0,1,2,\ldots,n-1\}. \nonumber\] llamamos a estos valores el módulo de residuos. En aritmética modular, cuando decimos “módulo reducido”, nos referimos a cualquier resultado que obtengamos, lo dividimos por$n$, y reportamos solo el residuo no negativo más pequeño posible.

El siguiente teorema es fundamental para la aritmética modular.

Teorema$\PageIndex{3}\label{thm:modthm}$

Dejar$n\geq2$ ser un entero fijo. Si$a\equiv b$ (mod$n$) y$c\equiv d$ (mod$n$), entonces\[\begin{array}{rcll} a+c &\equiv& b+d & \pmod{n}, \\ ac &\equiv& bd & \pmod{n}. \end{array} \nonumber\]

Prueba: Asumir$a\equiv b$ (mod$n$) y$c\equiv d$ (mod$n$). Entonces$n\mid (a-b)$ y$n\mid(c-d)$. Podemos escribir\[a-b = ns, \qquad\mbox{and}\qquad c-d = nt \nonumber\] para algunos enteros$s$ y$t$. En consecuencia,\[(a+c)-(b+d) = (a-b)+(c-d) = ns+nt = n(s+t), \nonumber\] donde$s+t$ es un entero. Esto demuestra que$a+c\equiv b+d$ (mod$n$). También tenemos\[ac-bd = (b+ns)(d+nt)-bd = bnt+nsd+n^2st = n(bt+sd+nst), \nonumber\] donde$bt+sd+nst$ es un entero. Así,$n\mid (ac-bd)$, lo que significa$ac\equiv bd$ (mod$n$).

Debido al Teorema 5.7.3, podemos sumar o multiplicar un entero a ambos lados de una congruencia sin alterar las congruencias.

Ejemplo$\PageIndex{2}\label{eg:modarith-02}$

Podemos usar la resta para reducir 2370 módulo 11. Cualquier múltiplo de 11 es congruente a 0 módulo 11. Entonces tenemos, por ejemplo,\[2370\equiv 2370 \pmod{11}, \qquad\mbox{and}\qquad 0\equiv-2200 \pmod{11}. \nonumber\] Aplicando el Teorema 5.7.3, obtenemos\[2370 \equiv 2370-2200 = 170 \pmod{11}. \nonumber\] Lo que esto significa es: podemos seguir restando múltiplos apropiados de$n$ desde$m$ hasta que la respuesta esté entre 0 y$n-1$, inclusive. No importa qué múltiplo de 11 uses. El punto es, elegir uno que se le ocurra rápidamente, y siga repitiendo el proceso. Continuando con esta moda, encontramos\[170 \equiv 170-110 = 60 \pmod{11}. \nonumber\] Desde$60-55=5$, determinamos que$2370\equiv5$ (mod 11).

ejercicio práctico$\PageIndex{2}\label{he:modarith-02}$

Reducir 12457 al residuo no negativo más pequeño módulo 17.

Ejemplo$\PageIndex{3}\label{eg:modarith-03}$

De manera similar, si$m$ es negativo, podemos seguir sumando múltiplos de$n$ al mismo hasta que la respuesta sea positiva. Por ejemplo,\[-278 \equiv -278+300 = 52 \pmod{11}. \nonumber\] es obvio que$52\equiv52-44=8$ (mod 11). Así,$-278\equiv8$ (mod 11).

ejercicio práctico$\PageIndex{3}\label{he:modarith-03}$

Evaluar$-3275\bmod11$. Esto es lo mismo que reducir$-3275$ al residuo no negativo más pequeño módulo 11.

En un cómputo complicado, reduce el resultado de cada paso intermedio antes de continuar con el siguiente paso. Esto simplificará enormemente el cómputo. Para acelerar aún más el cálculo, podemos usar valores negativos en el paso intermedio. Sin embargo, la respuesta final debe estar entre 0 y$n-1$.

Ejemplo$\PageIndex{4}\label{eg:modarith-04}$

Reducir$37^2\cdot41-53\cdot2$ módulo 7.

Solución: Toma nota que\[\begin{array}{lclcr} 37 &\equiv& 37-35 &=& 2 \pmod{7}, \\ 41 &\equiv& 41-42 &=& -1 \pmod{7}, \\ 53 &\equiv& 53-49 &=& 4 \pmod{7}. \end{array} \nonumber\] Por lo tanto,\[37^2\cdot41-53\cdot2 \equiv 2^2\cdot(-1)-4\cdot2 = -12 \pmod{7}. \nonumber\] Nosotros determinamos que$37^2\cdot41-53\cdot2 \equiv 2$ (mod 7).

ejercicio práctico$\PageIndex{4}\label{he:modarith-04}$

Evaluar$56^3\cdot22\cdot17-35\cdot481$ (mod 9).

El cálculo tedioso puede llegar a ser bastante simple bajo la aritmética modular.

Ejemplo$\PageIndex{5}\label{eg:modarith-05}$

Mostrar que si un entero no$n$ es divisible por 3, entonces siempre$n^2-1$ es divisible por 3. Equivalentemente, mostrar que si un entero no$n$ es divisible por 3, entonces$n^2-1\equiv0$ (mod 3).

Solución 1

Dejar$n$ ser un entero no divisible por 3, entonces ya sea$n\equiv1$ (mod 3), o$n\equiv2$ (mod 3).

Caso 1. Si$n\equiv1$ (mod 3), entonces\[n^2-1 \equiv 1^2-1 = 0 \pmod{3}. \nonumber\]

Caso 2. Si$n\equiv2$ (mod 3), entonces\[n^2-1 \equiv 2^2-1 = 3 \equiv 0 \pmod{3}. \nonumber\]

En ambos casos, hemos encontrado que$n^2-1$ es divisible por 3.

Solución 2: Dejar$n$ ser un entero no divisible por 3, entonces ya sea$n\equiv1$ (mod 3), o$n\equiv2$ (mod 3). Esto equivale a decir$n\equiv\pm1$ (mod 3). Entonces\[n^2-1 \equiv (\pm1)^2-1 = 1-1 = 0 \pmod{3}, \nonumber\] que significa$n^2-1$ es divisible por 3.

ejercicio práctico$\PageIndex{5}\label{he:modarith-05}$

Utilice la aritmética modular para mostrar eso$5\mid(n^5-n)$ para cualquier entero$n$.

ejercicio práctico$\PageIndex{6}$

Utilice la aritmética modular para mostrar que$n(n+1)(2n+1)$ es divisible por 6 para cualquier entero$n$.

Elevar un entero a una potencia grande plantea un problema grave. No podemos simplemente elevar un entero a una potencia grande, porque el resultado podría ser tan grande que la calculadora o computadora tiene que convertirlo en un valor decimal y comenzar a usar notación científica para manejarlo. En consecuencia, la respuesta no será exacta.

Una mejor solución es reducir los resultados intermedios módulo$n$ después de cada multiplicación. Esto producirá un resultado preciso, pero tardará mucho en terminar si la potencia es enorme. Afortunadamente, hay una manera mucho más rápida de realizar exponenciación que utiliza un menor número de multiplicaciones.

Ejemplo$\PageIndex{6}\label{eg:modarith-06}$

Evaluar$5^{29}$ (mod 11).

Solución

Primero, escribe el exponente 29 como una suma de potencias de 2. Podemos hacerlo por inspección. Empezar con el poder más alto de 2 que sea menor o igual a 29, y luego trabajar con lo que quede en la suma: Esencialmente\[29 = 16+13 = 16+8+5 = 16+8+4+1. \nonumber\] estamos expresando 29 en base 2. Ya podemos escribir

\[5^{29} = 5^{16+8+4+1} = 5^{16}\cdot5^8\cdot5^4\cdot5. \nonumber\]

Estas potencias de 5 se pueden obtener por medio de cuadratura repetida:

\[\begin{aligned} 5^1 &=& 5, \\ 5^2 &=& 5^2, \\ 5^4 &=& (5^2)^2, \\ 5^8 &=& (5^4)^2, \\ 5^{16} &=& (5^8)^2, \\ \vdots\hfil && \hfil\vdots \end{aligned}\label{eg:repsq}\]

La iteración es simple: cada nueva potencia se obtiene al cuadrar la potencia anterior. Ya que estamos haciendo aritmética modular, queremos reducir cada resultado intermedio módulo 11: De\[ \begin{array}{lclcrcrr@{\quad\pmod{11}}} 5 &= & 5 & & & & & \text{(mod 11)} \\ 5^2 &= & 25 &\equiv& 3 & & & \text{(mod 11)} \\ 5^4 &\equiv& 3^2 &= & 9 &=& -2 & \text{(mod 11)} \\ 5^8 &\equiv& 9^2 &\equiv&(-2)^2 &=& 4 & \text{(mod 11)} \\ 5^{16} &\equiv& 4^2 &= & 16&\equiv& 5 & \text{(mod 11)} \end{array} \nonumber\] ello se deduce que\[5^{29} = 5^{16}\cdot5^8\cdot5^4\cdot5 \equiv 5\cdot4\cdot(-2)\cdot5 \pmod{11}. \nonumber\] Después de la simplificación, nos encontramos con$5^{29}\equiv9$ (mod 11).

ejercicio práctico$\PageIndex{7}\label{he:modarith-06}$

Use cuadratura repetida para encontrar$7^{45}$ (mod 11).

ejercicio práctico$\PageIndex{8}\label{he:modarith-07}$

Use cuadratura repetida para evaluar$9^{58}$ (mod 23).

En la aritmética modular, básicamente estamos trabajando solo con los restos. El conjunto de enteros$\{0,1,2,\ldots,n-1\}$ se llama el conjunto de enteros módulo, y se denota por$\mathbb{Z}_n$ (pronunciado como Z mod$n$). Además, definimos dos nuevas operaciones aritméticas sobre$\mathbb{Z}_n$. Se les llama “suma” y “multiplicación” porque funcionan como la suma y multiplicación habituales, excepto que tenemos que aplicar la operación mod a los resultados. Para distinguirlos de la suma y multiplicación habituales, los denotamos por$\oplus$ y$\odot$, y se denominan “círculo más” y “punto circular”, respectivamente. Formalmente,

\[a\oplus b = (a+b) \bmod n, \qquad\mbox{and}\qquad a\odot b = (a\cdot b)\bmod n. \nonumber\]

A continuación se$\mathbb{Z}_6$ enumeran las tablas de suma y multiplicación para.

\[\begin{array}{|c||*{6}{c|}}\hline\oplus & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ \hline 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ \hline 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ \hline 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ \hline 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \hline \end{array} \qquad\qquad \begin{array}{|c||*{6}{c|}}\hline\odot & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ \hline 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ \hline 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ \hline 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \hline \end{array} \nonumber\]

Compárelos con las tablas para$\mathbb{Z}_7$.

\[\begin{array}{|c||*{7}{c|}}\hline\oplus & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 6 & 0 \\ \hline 2 & 2 & 3 & 4 & 5 & 6 & 0 & 1 \\ \hline 3 & 3 & 4 & 5 & 6 & 0 & 1 & 2 \\ \hline 4 & 4 & 5 & 6 & 0 & 1 & 2 & 3 \\ \hline 5 & 5 & 6 & 0 & 1 & 2 & 3 & 4 \\ \hline 6 & 6 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline \end{array} \qquad\qquad \begin{array}{|c||*{7}{c|}} \hline\odot & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 2 & 0 & 2 & 4 & 6 & 1 & 3 & 5 \\ \hline 3 & 0 & 3 & 6 & 2 & 5 & 1 & 4 \\ \hline 4 & 0 & 4 & 1 & 5 & 2 & 6 & 3 \\ \hline 5 & 0 & 5 & 3 & 1 & 6 & 4 & 2 \\ \hline 6 & 0 & 6 & 5 & 4 & 3 & 2 & 1 \\ \hline \end{array} \nonumber\]

En ambas tablas de adición, todos los valores posibles aparecen en cada fila y en cada columna. Lo mismo ocurre en las filas distintas de cero y en las columnas distintas de cero en la tabla de multiplicación para$\mathbb{Z}_7$. Sin embargo, algunas de las filas de la tabla de multiplicación para$\mathbb{Z}_6$ no contienen todos los enteros en$\mathbb{Z}_6$. Esto sugiere que las propiedades algebraicas de$\mathbb{Z}_n$ dependen del valor de$n$.

De hecho, siempre que$n$ sea primo, las tablas de suma y multiplicación de$\mathbb{Z}_n$ se comportan como las de$\mathbb{Z}_7$. Se puede demostrar que cuando$n$ es primo,$\mathbb{Z}_n$ tiene las siguientes propiedades.

Ambos$\oplus$ y$\odot$ son conmutativos, significado\[a\oplus b = b\oplus a \qquad\mbox{and}\qquad a\odot b = b\odot a \nonumber\] para todos$a,b\in\mathbb{Z}_n$.
Ambos$\oplus$ y$\odot$ son asociativos, es decir, eso\[(a\oplus b)\oplus c = a\oplus(b\oplus c) \qquad\mbox{and}\qquad (a\odot b)\odot c = a\odot(b\odot c) \nonumber\] para todos$a,b,c\in\mathbb{Z}_n$.
Las operaciones$\oplus$ y$\odot$ satisfacer las leyes distributivas\[a\odot(b\oplus c) = (a\odot b) \oplus (a\odot c) \qquad\mbox{and}\qquad (b\oplus c)\odot a = (b\odot a) \oplus (c\odot a) \nonumber\] para todos$a,b,c\in\mathbb{Z}_n$.
El entero 0 es la identidad aditiva, lo que significa que$a\oplus 0 = 0\oplus a = a$ para todos$a\in\mathbb{Z}_n$.
Para cada$a\in\mathbb{Z}_n$, existe un entero único$a'\in\mathbb{Z}_n$ tal que$a\oplus a'=0$. Este entero$a'$ se llama el inverso aditivo o negativo de$a$, y se denota por$-a$.
El entero 1 es la identidad multiplicativa, lo que significa que$a\odot 1 = 1\odot a = a$ para todos$a\in\mathbb{Z}_n$.
Por cada entero$a\in\mathbb{Z}_n^*$ (por lo tanto,$a\neq0$), existe un entero único distinto de cero$a'\in\mathbb{Z}_n$ tal que$a\odot a'=1$. Este entero$a'$ se llama el inverso multiplicativo o recíproco de$a$, y se denota por$a^{-1}$.

Ejemplo$\PageIndex{7}\label{eg:modarith-07}$

De las tablas anteriores, solo 1 y 5 tienen inversas multiplicativas en$\mathbb{Z}_6$. De hecho,\[1\cdot1 = 1 \qquad\mbox{and}\qquad 5\cdot5 = 1 \qquad\mbox{in $\mathbb{Z}_6$} \nonumber\] implica eso$1^{-1}=1$, y$5^{-1}=5$ en$\mathbb{Z}_6$. Por otro lado, cada entero distinto de cero en$\mathbb{Z}_7$ tiene una inversa multiplicativa:\[1^{-1}=1, \quad 2^{-2}=4, \quad 3^{-1}=5, \quad 4^{-1}=2, \quad 5^{-1}=3, \quad\mbox{and}\quad 6^{-1}=6. \nonumber\] Asegúrese de verificar estas inversas.

En general, dado cualquier conjunto de números, podemos definir operaciones aritméticas de la forma que queramos, siempre que obedezcan ciertas reglas. Esto produce una estructura algebraica. Por ejemplo, llamamos a un conjunto de elementos$S$ con dos operaciones binarias denotadas$\oplus$ y$\odot$ un campo, y escribir$\langle S,\oplus,\odot\rangle$ o$(S,\oplus,\odot)$, si satisface las siete propiedades enumeradas anteriormente. Ambos$\langle\mathbb{R},+,\cdot\,\rangle$ y$\langle\mathbb{Q},+,\cdot\,\rangle$ son campos, pero no lo$\langle\mathbb{Z},+,\cdot\,\rangle$ es, porque multiplicativa inversa de$a$ no existe si$a\neq\pm1$.

Teorema$\PageIndex{4}$

La estructura algebraica$\langle\mathbb{Z}_n,\oplus,\odot\rangle$ es un campo si y solo si$n$ es primo.

Prueba: La verificación de la mayoría de las propiedades es bastante sencilla, con la excepción de la existencia del inverso multiplicativo, que aquí probaremos. Dado que$n$ es un primo, cualquiera$a\in\mathbb{Z}^*$ debe ser relativamente primo para$n$. De ahí,\[as+nt = 1 \nonumber\] para algunos enteros$s$ y$t$. Modulo$n$, encontramos$nt=0$, de ahí,$as+nt=1$ se convierte en\[as = 1. \nonumber\] Therefore$a^{-1} \equiv s$ (mod$n$).

El teorema nos dice que si$n$ es primo, entonces$\mathbb{Z}_n$ es un campo, por lo tanto, cada entero distinto de cero tiene una inversa multiplicativa.

Ejemplo$\PageIndex{8}\label{eg:modarith-08}$

Determinar$7^{-1}$ (mod 29).

Solución: Queremos encontrar un número$a'$ tal que$7a'\equiv1$ (mod 29). Tenga en cuenta que$\gcd(7,29)=1$. Usando algoritmo euclidiano extendido, encontramos\[7(-4)+29\cdot1 = 1. \nonumber\] Desde$29\cdot1\equiv0$ (mod 29), después de reducir el módulo 29, encontramos\[7(-4) \equiv 1 \pmod{29}. \nonumber\] Esto implica que$7^{-1}\equiv-4\equiv 25$ (mod 29).

Cuando$n$ es compuesto, no$\mathbb{Z}_n$ es un campo. Entonces no todos los enteros distintos de cero en él tienen un inverso multiplicativo. Por supuesto, algunos enteros especiales distintos de cero aún pueden tener inversos multiplicativos.

ejercicio práctico$\PageIndex{9}\label{he:modarith-08}$

Determinar$8^{-1}$ (mod 45).

Ejemplo$\PageIndex{9}\label{eg:modarith-09}$

Resuelve la ecuación$7x-3=5$ sobre$\mathbb{Z}_{29}$.

Solución: De$7x-3=5$, encontramos$7x=8$. Recordemos que lo que realmente significa esta ecuación es\[7x \equiv 8 \pmod{29}. \nonumber\] La respuesta no es$x=\frac{8}{7}$, porque$\mathbb{Z}_{29}$ solo contiene enteros como sus elementos. Esto es lo que debemos hacer: multiplicar$7^{-1}$ a ambos lados de la congruencia:\[7^{-1}\cdot 7x \equiv 7^{-1}\cdot8 \pmod{29}. \nonumber\] Desde$7^{-1}\cdot7\equiv1$ (mod 29), ahora tenemos\[x\equiv 7^{-1}\cdot8 \pmod{29}. \nonumber\] En cierto modo, usamos la inversa multiplicativa para simular la división. En este caso,$7^{-1}\equiv7$ (mod 29). De ahí,$x\equiv7\cdot8\equiv26$ (mod 29).

ejercicio práctico$\PageIndex{10}\label{he:modarith-09}$

Resuelve la ecuación$8x+23=12$ sobre$\mathbb{Z}_{45}$.

Ejemplo$\PageIndex{10}\label{eg:modarith-10}$

$3^{-1}$Explique por qué no existe en$\mathbb{Z}_{24}$.

Solución: Supongamos que$3^{-1}$ existe en$\mathbb{Z}_{24}$, digamos,$3^{-1}\equiv z$ (mod 24). Esto significa$3z\equiv1$ (mod 24). De ahí,\[3z = 24q+1 \nonumber\] para algún entero$q$. Esto a su vez implica aquello\[1 = 3z-24q = 3(z-8q), \nonumber\] que es claramente imposible porque$z-8q$ es un entero. Esta contradicción demuestra que$3^{-1}$ no existe en$\mathbb{Z}_{24}$.

Ambos$\mathbb{R}$ y$\mathbb{Q}$ son campos infinitos, mientras que$\mathbb{Z}_n$ es un campo finito cuando$n$ es primo. El siguiente resultado es realmente asombroso, porque proclama que el número de elementos en cualquier campo finito (uno con finitamente muchos elementos) debe ser el poder de un determinado primo. Desafortunadamente, no podemos demostrarlo aquí, porque está más allá del alcance de este curso.

Teorema$\PageIndex{5}$

Existe un campo finito de$n$ elementos si y solo si$n$ es el poder de un primo.

Modular aritmética módulo$n$ utiliza la operación mod para reducir las respuestas de todos los cómputos a dentro de 0 a través de$n-1$.
En lugar de esperar hasta que obtengamos la respuesta final antes de reducirla módulo$n$, es más fácil reducir cada módulo de resultado inmediato$n$ antes de pasar al siguiente paso en el cálculo.
Podemos usar enteros negativos en los pasos intermedios.
El conjunto de enteros$\{0,1,2,\ldots,n-1\}$, junto con el módulo aritmético modular$n$, se denota como$\mathbb{Z}_n$.
Para$a\cdot a'\equiv1$ (mod$n$), decimos que$a'$ es el inverso multiplicativo de$a$, y lo denotamos$a^{-1}$.
Para algunos$a\in\mathbb{Z}_n$, la inversa multiplicativa$a^{-1}$ puede no existir. Si existe, podemos usarlo para simular la división.

Ejercicio$\PageIndex{1}\label{ex:modarith-01}$

Construir las tablas de suma y multiplicación para$\mathbb{Z}_8$. ¿Qué elementos distintos de cero tienen inversos multiplicativos (reciprocales)? ¿Cuáles son sus inversos multiplicativos?

Ejercicio$\PageIndex{2}\label{ex:modarith-02}$

Repite el último problema con$\mathbb{Z}_9$.

Ejercicio$\PageIndex{3}\label{ex:modarith-03}$

Encuentra la suma y producto de 1053 y 1761 en$\mathbb{Z}_{17}$.

Ejercicio$\PageIndex{4}\label{ex:modarith-04}$

Algunos de los resultados que derivamos anteriormente se pueden probar fácilmente a través de la aritmética modular. Por ejemplo, mostrar que si un entero no$n$ es divisible por 3, entonces$n\equiv\pm1$ (mod 3). ¿Qué puedes decir sobre$n^2$ (mod 3)? Por lo tanto, ¿qué forma debe$n^2$ tomar?

Ejercicio$\PageIndex{5}\label{ex:modarith-05}$

Mostrar que ningún entero de la forma$m^2+1$ es un múltiplo de 7.

Pista: ¿Cuáles son los valores posibles de$m$ (mod 7)? Compare esto con el último problema.

Ejercicio$\PageIndex{6}\label{ex:modarith-06}$

¿Cuáles son los valores posibles de$m$ (mod 13) tal que$m^2+1$ es un múltiplo de 13?

Pista: Calcular$m^2+1$ (mod 13) para cada valor de$m$.

Ejercicio$\PageIndex{7}\label{ex:modarith-07}$

Encuentra el valor de$4^{45}$ in$\mathbb{Z}_{11}$

utilizando el hecho de que$45=3\cdot3\cdot5$
usando cuadratura repetida

Ejercicio$\PageIndex{8}\label{ex:modarith-08}$

Use cuadratura repetida para evaluar$5^{23}$ (mod 11).

Ejercicio$\PageIndex{9}\label{ex:modarith-09}$

Resuelve estas ecuaciones

$2x+ 5=10$sobre$\mathbb{Z}_{13}$
$37x+28=25$sobre$\mathbb{Z}_{57}$
$12-24x=15$sobre$\mathbb{Z}_{35}$

Ejercicio$\PageIndex{10}\label{ex:modarith-10}$

Dejar$p$ y$q$ ser primos impares.

Demostrar que$p$ toma la forma de cualquiera$6k+1$ o$6k+5$.

Pista: Primero, explique por qué ser extraño restringe$p$ a la forma de$6k+1$,$6k+3$, y$6k+5$. A continuación, argumenta por qué$p\neq 6k+3$.

¿A qué podría$p$ ser congruente, módulo 24?
Demuéstralo si$p\geq q\geq5$, entonces$24\mid (p^2-q^2)$.

Pista: ¿Cuáles son los valores posibles de$p^2$ y$q^2$ módulo 24?

Ejercicio$\PageIndex{11}\label{ex:modarith-11}$

Usa la aritmética modular para probar que, si$n$ es un entero no divisible por 5, entonces$n^4-1$ es divisible por 5.

Ejercicio$\PageIndex{12}\label{ex:modarith-12}$

Utilice la aritmética modular para probar eso$8\mid(5^{2n}+7)$ para cualquier entero$n\geq0$.

Ejercicio$\PageIndex{13}\label{ex:modarith-13}$

Utilice la aritmética modular para probar eso$3\mid(2^{2n}-1)$ para cualquier entero$n\geq0$.

Ejercicio$\PageIndex{14}\label{ex:modarith-14}$

Utilice la aritmética modular para probar eso$5\mid(3^{3n+1}+2^{n+1})$ para cualquier entero$n\geq0$.