3.5: El algoritmo de división y congruencia

Vista previa de la Actividad 1: Cocientes y Restos

1. Dejar\(a = 27\) y\(b = 4\). Ahora determinaremos varios pares de enteros\(q\) y\(r\) para eso\(27 = 4q + r\). Por ejemplo, si\(q = 2\) y\(r = 19\), obtenemos\(4 \cdot 2 + 19 = 27\). La siguiente tabla se configura para diversos valores de\(q\). Para cada uno\(q\), determinar el valor de\(r\) para que\(4q + r = 27\).

   \(q\)	1	2	3	4	5	6	7	8	9	10
   \(r\)		19						-5
   \(4q + r\)	27	27	27	27	27	27	27	27	27	27

2. ¿Cuál es el valor positivo más pequeño para r que obtuvo en sus ejemplos de la Parte (1)?
   
   La división no se considera una operación en el conjunto de enteros ya que el cociente de dos enteros no necesita ser un entero. Sin embargo, todos hemos dividido un entero por otro y hemos obtenido un cociente y un resto. Por ejemplo, si dividimos 113 por 5, obtenemos un cociente de 22 y un resto de 3. Podemos escribir esto como\(\dfrac{113}{5} = 22 + \dfrac{3}{5}\). Si multiplicamos ambos lados de esta ecuación por 5 y luego usamos la propiedad distributiva para “borrar los paréntesis”, obtenemos
   
   \(5 \cdot \dfrac{113}{5} = 5 (22 + \dfrac{3}{5})\)
   \(113 = 5 \cdot 22 + 3\)
   
   Esta es la ecuación que usamos al trabajar en el enteros ya que implica sólo multiplicación y suma de enteros.
3. ¿Cuáles son el cociente y el resto cuando dividimos 27 por 4? ¿Cómo se relaciona esto con tu respuesta para la Parte (2)?
4. Repita la parte (1) usando\(a = -17\) y\(b = 5\). Entonces el objeto es encontrar enteros\(q\) y\(r\) así eso\(-17 = 5q + r\). Haga esto completando la siguiente tabla.

   \(q\)	-7	-6	-5	-4	-3	-2	-1
   \(r\)	18					-7
   \(5q + r\)	-17	-17	-17	-17	-17	-17	-17

5. La convención que seguiremos es que el resto será el entero positivo más pequeño\(r\) para el cual\(-17 = 5q + r\) y el cociente será el valor correspondiente de\(q\). Usando esta convención, ¿cuál es el cociente y cuál es el resto cuando -17 se divide por 5?

Vista previa Actividad 2: Algunos Trabajos con Congruencia Modulo\(n\)

1. Dejar\(n\) ser un número natural y dejar\(a\) y\(b\) ser enteros.

   (a) Escribir la definición de “\(a\)es congruente con\(b\) módulo”\(n\), que se escribe\(a \equiv b\) (mod\(n\)).

   (b) Utilizar la definición de “divide” para completar lo siguiente:
   Cuando escribimos\(a \equiv b\) (mod\(n\)), podemos concluir que existe un entero\(k\) tal que...
   
   Ahora exploraremos qué sucede cuando multiplicamos varios pares de enteros donde el primero es congruente a 3 módulo 6 y el segundo es congruente con 5 módulo 6. Podemos usar la notación set builder y el método roster para especificar el conjunto\(A\) de todos los enteros que son congruentes a 2 módulo 6 de la siguiente manera:
   \[A = \{a \in \mathbb{Z} | a \equiv 3\ (mod\ 6)\} = \{... -15, -9, -3, 3, 9, 15, 21, ...\}\]

2. Utilice el método roster para especificar el conjunto\(B\) de todos los enteros que son congruentes a 5 módulo 6.
   \[B = \{b \in \mathbb{Z} | b \equiv 5\ (mod\ 6)\} = ...\]
   Observe eso\(15 \in A\) y\(11 \in B\) y eso\(15 + 11 = 26\). También observe que\(26 \equiv 2\) (mod 6) y que 2 es el entero positivo más pequeño que es congruente a 26 (mod 6).
3. Ahora elige al menos otros cuatro pares de enteros\(a\) y\(b\) dónde\(a \in A\) y\(b \in B\). Para cada par, calcule\((a + b)\) y luego determine el entero positivo más pequeño\(r\) para el cual\((a + b) \equiv r\) (mod 6). Nota: El entero\(r\) satisfará las desigualdades\(0 \le r < 6\).
4. Demostrar que para todos los enteros\(a\) y\(b\), si\(a \equiv\) 3 (mod 6) y\(b \equiv\) 5 (mod 6), entonces\((a + b) \equiv\) 2 (mod 6).

El algoritmo de división

Preview Activity\(\PageIndex{1}\) fue una introducción a un resultado matemático conocido como Algoritmo de División. Uno de los propósitos de esta actividad previa fue ilustrar que ya hemos trabajado con este resultado, quizás sin conocer su nombre. Por ejemplo, cuando dividimos 337 por 6, a menudo escribimos

\[\dfrac{337}{6} = 56 + \dfrac{1}{6}. \nonumber\]

Cuando multiplicamos ambos lados de esta ecuación por 6, obtenemos

\[337 = 6 \cdot 56 + 1 \nonumber\]

Cuando estamos trabajando dentro del sistema de enteros, se prefiere la segunda ecuación sobre la primera ya que la segunda usa solo enteros y las operaciones de suma y multiplicación, y los enteros se cierran bajo suma y multiplicación. A continuación se presenta una declaración completa del Algoritmo de División.

