5.6: Ejercicios

Ejercicio\(\PageIndex{1}\)

1. Vamos\(m > 0\). Demostrar que\(a = _{m} b\) es una relación de equivalencia sobre\(\mathbb{Z}\). (Utilice las definiciones 1.5 y 1.24.)
2. Describir las clases de equivalencia de\(\mathbb{Z}\) módulo\(6\). (¿A qué números\(\mathbb{Z}\) son equivalentes\(0\)? ¿Cuáles son equivalentes a\(1\)? Etcétera.)
3. Mostrar que las clases de equivalencia se identifican por su residuo, es decir:\(a \sim b\) si y solo si\(\mbox{Res}_{m} (a) = \mbox{Res}_{m} (b)\).

Nota: Si elegimos un elemento de cada clase de equivalencia, dicho elemento se llama un representante de esa clase. El menor represen- tativo no negativo de una clase de residuo en\(\mathbb{Z}_{m}\), se llama el menor residuo. La colección que consiste en el representante no negativo más pequeño de cada clase de residuos se denomina conjunto completo de menos residuos.

Ejercicio\(\PageIndex{2}\)

Este ejercicio se basa en el ejercicio 5.1. Denote el conjunto de clases de equivalencia de\(\mathbb{Z}\) módulo\(m\) por\(\mathbb{Z}_{m}\) (ver Definición 1.5). Demostrar que la suma y la multiplicación están bien definidas en\(\mathbb{Z}_{m}\), utilizando los siguientes pasos.

1. Si\(a = _{m} a′\) y\(b = _{m} b′\), entonces\(\mbox{Res}_{m} (a) + \mbox{Res}_{m} (b) = _{m} \mbox{Res}_{m} (a′) + \mbox{Res}_{m} (b′)\). (Pista: mostrar que\(a+b = c\) si y solo si\(a+b = _{m} c\). En otras palabras: el módulo suma\(m\) sólo depende\(\mbox{Res}_{m} (a)\)\(\mbox{Res}_{m} (b)\) y no de qué representante en la clase (ver ejercicio 5.1) con el que empezaste.)
2. Haz lo mismo para la multiplicación.

Ejercicio\(\PageIndex{3}\)

Vamos a\(n = \sum^{k}_{i=1} a_{i} 10^{i}\) donde\(a_{i} \in \{0, 1, 2, \cdots ,9\}\).

1. \(10^{k} = _{3} 1\)Demuéstralo para todos\(k \ge 0\). (Pista: use el ejercicio 5.2.)
2. \(n = 3 \sum^{k}_{i=1} a_{i}\)Demuéstralo.
3. Demostrar que esto implica que\(n\) es divisible por\(3\) si y solo la suma de sus dígitos es divisible por\(3\).

Ejercicio\(\PageIndex{4}\)

Vamos a\(n = \sum^{k}_{i=1} a_{i} 10^{i}\) donde\(a_{i} \in \{0, 1, 2, \cdots ,9\}\). Seguir la estrategia en el ejercicio 5.3 para acreditar los siguientes hechos.

1. Mostrar que\(n\) es divisible por\(5\) si y solo si\(a_{0}\) es. (Pista:\(n = _{5} a_{0}\) Demuéstralo.)
2. Mostrar que\(n\) es divisible por\(2\) si y solo si\(a_{0}\) es.
3. Mostrar que\(n\) es divisible por\(9\) si y solo si\(\sum^{k}_{i=1} a_{i}\) es.
4. Mostrar que\(n\) es divisible por\(11\) si y solo si\(\sum^{k}_{i=1} (-1)^{i} a_{i}\) es.
5. Encuentra el criterio de divisibilidad por\(4\).
6. Encuentra el criterio de divisibilidad por\(7\). (Pista: ¡este es un criterio más complicado!)

Ejercicio\(\PageIndex{5}\)

1. Lista\((n-1)!\) mod\(n\) para\(n \in \{2, \cdots, 16\}\).
2. ¿Dónde falla la prueba de la primera parte del teorema de Wilson en el caso de\(n = 16\)?
3. ¿Se sostiene el teorema de Wilson\(p = 2\)? ¡Explique!

