Problemas resueltos sobre aritmética modular – Parte I

Con este post quiero iniciar una serie de ejercicios sencillos, pero que proporcionen técnicas para utilizar la teoría, algunos son bastante elementales o rutinarios, pero la idea es ir adquiriendo técnicas que permitan complementar y comprender mejor la teoría.

EJERCIOS RESUELTOS ARITMETICA MODULAR PARTE I – VERSION PDF

Ejercicio 1 Muestre que La relación {a \equiv b\, (mod\,m)} es una relación de equivalencia en {\mathbb{Z}}.

Sean, {a,b,c,m \neq 0 \, \in \mathbb{Z}} sólo hay que probar que tal relación es

  • i) Reflexiva: {a \equiv a \, (mod\, m) \Leftrightarrow m \mid (a-a) \Leftrightarrow m \mid 0}.
  • ii) Simétrica: {a \equiv b\, (mod\, m) \Leftrightarrow m \mid (a-b) \Leftrightarrow m \mid -(b-a) \Leftrightarrow b \equiv a\, (mod\, m) }
  • iii)Transitiva: Suponga {a \equiv b \, (mod\, m)} y {b \equiv c \, (mod\, m)} Entonces

    \displaystyle a-c=(a-b)+(b-c)=k_1 m + k_2 m = (k_1 + k_2)m \Leftrightarrow a\equiv c\, (mod\, m)

Así, la relación es una relación de equivalencia. {\diamond}

Ejercicio 2 Mostrar que {n^{3}-n} es divisible por 3 para todo {n\in \mathbb{N}}.

Notemos que: {n^{3}-n} es divisible por 3 si {n^{3}\equiv n} mod {3}, que es nuestra definición de congruencia; entonces, un posible camino a la solución es este: A partir del hecho {n^{3}-n = n(n^{2}-1)} sólo hay que analizar el caso de no ser divisible {n} por 3, pues, por el algoritmo de Euclides, se tiene que {n=3k+r} donde {r=1} o {r=2} y {k\in \mathbb{Z}}, por ejemplo, sea {r=2} entonces, tenemos que {n=3k+2} lo que implica que {n(n^{2}-1)=(3k+2)[(3k+2)^{2}-1]} que es evidentemente divisible por 3. Cuando {r=1} el análisis es completamente análogo y podemos concluir el resultado.{\diamond}

Ejercicio 3 Hallar el residuo de {\sum_{i=1}^{100}{i!}} cuando es dividido por 10.

Tome en cuenta que la función factorial es definida por

\displaystyle n!=n(n-1)(n-2)...(2)(1)

y a partir de esto, observemos también que a partir de n=5, 10 será factor común de cada sumando (pues en partícular {5!=[(2)(5)](4)(3)(1)}) en adelante, luego entonces

\displaystyle \begin{array}{rcl} 1! & \equiv & 1! (mod\, 10) \\ 2! & \equiv & 2! (mod\, 10) \\ 3! & \equiv & 3! (mod\, 10) \\ 4! & \equiv & 4! (mod\, 10) \\ 5! & \equiv & 0 (mod\, 10) \\ 6! & \equiv & 0 (mod\, 10) \\ & \vdots & \\ 100! & \equiv & 0 (mod\, 10) \end{array}

Ahora, debido a la estructura que tienen las clases de congruencias, podemos sumar estas y obtener:

\displaystyle \sum_{i=1}^{100}{i!} \equiv (1!+2!+3!+4! + \sum_{i=5}^{100}{0}) \, (mod\, 10)

De donde, de la definición de congruencia, tenemos que el residuo es entonces

\displaystyle r=(1! + 2! +3! + 4!) (mod\, 10) = 33 (mod\, 10) = 3

por lo que el residuo buscado es 3. {\diamond}

Ejercicio 4 \textquestiondown Cuál será el dígito final de un entero elevado a la cuarta potencia en base 10?

Sea {k \in \mathbb{Z}} entonces, en base 10

\displaystyle k=\sum\limits_{i=0}^{n}10^{i}a_{i},\; a_{i}\in \{0,1,2,\ldots , 9\}

Por lo que

\displaystyle k^{4}=(\sum\limits_{i=1}^{n}10^{i}a_{i} + a_{0})^{4}

Por lo que cuando {a_{0}^{4}} no sea divisible por 10 tendremos residuos, esto es en sí

\displaystyle 1^4 \equiv 3^4 \equiv 7^4 \equiv 9^4 \equiv 1\,mod(10)

\displaystyle 2^4 \equiv 4^4 \equiv 6^4 \equiv 8^4 \equiv 6\,mod(10)

Y por último {5^4 \equiv 5\, mod(10)} por lo que el dígito final puede ser 0,1,5 ó 6. {\diamond}

Ejercicio 5 Se define un sistema completo de residuos módulo {m}, {S.C.R(m)} por

\displaystyle S.C.R(m):=\{r_{1},r_{2},\ldots ,r_{q}\in \mathbb{Z}:k\in \mathbb{Z}\Rightarrow k \equiv r_{i}\; mod(m) \}