El algoritmo de división

Para todos los enteros\(a\) y\(b\) con\(b > 0\), existen enteros únicos\(q\) y\(r\) tales que

\(a = bq + r\)y\(0 \le r < b\)

Algunos comentarios sobre el algoritmo de división

1. Se puede probar el Algoritmo de División, pero aún no hemos estudiado los métodos que suelen emplearse para hacerlo. En este texto, trataremos al Algoritmo de División como un axioma de los enteros. El trabajo en Preview Activity\(\PageIndex{1}\) proporciona cierta justificación de que se trata de un axioma razonable.
2. El enunciado del Algoritmo de División contiene la nueva frase, “existen enteros únicos q y r tales que...” Esto quiere decir que sólo hay un par de enteros\(q\) y\(r\) que satisfacen tanto las condiciones\(a = bq + r\) como\(0 \le r < b\). Como vimos en Preview Activity\(\PageIndex{1}\), hay varias formas diferentes de escribir el entero\(a\) en la forma\(a = bq + r\). No obstante, sólo hay una manera de hacer esto y satisfacer la condición adicional que\(0 \le r < b\).
3. A la luz del comentario anterior, cuando hablamos del cociente y del resto cuando “dividimos un entero\(a\) por el entero positivo”\(b\), siempre nos referiremos al cociente\((q)\) y al resto\((r)\) garantizado por el Algoritmo de División. Entonces el resto r es el menor número entero no negativo tal que existe un entero (cociente)\(q\) con\(a = bq + r\).
4. Si\(a < 0\), entonces debemos tener cuidado al escribir el resultado del Algoritmo de División. Por ejemplo, en las partes (4) y (5) de Preview Activity\(\PageIndex{1}\), con\(a = -17\) y\(b = 5\), obtuvimos\(-17 = 5 \cdot (-4) + 3\), y así el cociente es -4 y el resto es 3. Observe que esto es diferente al resultado de una calculadora, que sería\(\dfrac{-17}{5} = -3.4\). Pero esto significa\[\dfrac{-17}{5} = -(3 + \dfrac{4}{10}) = -3 - \dfrac{2}{5}.\] Si multiplicamos ambos lados de esta ecuación por 5, obtenemos\[-17 = 5 (-3) + (-2).\] Este no es el resultado garantizado por el Algoritmo de División ya que el valor de 2 no satisface el resultado de ser mayor o igual a 0 e inferior a 5.
5. Una forma de ver el Algoritmo de División es que el entero\(a\) va a ser un múltiplo de\(b\), o se encontrará entre dos múltiplos de\(b\). Supongamos que no\(a\) es un múltiplo de\(b\) y que se encuentra entre los múltiplos\(b \cdot q\) y\(b (q + 1)\), donde\(q\) hay algún entero. Esto se muestra en la recta numérica de la Figura 3.2.

Figura 3.2: Resto para el algoritmo de división

6. Si\(r\) representa la distancia de\(b \cdot q\) a\(a\), entonces
   \ begin {eqnarray}
   r &=& a - b\ cdot q, o\\
   a &=& b\ cdot q +r.
   \ end {eqnarray}
   Del diagrama, observe también que \(r\)es menor que la distancia entre\(b \cdot q\) y\(b (q + 1)\). Álgebraicamente, esta distancia es
   \ begin {eqnarray}
   b (q + 1) - b\ cdot q &=& b\ cdot q + b - b\ cdot q\\
   &=& b.
   \ end {eqnarray}
   Así, en el caso donde no\(a\) es un múltiplo de\(b\), obtenemos\(0 < r < b\).
7. Hemos estado usando implícitamente el hecho de que un entero no puede ser par e impar. Hay varias formas de entender este hecho, pero una forma es a través del Algoritmo de División. Cuando clasificamos un entero como par o impar, lo estamos haciendo sobre la base del resto (según el Algoritmo de División) cuando el entero está “dividido” por 2. Si\(a \in \mathbb{Z}\), entonces por el Algoritmo de División existen enteros únicos\(q\) y\(r\) tal que
   
   \(a = 2q + r\) y\(0 \le r < 2\).

   Esto significa que el resto,\(r\), sólo puede ser cero o uno (y no ambos). Cuando\(r = 0\), el entero es par, y when\(r = 1\), el entero es impar.

Comprobación de Progreso 3.26: Uso del Algoritmo de División

1. ¿Cuáles son los posibles restos (según el algoritmo de división) cuando un entero es
   1. a) ¿Dividido por 4?
   2. b) ¿Dividido por 9?
2. Para cada una de las siguientes, encuentre el cociente y el resto (garantizado por el Algoritmo de División) y luego resuma los resultados escribiendo una ecuación de la forma\(a = bq + r\), donde\(0 \le r < b\).
   1. Cuando 17 se divide por 3.
   2. Cuando -17 se divide por 3.
   3. Cuando 73 se divide por 7.
   4. Cuando -73 se divide por 7.
   5. Cuando 436 se divide por 27.
   6. Cuando 539 se divide por 110.

Contestar

Agrega textos aquí. No elimine primero este texto.

Uso de casos determinados por el algoritmo de división

El algoritmo de división a veces se puede usar para construir casos que se pueden usar para probar una declaración que es verdadera para todos los enteros. Esto lo hemos hecho cuando dividimos los enteros en los enteros pares y los enteros impares ya que los enteros pares tienen un resto de 0 cuando se dividen por 2 y los enteros impares tienen un resto o 1 cuando se dividen por 2.