Ejercicio\(\PageIndex{6}\)

Denotar por\(\{x_{i}\}\) el conjunto reducido de residuos módulo\(16\). Si se mantiene el razonamiento similar al del teorema de Wilson, eso se espera\(\prod_{i} x_{i} = _{16} -1\).

1. Cómputos\(\prod_{i} x_{i}\).
2. ¿Cómo falla el razonamiento en el teorema de Wilson? (Pista: ver lema 5.17.)
3. Listar el producto del conjunto reducido de residuos módulo\(n\) para\(n \in \{2, \cdots ,16\}\).

Ejercicio\(\PageIndex{7}\)

1. Para\(i\) dentro\(\{1,2, \cdots 11\}\) y\(j\) en\(\{2,3, \cdots 11\}\), hacer una tabla de\(\mbox{Ord}^{\times}_{j} (i)\),\(i\) variando horizontalmente. Después de la jésima columna, escribe\(\varphi (j)\).
2. Enumere el\(i\) módulo de raíces primitivas\(j\) para\(i\) y\(j\) como en (a). (Pista: las raíces primitivas más pequeñas módulo\(j\) son:\(\{1,2,3,2,5,3, \emptyset, 2,3,2\}\).)

Ejercicio\(\PageIndex{8}\)

1. Determinar el periodo de expansión decimal de los siguientes números:\(100/13, 13/77\), y\(1/17\) mediante división larga.
2. Utilice la Proposición 5.6 para determinar el periodo.
3. Comprobar que este periodo sea igual a un divisor de\(\varphi (n)\).
4. Las mismas preguntas para expansiones en base en\(2\) lugar de base\(10\).

Ejercicio\(\PageIndex{9}\)

1. Calcular\(2^{n-1}\) mod\(n\) para\(n\) impar in\(\{3 \dots 40\}\).
2. ¿Hay algún pseudo-primo en la lista?

Ejercicio\(\PageIndex{10}\)

Supongamos que\(n\) es un pseudoprimo a la base\(2\).

1. \(2^{n}-2 = _{n} 0\)Demuéstralo.
2. Mostrar desde (a) eso\(n | M_{n}-1\). (Ver Definición 5.11.)
3. Use Lema 5.12 para demostrar que (b) implica eso\(M_{n}| 2^{M_{n}-1}-1\).
4. Concluir de (c) que si\(n\) es un pseudoprimo en base\(2\), así es\(M_{n}\).

Ejercicio\(\PageIndex{11}\)

Mostramos que el número 5-ésimo de Fermat,\(2^{32}+1\), es un número compuesto.

1. \(2^{4} = _{641} -5^4\)Demuéstralo. (Pista: agregar\(2^4\) y\(5^4\).)
2. \(2^{75} = _{641} -1\)Demuéstralo.
3. \(2^{32} +1 = (2^{7})^{4} 2^{4}+1 = _{641} 0\)Demuéstralo.
4. Concluir que\(F_{5}\) es divisible por\(641\).

Ejercicio\(\PageIndex{12}\)

1. Cómputos\(\varphi (100)\). (Pista: use Teorema 4.16.)
2. \(179^{121} = _{100} 79^{121}\)Demuéstralo.
3. \(79^{121} = _{100} 79^{1}\)Demuéstralo. (Pista: use Teorema 5.4)
4. ¿Cuáles son los últimos\(2\) dígitos de\(179^{121}\)?

Los siguientes 5 ejercicios sobre criptografía básica se basan en [22]. Primero algo de lenguaje. El mensaje original legible se llama texto plano. La codificación del mensaje se llama cifrado. Y el mensaje codificado a menudo se llama el mensaje cifrado o código. Para revertir el proceso, es decir: para volver a convertir el mensaje cifrado en texto plano, a menudo se necesita una clave. A continuación codificaremos las letras por\(0\) a través\(25\) (en orden alfabético). Encriptamos usando un cifrado multiplicativo. Esto significa que cifraremos nuestro texto multiplicando cada número por el módulo de cifrado 26, para luego devolver la letra correspondiente. Por ejemplo, si usamos el cifrado\(3\) para cifrar el bob de texto plano, obtenemos el texto cifrado de la siguiente manera 1.14.1\(\rightarrow\) 3.42.3\(\rightarrow\) 3.16.3.