Para algún {i \in \{1,2,\ldots, q\}}. Pruebe que si {r_{i},r_{j} \in S.C.R(m), i\neq j, \Rightarrow r_{i} \not\equiv r_{j} \; mod(m)}.

Suponga que {r_{i},r_{j} \in S.C.R(m), r_{i}\neq r_{j}, r_{i}\equiv r_{j}\; mod(m)} entonces, sin pérdida de generalidad, tome un entero {k} tal que

\displaystyle k\equiv r_{i}\; mod(m) \Rightarrow k\equiv r_{j}\; mod(m)

Pero, por definición de {S.C.R(m)} se tendría entonces que {i=j}. {\diamond}

Ejercicio 6 Proporcione 2 {S.C.R(13)}.

De la definición tenemos que {\{ 0,1,2,\ldots , m-1 \}} es un {S.C.R(m)}. Como aplicación podemos tener un sistema completo de residuos módulo 13, {S.C.R(13)=\{0,1,2,3,4,5,6,7,8,9,10,11,12\}} pero también, el conjunto

\displaystyle \{1,3,5,7,9,11,13,15,17,19,21,23,25\}

forman un {S.C.R(13)}.{\diamond}

Ejercicio 7 Usando la definición de Sistema Reducido de Residuos módulo m, {S.R.R(m)}, muestre que

\displaystyle \{ 1,2,4,5,7,8 \}

Es {S.R.R(9)}.

La definición de un {S.R.R(m)} es: Un conjunto de enteros obtenido de un {S.C.R(m)} eliminando todos los {x_{i}} que son divisores de cero en {\mathbb{Z}_{m}} y al elemento que es congruente con cero módulo {m}. Así tenemos que

\displaystyle S.C.R(9)=\{ 0,1,2,3,4,5,6,7,8 \}

Los divisores de cero aquí son 3 y 6 (pues, por ejemplo {3\cdot 3 = 9 \equiv 0 (mod\, m)} el elemento congruente con cero es cero (o 9) por lo que al eliminarlos tenemos que

\displaystyle S.R.R(9)= \{ 1,2,4,5,7,8 \}

Como se quería. Algo importante a destacar de los {S.R.R(m)} es que siempre es un conjunto maximal de enteros que son primos relatimos con {m}. {\diamond}

Ejercicio 8 ¿Cuáles son los divisores de cero en el {S.C.R(30)=\{0,1,2,\ldots , 29 \}}?

Los divisores de cero son, precisamente, aquellos elementos tales que {(x_{i},m)>1} por lo tanto 2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,24,25,26,27,28 son divisores de cero. {\diamond}

Definición  El número de enteros positivos menor o igual a {m} tales que son primos relativos con {m} es denotado por {\phi(m)}, donde {\phi} es llamada la función indicatriz de Euler o la {\phi}-función de Euler.

Ejercicio 9 Suponga {(m,n)=1, \, r \in \mathbb{Z}}. Entonces los {n} enteros

\displaystyle \{r,r+m,r+2m, \ldots , r+(n-1)m \}

forman un {S.C.R(n)}.

En general, un {S.C.R(m)} tiene {m} elementos, por lo que sólo necesitamos probar entonces que dos cualesquiera elementos del conjunto dado son incongruentes módulo {n}, supongamos lo contrario, es decir que existen 2 elementos del conjunto que son congruentes, digamos

\displaystyle r+km \equiv r+lm \, (mod\, n)

Entonces, de las propiedades de las congruencias tenemos que

\displaystyle m(k-l) \equiv 0 \, (mod\, n) \Leftrightarrow n \mid (k-l) \Rightarrow !!

Pues {|k-l|<n}, así el conjunto dado es un {S.C.R(n)}. {\diamond}.

Ejercicio 10 Suponga {(m,n)=1}, {(M,n)=1, \, r \in \mathbb{Z}}, {u} tomando valores en un {S.C.R(n)} y {v} tomando valores en un {S.C.R(m)}. Muestre que los {mn} enteros de la forma

\displaystyle r+Mnu+nv

forman un {S.C.R(mn)}.

Tomando la idea del ejercicio anterior podemos, veremos que 2 elementos cualesquiera del conjunto

\displaystyle \{r+Mnu+nv:u\in S.C.R(n),\, v \in S.C.R(m) \}

no son congruentes, para ello suponga que si hay dos elementos congruentes, digamos

\displaystyle r+Mnu+nv \equiv r+Mnu'+nv' \, (mod \, mn)

Entonces tenemos que

\displaystyle Mm(u-u')+n(v-v') \equiv 0 \, (mod\, mn) \Leftrightarrow n\mid (u-u');\, m\mid (v-v') \Rightarrow !!

Pues tanto {u} como {v} se encuentran en sistemas de residuos de módulo {n} y {m} respectivamente. {\diamond}.

Saludos.

About these ads

2 pensamientos en “Problemas resueltos sobre aritmética modular – Parte I

Hey, hey ;) ¿Quieres comentar algo al respecto? Puedes utilizar código LaTeX: Sólo tienes que escribir $latex código-latex-que-quieras-insertar$.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s