A veces es más útil dividir el entero\(a\) por un entero distinto de 2. Por ejemplo, si\(a\) se divide por 3, hay tres posibles restos: 0, 1 y 2. Si\(a\) se divide por 4, hay cuatro posibles restos: 0, 1, 2 y 3. Los restos forman la base de los casos.

Si la hipótesis de una proposición es que “\(n\)es un entero”, entonces podemos usar el Algoritmo de División para afirmar que hay números enteros únicos\(q\) y\(r\) tales que

\(n = 3q + r\)y\(0 \le r < 3\)

Entonces podemos dividir la prueba en los siguientes tres casos: (1)\(r = 0\); (2)\(r = 1\); y (3)\(r = 2\). Esto se hace en la Proposición 3.27.

Proposición 3.27

Si\(n\) es un entero, entonces 3 divide\(n^3 - n\).

Prueba

Dejar\(n\) ser un entero. Mostraremos que 3 divide\(n^3 - n\) examinando los tres casos para el resto cuando\(n\) se divide por 3. Por el Algoritmo de División, existen enteros únicos\(q\) y\(r\) tales que

\(n = 3q + r\), y\(0 \le r < 3\).

Esto significa que podemos considerar los siguientes tres casos: (1)\(r = 0\); (2)\(r = 1\); y (3)\(r = 2\).

En el caso donde\(r = 0\), tenemos\(n = 3q\). Al sustituir esto en la expresión\(n^3 - n\), obtenemos

\ begin {eqnarray}
n^3 - n &=& (3q) ^3 - (3q)\\
&=& 27q^3 - 3q\\
&=& 3 (9q^3-q).
\ end {eqnarray}

Dado que\((9q^3 -q)\) es un entero, la última ecuación lo demuestra\(3 | (n^3 - n)\).

En el segundo caso,\(r = 1\) y\(n = 3q + 1\). Cuando sustituimos esto en\((n^3 -n)\), obtenemos

\ begin {eqnarray}
n^3 - n &=& (3q + 1) ^3 - (3q + 1)\\
&=& (27q^ {3} 27q^ {2} + 27q + 1) - (3q + 1)\\
&=& 27q^3 + 27q^2 + 6q\\
&=& 3 (9q^3 + 9q^2 + 2q).
\ end {eqnarray}

Dado que\((9q^3 + 9q^2 + 2q)\) es un entero, la última ecuación lo demuestra\(3 | (n^3 - n)\).

El último caso es cuando\(r = 2\). Los detalles para este caso son parte del Ejercicio (1). Una vez concluido este caso, habremos probado que 3 divide\(n^3 - n\) en los tres casos. De ahí que podamos concluir que si n es un número entero, entonces 3 divide\(n^3 - n\).

Propiedades de Congruencia

La mayor parte del trabajo que hemos realizado hasta ahora ha consistido en utilizar definiciones para ayudar a probar resultados. Seguiremos probando algunos resultados pero ahora probaremos algunos teoremas sobre congruencia (Teorema 3.28 y Teorema 3.30) que luego usaremos para ayudar a probar otros resultados.

Vamos\(n \in \mathbb{N}\). Recordemos que si\(a\) y\(b\) son enteros, entonces decimos que\(a\) es congruente con\(b\) modulo\(n\) siempre que\(n\) divida\(a - b\), y escribimos\(a \equiv b\) (mod\(n\)). (Ver Sección 3.1.) Ahora vamos a probar algunas propiedades de congruencia que son consecuencias directas de la definición. Una de estas propiedades fue sugerida por el trabajo en Vista previa de Actividad\(\PageIndex{2}\) y es la Parte (1) del siguiente teorema.

Teorema 3.28: Propiedades de Congruencia Modulo\(n\)

Dejar\(n\) ser un número natural y dejar\(a\)\(b\),\(c\),, y\(d\) ser enteros. Si\(a \equiv b\) (mod\(n\)) y\(c \equiv d\) (mod\(n\)), entonces

1. \(a + c) \equiv (b + d)\)(mod\(n\)).
2. \(ac \equiv bd\)(mod\(n\)).
3. Para cada uno\(m \in \mathbb{N}\),\(a^{m} \equiv b^{m}\) (mod\(n\)).

Prueba

Demostraremos Partes (2) y (3). El comprobante de la Parte (1) es Comprobación de Progreso 3.29. Dejar\(n\) ser un número natural y dejar\(a\)\(b\),\(c\),, y\(d\) ser enteros. Supongamos que\(a \equiv b\) (mod\(n\)) y\(c \equiv d\) (mod\(n\)). Esto significa que\(n\) divide\(a - b\) y eso\(n\) divide\(c - d\). De ahí que existan enteros\(k\) y\(q\) tal que\(a - b = nk\) y\(c - d = nq\). Luego podemos escribir\(a = b + nk\)\(c = d + nq\) y obtener

\ begin {eqnarray}
ac &=& (b + nk) (d + nq)\\
&=& bd + bnq + dnk + n^2kq\\
&=& bd + n (bq + dk + nkq).
\ end {eqnarray}

restando\(bd\) de ambos lados de la última ecuación, vemos que

\[ac - bd = n (bq + dk + nkq).\]

Ya que\(bq + dk + nkq\) es un entero, esto lo demuestra\(n | (ac - bd)\), y de ahí podemos concluir que\(ac \equiv bd\) (mod\(n\)). Esto completa la prueba de la Parte (2).