Ejercicio\(\PageIndex{13}\)

1. Utilice el cifrado multiplicativo\(3\) para decodificar DHIM.
2. Demostrar que una manera fácil de decodificar es multiplicar por\(9\) (módulo\(26\)). El algoritmo correspondiente a nivel numérico se llama división por\(3\) módulo\(26\).
3. Supongamos en cambio que nuestro cifrado multiplicativo lo era\(4\). Codifica bob de nuevo.
4. ¿Podemos invertir este cifrado mediante el uso de módulo de multiplicación\(26\)? Explique por qué.

Ejercicio\(\PageIndex{14}\)

Supongamos que tenemos un alfabeto de\(q\) letras y ciframos usando el cifrado multiplicativo\(p \in \{0, \cdots q-1\}\). Utilice la aritmética modular para mostrar que el cifrado se puede invertir si y solo\(\gcd (p, q) = 1\). (Pista: Supongamos que el cifrado de\(j_{1}\) y\(j_{2}\) son iguales. Luego busque y use el teorema de Factorización Única en el Capítulo 2.)

Ejercicio\(\PageIndex{15}\)

Asumir el ajuste del ejercicio 5.14. Supongamos\(p\) y\(q\) son tales que el cifrado es invertible. ¿Cuál es el algoritmo de descifrado? Demuéstralo. (Pista Encuentra\(r \in \{0, \cdots q-1\}\) tal que\(rp = _{q} 1\). Luego multiplique el cifrado por\(r\).)

Ejercicio\(\PageIndex{16}\)

Resolver los dos últimos problemas si ciframos usando un cifrado afín\((a, p)\). Es decir, el cifrado en el alfabeto\(\{0, \cdots q-1\}\) se realiza de la siguiente manera:

\[i \rightarrow a+pi \mbox{ mod } q \nonumber\]

Calcular cuándo se puede invertir esto, y cuál es el algoritmo para la inversa.

Ejercicio\(\PageIndex{17}\)

Descifrar el código V'ir Tbg n Frperg.

Ejercicio\(\PageIndex{18}\)

1. \(7^{72}\)Mod de cómputos\(13\), usando exponenciación modular.
2. De manera similar para\(484^{187}\) mod\(1189\).
3. Encuentra\(100!+102!\) mod\(101\). (Pista: Fermat.)
4. \(1381! = _{1382} 0\)Demuéstralo. (Pista: Wilson.)

Ejercicio\(\PageIndex{19}\)

Caracterizar el conjunto de\(n \ge 2\) para el que\(n\) el\((n-1)!\) mod no está en\(\{0, -1\}\). (Pista: Wilson.)

Teorema 5.20 (Teorema Binomial)

Si\(n\) es un entero positivo, entonces

\[\begin{array}{ccc} {(a+b)^{n} = \sum_{i=0}^{n} \binom{n}{i} a^{i} b^{n-i}}&{\mbox{where}}&{\binom{n}{i} = \frac{n!}{i! (n-i)!}} \end{array} \nonumber\]

Ejercicio\(\PageIndex{20}\)

1. Si\(p\) es primo, muestra que\({p \choose i}\) mod\(p\) es igual a\(0\) if\(1 \le i \le p-1\), y es igual a\(1\) if\(i = 0\) o\(i = p\).
2. Evaluar\({4 \choose 2} \mbox{ mod } 4\) y\({6 \choose 4} \mbox{ mod } 6\). Entonces, ¿dónde en (a) usaste el hecho de que\(p\) es prime?
3. Usa el teorema binomial para mostrar que si\(p\) es primo\((a+b)^{p} = _{p} a^{p}+b^{p}\)

