• Categories
• Álgebra abstracta
• Teoría de números
• Matemática discreta
• Teoría de anillos
• Números

Citation preview

Problemas resueltos sobre Aritm´etica Modular parte I J. Armando Velazco 30 de abril de 2013

Ejercicio Muestre que La relaci´on a ≡ b (mod m) es una relaci´on de equivalencia en Z. Soluci´ on Sean, a, b, c, m 6= 0 ∈ Z s´olo hay que probar que tal relaci´on es i) Reflexiva: a ≡ a (mod m) ⇔ m | (a − a) ⇔ m | 0. ii) Sim´etrica: a ≡ b (mod m) ⇔ m | (a − b) ⇔ m | −(b − a) ⇔ b ≡ a (mod m) iii) Transitiva: Suponga a ≡ b (mod m) y b ≡ c (mod m) Entonces a − c = (a − b) + (b − c) = k1 m + k2 m = (k1 + k2 )m ⇔ a ≡ c (mod m) As´ı, la relaci´ on es una relaci´on de equivalencia. ⋄ Ejercicio Mostrar que n3 − n es divisible por 3 para todo n ∈ N. Soluci´ on Notemos que: n3 −n es divisible por 3 si n3 ≡ n mod 3, que es nuestra definici´on de congruencia; entonces, un posible camino a la soluci´on es este: A partir del hecho n3 −n = n(n2 −1) s´olo 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 ∈ Z, por ejemplo, sea r = 2 entonces, tenemos que n = 3k + 2 lo que implica que n(n2 − 1) = (3k + 2)[(3k + 2)2 − 1] que es evidentemente divisible por 3. Cuando r = 1 el an´alisis es completamente an´alogo y podemos concluir el resultado.⋄ P Ejercicio Hallar el residuo de 100 i=1 i! cuando es dividido por 10. Soluci´ on Tome en cuenta que la funci´ on factorial es definida por n! = n(n − 1)(n − 2)...(2)(1) y a partir de esto, observemos tambi´en que a partir de n=5, 10 ser´a factor com´ un de cada sumando (pues en part´ıcular 5! = [(2)(5)](4)(3)(1)) en adelante, luego entonces 1! ≡ 2! ≡

1!(mod 10) 2!(mod 10)

3! ≡ 4! ≡

3!(mod 10) 4!(mod 10)

5! ≡ 6! ≡ .. .

0(mod 10) 0(mod 10)

100! ≡

0(mod 10)

1

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

i! ≡ (1! + 2! + 3! + 4! +

100 X

0) (mod 10)

i=5

i=1

De donde, de la definici´on de congruencia, tenemos que el residuo es entonces r = (1! + 2! + 3! + 4!)(mod 10) = 33(mod 10) = 3 Por lo que el residuo buscado es 3. ⋄ Ejercicio ¿Cu´ al ser´a el d´ıgito final de un entero elevado a la cuarta potencia en base 10? Soluci´ on Sea k ∈ Z entonces, en base 10 k=

n X

10i ai , ai ∈ {0, 1, 2, . . . , 9}

i=0

Por lo que

n X 10i ai + a0 )4 k4 = ( i=1

Por lo que cuando

a40

no sea divisible por 10 tendremos residuos, esto es en s´ı 14 ≡ 34 ≡ 74 ≡ 94 ≡ 1 mod(10) 24 ≡ 44 ≡ 64 ≡ 84 ≡ 6 mod(10)

Y por u ´ltimo 54 ≡ 5 mod(10) por lo que el d´ıgito final puede ser 0,1,5 ´o 6. ⋄ Ejercicio Se define un sistema completo de residuos m´odulo m, S.C.R(m) por S.C.R(m) := {r1 , r2 , . . . , rq ∈ Z : k ∈ Z ⇒ k ≡ ri mod(m)} Para alg´ un i ∈ {1, 2, . . . , q}. Pruebe que si ri , rj ∈ S.C.R(m), i 6= j, ⇒ ri 6≡ rj mod(m). Soluci´ on Suponga que ri , rj ∈ S.C.R(m), ri 6= rj , ri ≡ rj mod(m) entonces, sin p´erdida de generalidad, tome un entero k tal que k ≡ ri mod(m) ⇒ k ≡ rj mod(m) Pero, por definici´on de S.C.R(m) se tendr´ıa entonces que i = j. ⋄ Ejercicio Proporcione 2 S.C.R(13).

2

Soluci´ on De la definici´on tenemos que {0, 1, 2, . . . , m − 1} es un S.C.R(m). Como aplicaci´on podemos tener un sistema completo de residuos m´odulo 13, S.C.R(13) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} pero tambi´en, el conjunto {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25} forman un S.C.R(13).⋄ Ejercicio Usando la definici´on de Sistema Reducido de Residuos m´odulo m, S.R.R(m), muestre que {1, 2, 4, 5, 7, 8} Es S.R.R(9). Soluci´ on La definici´on de un S.R.R(m) es: Un conjunto de enteros obtenido de un S.C.R(m) eliminando todos los xi que son divisores de cero en Zm y al elemento que es congruente con cero m´odulo m. As´ı tenemos que 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 · 3 = 9 ≡ 0(mod m) el elemento congruente con cero es cero (o 9) por lo que al eliminarlos tenemos que 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. ⋄ Ejercicio ¿Cu´ ales son los divisores de cero en el S.C.R(30) = {0, 1, 2, . . . , 29}? Soluci´ on Los divisores de cero son, precisamente, aquellos elementos tales que (xi , 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. ⋄ Definici´ on El n´ umero de enteros positivos menor o igual a m tales que son primos relativos con m es denotado por φ(m), donde φ es llamada la funci´ on indicatriz de Euler o la φ-funci´on de Euler. Ejercicio Suponga (m, n) = 1, r ∈ Z. Entonces los n enteros {r, r + m, r + 2m, . . . , r + (n − 1)m} forman un S.C.R(n). Soluci´ on En general, un S.C.R(m) tiene m elementos, por lo que s´olo necesitamos probar entonces que dos cualesquiera elementos del conjunto dado son incongruentes m´odulo n, supongamos lo contrario, es decir que existen 2 elementos del conjunto que son congruentes, digamos r + km ≡ r + lm (mod n) 3

Entonces, de las propiedades de las congruencias tenemos que m(k − l) ≡ 0 (mod n) ⇔ n | (k − l) ⇒!! Pues |k − l| < n, as´ı el conjunto dado es un S.C.R(n). ⋄. Ejercicio Suponga (m, n) = 1, (M, n) = 1, r ∈ 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 r + M nu + nv forman un S.C.R(mn). Soluci´ on Tomando la idea del ejercicio anterior podemos, veremos que 2 elementos cualesquiera del conjunto {r + M nu + nv : u ∈ S.C.R(n), v ∈ S.C.R(m)} no son congruentes, para ello suponga que si hay dos elementos congruentes, digamos r + M nu + nv ≡ r + M nu′ + nv ′ (mod mn) Entonces tenemos que M m(u − u′ ) + n(v − v ′ ) ≡ 0 (mod mn) ⇔ n | (u − u′ ); m | (v − v ′ ) ⇒!! Pues tanto u como v se encuentran en sistemas de residuos de m´odulo n y m respectivamente. ⋄.

4