La parte (2) básicamente significa que si tenemos dos congruencias, podemos multiplicar los lados correspondientes de estas congruencias para obtener otra congruencia. Hemos asumido que\(a \equiv�� b\) (mod\(n\)) y así escribimos esto dos veces de la siguiente manera:

\ begin {eqnarray}
a &\ equiv& b (mod\ n),\ y\\
a &\ equiv& b (mod\ n).
\ end {eqnarray}

Si ahora usamos el resultado en la Parte (2) y multiplicamos los lados correspondientes de estas dos congruencias, obtenemos\(a^2 \equiv b^2\) (mod\(n\)). Entonces podemos usar esta congruencia y la congruencia\(a \equiv b\) (mod\(n\)) y el resultado en la Parte (2) para concluir que

\[a^2 \cdot b \equiv b^2 \cdot b (mod\ n),\]

o eso\(a^3 \equiv b^3\) (mod\(n\)). Podemos decir que podemos continuar con este proceso para acreditar la Parte (3), pero esto no se considera una prueba formal de este resultado. Para construir una prueba formal para esto, podríamos usar una prueba por inducción matemática. Esto se estudiará en el Capítulo 4. Ver Ejercicio (13) en la Sección 4.1.

Comprobación de Progreso 3.29: Prueba Parte (1) del Teorema 3.28

Demostrar parte (1) del Teorema 3.28.

Contestar

Agrega textos aquí. No elimine primero este texto.

El ejercicio (11) en la Sección 3.1 dio tres importantes propiedades de módulo de congruencia\(n\). Por su importancia, estas propiedades son declaradas y probadas en el Teorema 3.30. Por favor, recuerde que las pruebas de libros de texto generalmente se escriben en forma final de “reportar las noticias”. Antes de leer estas pruebas, podría ser instructivo tratar primero de construir una tabla de conocimientos para cada prueba.

Teorema 3.30: Propiedades de Congruencia Modulo\(n\)

Dejar\(n \in \mathbb{N}\), y dejar\(a\)\(b\),, y\(c\) ser enteros.

1. Por cada entero\(a\),\(a \equiv a\) (mod\(n\)).
   A esto se le llama la propiedad reflexiva de módulo de congruencia\(n\).
2. Si\(a \equiv b\) (mod\(n\)), entonces\(b \equiv a\) (mod\(n\)).
   A esto se le llama propiedad simétrica de módulo de congruencia\(n\).
3. Si\(a \equiv b\) (mod\(n\)) y\(b \equiv c\) (mod\(n\)), entonces\(a \equiv c\) (mod\(n\)).
   Esto se llama propiedad transitiva de congruencia módulo\(n\).

Prueba

Demostraremos la propiedad reflexiva y la propiedad transitiva. El comprobante de la propiedad simétrica es Ejercicio (3).

Vamos\(n \in \mathbb{N}\), y vamos\(a \in \mathbb{Z}\). Vamos a mostrar eso\(a \equiv a\) (mod\(n\)). Observe que

\[a - a = 0 = n \cdot 0.\]

Esto prueba que\(n\) divide\(a - a\) y de ahí, por la definición de módulo de congruencia\(n\), hemos demostrado que\(a \equiv a\) (mod\(n\)).

Para probar la propiedad transitiva, dejamos\(n \in \mathbb{N}\), y dejamos\(a\),\(b\), y\(c\) ser enteros. Suponemos que\(a \equiv b\) (mod\(n\)) y\(b \equiv c\) (mod\(n\)). Usaremos la definición de módulo de congruencia\(n\) para probarlo\(a \equiv c\) (mod\(n\)). Desde\(a \equiv b\) (mod\(n\)) y\(b \equiv c\) (mod\(n\)), lo sabemos\(n | (a - b)\) y\(n | (b - c)\). De ahí que existan enteros\(k\) y\(q\) tales que

\ begin {eqnarray}
a - b &=& nk\\
b - c &=& nq. \\
\ fin {eqnarray}

sumando los lados correspondientes de estas dos ecuaciones, obtenemos

\[(a - b) + (b - c) = nk + nq.\]

Si simplificamos el lado izquierdo de la última ecuación y factorizamos el lado derecho, obtenemos

\[a - c = n (k + q).\]

Por la propiedad de cierre de los enteros,\((k + q) \in \mathbb{Z}\), y así esta ecuación prueba eso\(n | (a - c)\) y por lo tanto eso\(a \equiv c\) (mod\(n\)). Esto completa la prueba de la propiedad transitiva de congruencia módulo\(n\).

Uso de Casos Basados en Congruencia Modulo\(n\)

Observe que el conjunto de todos los enteros que son congruentes a 2 módulo 7 es

\[\{n \in \mathbb{Z} | n \equiv 2\ (mod\ 7)\} = \{..., -19, -12, -5, 2, 9, 16, 23,...\}\]

Si dividimos cualquier entero en este conjunto por 7 y escribimos el resultado de acuerdo con el Algoritmo de División, obtendremos un resto de 2. Por ejemplo,

\ begin {eqnarray}
2 &=& 7\ cdot 0 + 2\\
9 &=& 7\ cdot 1 + 2\\
16 &=& 7\ cdot 2 + 2\\
23 &=& 7\ cdot 3 + 2\\
-5 &=& 7 (-1) + 2\\
-12 &=& 7 (-2) + 2\\
-19 &=& amp; 7 (-3) + 2\\
\ end {eqnarray}

¿Es esto una coincidencia o es esto siempre cierto? Veamos el caso general. Para ello, dejemos\(n\) ser un número natural y dejar\(a \in \mathbb{Z}\). Por el Algoritmo de División, existen enteros únicos\(q\) y\(r\) tales que