Ejercicio\(\PageIndex{21}\)

\(p\)Déjese ser prime.

1. Demostrar que\(0^{p} = _{p} 0\)
2. \(k > 0\)Demuéstralo por, si\(k^{p} = _{p} k\), entonces\((k+1)^{p} = _{p} k+1\). (Pista: use el ejercicio 5.20.)
3. Concluir eso para todos\(n \in \{0,1,2,\cdots\}, n^{p} = _{p} n\). (Pista: usar inducción)
4. Demuéstralo para todos\(n \in \mathbb{Z}, n^{p} = _{p} n\). (Pista:\((-n)^{p} = _{p} (-1)^{p}n^{p}\).)
5. Utilizar (d) para probar el pequeño teorema de Fermat. (Pista: usar cancelación.)

Los ejercicios 3.19 y 3.22 muestran cómo resolver congruencias lineales en general. Las congruencias cuadráticas son mucho más complicadas. A modo de ejemplo. miramos la ecuación\(x^{2} = _{p} \pm 1\) en el siguiente ejercicio.

Ejercicio\(\PageIndex{22}\)

1. Demostrar que el pequeño teorema de Fermat da una solución de\(x^{2}-1 = _{p} 0\) cuando\(p\) sea un primo impar. (Pista: considerar\(a^{\frac{p-1}{2}}\).)
2. Demostrar que el teorema de Wilson implica que para primos impares\(p\)\[(-1)^{\frac{p-1}{2}} ((\frac{p-1}{2})!)^2 = _{p} -1 \nonumber\] (pista: la mano derecha da módulo de todos los residuos reducidos\(p\).)
3. Mostrar que si también\(p = _{4} 1\) (los ejemplos son 13,17,29, etc), entonces\[((\frac{p-1}{2})!)^2 = _{p} -1 \nonumber\] satisface la congruencia cuadrática\(x^2+1 = _{p} 0\).
4. Supongamos\(x^2+1 = _{p} 0\) y\(p\) es un primo impar. Demostrar que el pequeño teorema de Fermat implica que\[(-1)^{\frac{p-1}{2}} = 1 \nonumber\]
5. Demostrar que\(p\) en (d) no puede satisfacer\(p = _{4} 3\).

Ejercicio\(\PageIndex{23}\)

Let\(R = \{1,3,5,7,9,11,13,15\}\), el conjunto reducido de residuos módulo\(16\). En\(\mathbb{Z}_{16}\) y para cada uno\(r \in R\), definir multiplicación por\(r^{-1}\) (o división por\(r\)).

Ejercicio\(\PageIndex{24}\)

1. Elaborar las tablas de suma y multiplicación para\(\mathbb{Z}_{7}\).
2. Haz lo mismo para\(\mathbb{Z}_{8}\). Está bien definida la división.
3. Lo mismo para el conjunto reducido de residuos más\(0\) in\(\mathbb{Z}_{8}\). ¿Qué va mal aquí?

Ejercicio\(\PageIndex{25}\)

Dado\(n > 2\), dejar\(R \subseteq \mathbb{Z}_{n}\) ser el conjunto reducido de residuos y dejar\(S \subseteq \mathbb{Z}_{n}\) ser el conjunto de soluciones en\(\mathbb{Z}_{n}\) de\(x^{2} = _{n} 1\) (o auto inversas).

1. \(S \subseteq R\)Demuéstralo. (Hint:Be ́zout)
2. Demostrar que\[\prod_{x \in R} x = n \prod_{x \in S} x (= _{n} 1 \mbox{ if S is empty}) \nonumber\]
3. Mostrar que si\(S\) contiene\(a\), entonces contiene\(-a\).
4. Demostrar que si\(a = _{n} -a\), entonces\(a\) y no\(-a\) están en\(S\).
5. Demostrar que\[\begin{array} {cc} {\prod_{x \in R} x = _{n} (-1)^m}&{\mbox{some } m} \end{array} \nonumber\]
6. \(m = |S|/2\)Demuéstralo.