\(a = nq + r\)y\(0 \le r < n\).

Al restar\(r\) de ambos lados de la ecuación\(a = nq + r\), obtenemos

\(a - r = nq\).

Pero esto implica eso\(n | (a - r)\) y de ahí que\(a \equiv r\) (mod\(n\)). Hemos probado el siguiente resultado.

Teorema 3.31

Dejar\(n \in \mathbb{N}\) y dejar\(a \in mathbb{Z}\). Si\(a = nq + r\) y\(0 \le r < n\) para algunos enteros\(q\) y\(r\), entonces\(a \equiv r\) (mod\(n\)).

Este teorema dice que un entero es congruente (mod\(n\)) a su resto cuando se divide por\(n\). Dado que este resto es único y dado que los únicos restos posibles para la división por\(n\) son 0, 1, 2\(n 1\),..., podemos exponer el siguiente resultado.

Corolario 3.32

Si\(n \in \mathbb{N}\), entonces cada entero es congruente, módulo\(n\), con precisamente uno de los enteros 0, 1, 2,...,\(n - 1\). Es decir, para cada entero\(a\), existe un entero único\(r\) tal que

\(a \equiv r\)(mod\(n\)) y\(0 \le r < n\).

El corolario 3.32 se puede usar para configurar casos para un entero en una prueba. Si\(n \in \mathbb{N}\) y\(a \in \mathbb{Z}\), entonces podemos considerar\(n\) casos para\(a\). El entero a podría ser congruente a 0,1, 2,..., o\(n - 1\) módulo\(n\). Por ejemplo, si asumimos que 5 no divide un entero\(a\), entonces sabemos que no\(a\) es congruente con 0 módulo 5, y por lo tanto, que\(a\) debe ser congruente con 1, 2, 3 o 4 módulo 5. Podemos usar estos como 4 casos dentro de una prueba. Por ejemplo, supongamos que deseamos determinar los valores de\(a^2\) módulo 5 para enteros que no son congruentes a 0 módulo 5. Comenzamos por cuadrar algunos enteros que no son congruentes a 0 módulo 5. Vemos que

\ begin {eqnarray}
1^2 &=& 1\\\\\\\\\\\\\\\\\\\\\ y\\\\\\\\\\\\\\\\\\\\\\ 1&\\ equiv& 1\ (mod\ 5). \\
3^2 &=& 9\\\\\\\\\\\\\\\\\\\ y\\\\\\\\\\\\\\\\\\\\\\\\\\ 9&\ equiv& 4\ (mod\ 5). \\
6^2 &=& 36\\\\\\\\\\\\\\\\\\ y\\\\\\\\\\\\\\\\\\\\\\\\\\\ 36&\\ equiv& 1\ (mod\ 5). \\
8^2 &=& 64\\\\\\\\\\\\\\\\\\ y\\\\\\\\\\\\\\\\\\\\\\\\\\\\ 64&\ equiv& 4\ (mod\ 5). \\
9^2 &=& 81\\\\\\\\\\\\\\\\\\ y\\\\\\\\\\\\\\\\\\\\\\\\\ 81&\\ equiv& 1\ (mod\ 5).
\ end {eqnarray}

Estas exploraciones indican que la siguiente proposición es cierta y ahora esbozaremos un método para demostrarla.

Proposición 3.33.

Para cada entero\(a\), si\(a \not\equiv 0\) (mod 5), entonces\(a^2 \equiv 1\) (mod 5) o\ (a^2\ equiv 4) (mod 5).

Prueba

Demostraremos esta proposición usando casos para\(a\) basados en congruencia módulo 5. Al hacerlo, utilizaremos los resultados en Teorema 3.28 y Teorema 3.30. Debido a que la hipótesis es\(a \not \equiv 0\) (mod 5), podemos usar cuatro casos, que son: (1)\(a \equiv 1\) (mod 5), (2)\(a \equiv 2\) (mod 5), (3)\(a \equiv 3\) (mod 5) y (4)\ (a\ equiv 4) (mod 5). A continuación se presentan pruebas para los casos primero y cuarto.

Caso 1. (\(a \equiv 1\)(mod 5)). En este caso, utilizamos el Teorema 3.28 para concluir que

\(a^2 \equiv 1^2\)(mod 5) o\(a^2 \equiv 1\) (mod 5).

Esto demuestra que si\(a \equiv 1\) (mod 5), entonces\(a^ \equiv 1\) (mod 5).

Caso 4. (\(a \equiv 4\)(mod 5)). En este caso, utilizamos el Teorema 3.28 para concluir que

\(a^2 \equiv 4^2\)(mod 5) o\(a^2 \equiv 16\) (mod 5).

También lo sabemos\(16 \equiv 1\) (mod 5). Entonces tenemos\(a^2 \equiv 16\) (mod 5) y\(16 \equiv 1\) (mod 5), y ahora podemos usar la propiedad transitiva de congruencia (Teorema 3.30) para concluir que\(a^2 \equiv 1\) (mod 5). Esto demuestra que si\(a \equiv 4\) (mod 5), entonces\(a^2 \equiv 1\) (mod 5).

Comprobación de progreso 3.34 (Uso de propiedades de congruencia)

Completar un comprobante de la Proposición 3.33 completando pruebas para los otros dos casos.

Nota: Es posible probar la Proposición 3.33 usando solo la definición de congruencia en lugar de usar las propiedades que hemos probado sobre la congruencia. Sin embargo, tal prueba implicaría una buena cantidad de álgebra. Una de las ventajas de utilizar las propiedades es que evita el uso de álgebra complicada en la que es fácil cometer errores.

Contestar

Agrega textos aquí. No elimine primero este texto.

En la prueba de la Proposición 3.33, se utilizaron cuatro casos. A veces puede parecer un poco abrumador cuando se enfrenta a una prueba que requiere de varios casos. Por ejemplo, si queremos probar algo sobre algunos enteros módulo 6, es posible que tengamos que usar seis casos. Sin embargo, a veces hay supuestos (o conclusiones) adicionales que pueden ayudar a reducir el número de casos que deben considerarse. Esto se ilustrará en la próxima comprobación de progreso.

Comprobación de Progreso 3.35: Uso de Casos Modulo 6

Supongamos que queremos determinar los valores posibles para el\(a^2\) módulo 6 para enteros impares que no son múltiplos de 3. Antes de comenzar a utilizar la aritmética de congruencia (como en la prueba de la Proposición 3.33) en cada uno de los seis posibles casos, podemos demostrar que algunos de los casos no son posibles bajo estos supuestos. (En cierto sentido, utilizamos una prueba corta por contradicción para estos casos.) Entonces supongamos que\(a\) es un entero impar. Entonces:

• Si\(a \equiv 0\) (mod 6), entonces existe un entero\(k\) tal que\(a = 6k\). Pero entonces\(a = 2(3k)\) y por lo tanto,\(a\) es parejo. Ya que asumimos que eso\(a\) es extraño, este caso no es posible.
• Si\(a \equiv 2\) (mod 6), entonces existe un entero\(k\) tal que\(a = 6k + 2\). Pero entonces\(a = 2(3k + 1)\) y por lo tanto,\(a\) es parejo. Ya que asumimos que eso\(a\) es extraño, este caso no es posible.

1. Demostrar que si\(a\) es un entero impar, entonces\(a\) no puede ser congruente con 4 módulo 6.
2. Demostrar que si\(a\) es un entero y 3 no divide\(a\), entonces\(a\) no puede ser congruente con 3 módulo 6.
3. Entonces si\(a\) es un entero impar que no es múltiplo de 3, entonces\(a\) debe ser congruente a 1 o 5 módulo 6. Utilice estos dos casos para probar la siguiente proposición:

Contestar

Agrega textos aquí. No elimine primero este texto.

Proposición 3.36.

Para cada entero\(a\), si\(a\) es un entero impar que no es múltiplo de 3, entonces\(a^2 \equiv 1\) (mod 6).

Ejercicios para la Sección 3.5

1. Complete los datos para el comprobante del Caso 3 de la Proposición 3.27.
2. Extendiendo la idea en el Ejercicio (1) de la Sección 3.4, podemos representar tres enteros consecutivos como\(m\),\(m + 1\), y\(m + 2\), donde\(m\) es un entero.
   
   (a) Explicar por qué también podemos representar tres enteros consecutivos como\(k - 1\),\(k\), y\(k + 1\), donde\(k\) es un entero.
   (b) Explicar por qué la Proposición 3.27 prueba que el producto de tres enteros consecutivos cualquiera es divisible por 3.
   (c) Demostrar que el producto de tres enteros consecutivos es divisible por 6.
3. Demostrar la propiedad simétrica de congruencia establecida en el Teorema 3.30.
4. (a) Dejar\(n \in \mathbb{N}\) y dejar\(a \in \mathbb{Z}\). Explica por qué\(n\) divide\(a\) si y solo si\(a \equiv 0\) (mod\(n\)).
   b) Dejar\(a \in \mathbb{Z}\). Explica por qué si\(a \not\equiv 0\) (mod 3), entonces\(a \equiv 1\) (mod 3) o\(a \equiv 2\) (mod 3).
   c) ¿Es verdadera o falsa la siguiente proposición? Justifica tu conclusión.
   Para cada uno\(a \in \mathbb{Z}\),\(a \not\equiv 0\) (mod 3) si y solo si\(a^2 \equiv 1\) (mod 3).
5. (a) Casos de uso basados en congruencia módulo 3 y propiedades de congruencia para demostrar que para cada entero\(n\),\(n^3 \equiv n\) (mod 3).
   (b) Explicar por qué el resultado de la Parte (a) demuestra que para cada entero\(n\), 3 divide\(n^3 - n\). Compárelo con la prueba del mismo resultado en la Proposición 3.27.
6. Demostrar que para cada número natural\(n\), no\(\sqrt{3n + 2}\) es un número natural.
7. Demostrar la siguiente proposición demostrando su contrapositiva. (Pista: Análisis de casos de uso. Hay varios casos.
   
   Para todos los enteros\(a\) y\(b\), si\(ab \equiv 0\) (mod 3), entonces\(a \equiv 0\) (mod 3) o\(b \equiv 0\) (mod 3).
8. a) Explicar por qué la siguiente proposición es equivalente a la proposición en el Ejercicio (7).
   Para todos los enteros\(a\) y\(b\), si\(3 | ab\), entonces\(3 | a\) o\(3 | b\).
   (b) Demostrar que para cada entero\(a\), si 3 divide\(a^2\), entonces 3 divide\(a\).
9. a) Demostrar que el número real\(\sqrt 3\) es un número irracional. Es decir, probar que
   Si\(r\) es un número real positivo tal que\(r^2 = 3\), entonces\(r\) es irracional.
   b) Demostrar que el número real\(\sqrt{12}\) es un número irracional.
10. (a) Utilice el resultado de la Proposición 3.33 para ayudar a probar que el entero\(m\) = 5, 344, 580, 232, 468, 953, 153 no es un cuadrado perfecto. Recordemos que un entero\(n\) es un cuadrado perfecto siempre que exista un entero\(k\) tal que\(n = k^2\). Pista: Usa una prueba por contradicción.
    (b) ¿Es el entero\(n\) = 782, 456, 231, 189, 002, 288, 438 un cuadrado perfecto? Justifica tu conclusión.
11. (a) Utilice el resultado de la Proposición 3.33 para ayudar a probar que para cada entero\(a\), si 5 divide\(a^2\), entonces 5 divide\(a\).
    b) Demostrar que el número real\(\sqrt 5\) es un número irracional.
12. (a) Demostrar que para cada entero\(a\), si\(a \not\equiv 0\) (mod 7), entonces\(a^2 \not\equiv 0\) (mod 7).
    (b) Demostrar que para cada entero\(a\), si 7 divide\(a^2\), entonces 7 divide\(a\).
    c) Demostrar que el número real\(\sqrt 7\) es un número irracional.
13. (a) Si un entero tiene un resto de 6 cuando se divide por 7, ¿es posible determinar el resto del cuadrado de ese entero cuando se divide por 7? Si es así, determine el resto y demuestre que su respuesta es correcta.
    (b) Si un entero tiene un resto de 11 cuando se divide por 12, ¿es posible determinar el resto del cuadrado de ese entero cuando se divide por 12? Si es así, determine el resto y demuestre que su respuesta es correcta.
    (c)\(n\) Sea un número natural mayor a 2. Si un entero tiene un resto de\(n - 1\) cuando se divide por\(n\), ¿es posible determinar el resto del cuadrado de ese entero cuando se divide por\(n\)? Si es así, determine el resto y demuestre que su respuesta es correcta.
14. Dejar\(n\) ser un número natural mayor que 4 y dejar que a sea un número entero que tenga un resto de\(n - 2\) cuando se divide por\(n\). Haz las conclusiones que puedas sobre el resto de\(a^2\) cuando se divide por\(n\). Justificar todas las conclusiones
15. ¿La siguiente proposición es verdadera o falsa? Justifica tu conclusión con una prueba o un contraejemplo.
    Por cada número natural\(n\), si 3 no divide\((n^2 + 2)\), entonces no\(n\) es un número primo o\(n = 3\).
16. a) ¿Es verdadera o falsa la siguiente proposición? Justifica tu conclusión con un contraejemplo o una prueba.
    Para cada entero\(n\), si\(n\) es impar entonces\(n^2 \equiv 1\) (mod 8).
    b) Comparar esta proposición con la proposición en el Ejercicio (7) de la Sección 3.4. ¿Estas dos proposiciones son equivalentes? Explique.
    c) ¿Es verdadera o falsa la siguiente proposición? Justifica tu conclusión con un contraejemplo o una prueba.
    Para cada entero\(n\), si\(n\) es impar y no\(n\) es un múltiplo de 3, entonces\(n^2 \equiv 1\) (mod 24).
17. Demostrar la siguiente proposición:
    Para todos los enteros\(a\) y\(b\), si 3 divide\((a^2 + b^2)\), entonces 3 divide\(a\) y 3 divide\(b\).
18. ¿La siguiente proposición es verdadera o falsa? Justifica tu conclusión con un contraejemplo o una prueba.
    Por cada entero\(a\), 3 divide\(a^3 + 23a\).
19. ¿Son verdaderas o falsas las siguientes afirmaciones? O probar que la afirmación es verdadera o proporcionar un contraejemplo para demostrar que es falsa.
    
    (a) Para todos los enteros\(a\) y\(b\), si\(a \cdot b \equiv 0\) (mod 6), entonces\(a \equiv 0\) (mod 6) o\(b \equiv 0\) (mod 6).
    (b) Para todos los enteros\(a\) y\(b\), si\(a \cdot b \equiv 0\) (mod 8), entonces\(a \equiv 0\) (mod 8) o\(b \equiv 0\) (mod 8).
    (c) Para todos los enteros\(a\) y\(b\), si\(a \cdot b \equiv 1\) (mod 6), entonces\(a \equiv 1\) (mod 6) o\(b \equiv 1\) (mod 6).
    (d) Para todos los enteros\(a\) y\(b\), si\(ab \equiv 7\) (mod 6), entonces ya sea\(a \equiv 1\) (mod 12) o\(b \equiv 7\) (mod 12).
20. (a) Determinar varios pares de enteros\(a\) y\(b\) tal que\(a \equiv b\) (mod 5). Para cada uno de esos pares, calcular\(4a + b\),\(3a + 2b\), y\(7a + 3b\). ¿Cada uno de los enteros resultantes es congruente con 0 módulo 5?
    (b) Demostrar o desacreditar la siguiente proposición:
    Dejar\(m\) y\(n\) ser enteros tales que\((m + n) \equiv 0\) (mod 5) y let\(a,b \in \mathbb{Z}\). Si\(a \equiv b\) (mod 5), entonces\((ma + nb) \equiv 0\) (mod 5).
21. Evaluación de pruebas
    Consulte las instrucciones para Ejercicio (19) en la página 100 de la Sección 3.1.
    a)

    Proposición

    Para todos los enteros\(a\) y\(b\), si\((a + 2b) \equiv 0\) (mod 3), entonces\((2a + b) \equiv 0\) (mod 3).

    Prueba

    Asumimos\(a,b \in \mathbb{Z}\) y\((a + 2b) \equiv 0\) (mod 3). Esto quiere decir que 3 divide\(a + 2b\) y, de ahí, existe un entero\(m\) tal que\(a + 2b = 3m\). De ahí,\(a = 3m - 2b\). Para\((2a + b) \equiv 0\) (mod 3), existe un entero\(x\) tal que\(2a + b = 3x\). Por lo tanto,

    \ begin {eqnarray}
    2 (3m - 2b) + b &=& 3x\\
    6m - 3b &=& 3x\\
    3 (2m - b) &=& 3x\\
    2m - b &=& x
    \ end {eqnarray}

    Dado que\((2m - b)\) es un entero, esto demuestra que 3 divide\((2a + b)\) y por lo tanto,\((2a + b) \equiv 0\) (mod 3)

    b)

    Proposición.

    Por cada entero\(m\), 5 divide\((m^5 - m)\).

    Prueba

    Vamos\(m \in \mathbb{Z}\). Demostraremos que 5 divide\((m^5 - m)\) demostrando que divide\((m^5 - m) \equiv 0\) (mod 5). Vamos a usar casos.

    Para el primer caso, si\(m \equiv 0\) (mod 5), entonces\(m^5 \equiv 0\) (mod 5) y, por lo tanto, ((m^5 - m)\ equiv 0\) (mod 5).

    Para el segundo caso, si\(m \equiv 1\) (mod 5), entonces\(m^5 \equiv 1\) (mod 5) y, por lo tanto, ((m^5 - m)\ equiv (1 - 1)\) (mod 5), lo que significa que ((m^5 - m)\ equiv 0\) (mod 5).

    Para el tercer caso, si\(m \equiv 2\) (mod 5), entonces\(m^5 \equiv 32\) (mod 5) y, por lo tanto, ((m^5 - m)\ equiv (32 - 2)\) (mod 5), lo que significa que ((m^5 - m)\ equiv 0\) (mod 5).

    Exploraciones y actividades

22. No es posible usar una contradicción para probar un caso. Explore las afirmaciones de las Partes (a) y (b) considerando varios ejemplos donde la hipótesis es cierta.
    
    (a) Si un entero\(a\) es divisible por 4 y 6, entonces es divisible por 24.
    (b) Si un entero\(a\) es divisible tanto por 2 como por 3, entonces es divisible por 6.
    c) ¿Qué se puede concluir de los ejemplos de la Parte a)?
    d) ¿Qué se puede concluir de los ejemplos de la Parte b)?
    
    La prueba de la siguiente proposición basada en los casos de usos de la Parte (b). En esta prueba, sin embargo, utilizamos casos y una prueba por contradicción para probar que un cierto número entero no puede ser extraño. De ahí que sea parejo. Completar la prueba de la proposición.
    
    Proposición. Vamos\(a \in \mathbb{Z}\). Si 2 divide a y 3 divide\(a\), entonces 6 divide\(a\).
    
    Prueba: Dejemos\(a \in \mathbb{Z}\) y asumamos que 2 divide\(a\) y 3 divide\(a\). Demostraremos que 6 divide\(a\). Dado que 3 divide\(a\), existe un entero\(n\) tal que
    \[a = 3n.\]
    El entero\(n\) es par o es impar. Demostraremos que debe ser parejo obteniendo una contradicción si se supone que es extraña. Entonces, supongamos que eso\(n\) es extraño. (Ahora complete la prueba.)
23. Los dos últimos dígitos de un entero grande.
    Observe que 7, 381, 272\(\equiv\) 72 (mod 100) desde 7, 381, 272 - 72 = 7, 381, 200, que es divisible por 100. En general, si empezamos con un entero cuya representación decimal tiene más de dos dígitos y restamos el entero formado por los dos últimos dígitos, el resultado será un entero cuyos dos últimos dígitos son 00. Este resultado será divisible por 100. Por lo tanto, cualquier entero con más de 2 dígitos es congruente módulo 100 al entero formado por sus dos últimos dígitos.
    
    (a) Empezar por cuadrar ambos lados de la congruencia\(3^4 \equiv 81\) (mod 100) para probarlo\(3^8 \equiv 61\) (mod 100) y luego probarlo\(3^{16} \equiv 21\) (mod 100). ¿Qué le dice esto sobre los dos últimos dígitos en la representación decimal de\(3^{16}\)?
    (b) Utilizar las dos congruencias de la Parte (23a) y las leyes de los exponentes para determinar\(r\) dónde\(3^{20} \equiv r\) (mod 100) y\(r \in \mathbb{Z}\) con\(0 \le r < 100\). ¿Qué le dice esto sobre los dos últimos dígitos en la representación decimal de\(3^{20}\)?
    (c) Determinar los dos últimos dígitos en la representación decimal de\(3^{400}\).
    (d) Determinar los dos últimos dígitos en la representación decimal de\(4^{804}\).
    Pista: Una forma es determinar los “valores mod 100”, para,\(4^2\),\(4^4\),\(4^8\),\(4^{16}\),\(4^{32}\),\(4^{64}\), y así sucesivamente. Después usa estos valores y leyes de exponentes para determinar\(r\), dónde\(4^{804} \equiv r\) (mod 100) y\(r \in \mathbb{Z}\) con\(0 \le r < 100\).
    (e) Determinar los dos últimos dígitos en la representación decimal de\(3^{3356}\).
    (f) Determinar los dos últimos dígitos en la representación decimal de\(7^{403}\).

Contestar

Agrega textos aquí. No elimine primero este texto.