Voy a asumir el siguiente resultado estándar.
Teorema [matemáticas] 1 [/ matemáticas] . Para cualquier par de enteros [matemática] m [/ matemática], [matemática] n [/ matemática], ambos distintos de cero, existen enteros [matemática] r [/ matemática], [matemática] s [/ matemática] tal que
[matemáticas] \ gcd (m, n) = mr + ns [/ matemáticas].
Corolario. Si [matemática] a [/ matemática], [matemática] b [/ matemática], [matemática] m [/ matemática] son números enteros tales que [matemática] \ gcd (a, m) = \ gcd (b, m) = 1 [/ math], luego [math] \ gcd (ab, m) = 1 [/ math].
- ¿Cuál es el resto de 57 ^ 67 ^ 77/17?
- ¿Cuántos enteros positivos ‘n’ se pueden formar a partir de los dígitos 3,4,4,5,5,6,7 si n debe ser mayor que 5,000,000?
- ¿Hay una explicación laica de la prueba de Andrew Wiles del último teorema de Fermat?
- ¿Qué es la aritmética modular?
- ¿Cuáles son las propiedades de los números primos y racionales?
Prueba [matemáticas] 1 [/ matemáticas] . [matemáticas] ([/ matemáticas] Usando el teorema [matemáticas] 1) [/ matemáticas] Elija enteros [matemática] r [/ matemática], [matemática] s [/ matemática] tal que [matemática] ar + ms = 1 [/ matemática] y enteros [matemática] t [/ matemática], [matemática] u [/ matemática] tal que [matemática] bt + mu = 1 [/ matemática]. Tenga en cuenta que la existencia de estos cuatro enteros está garantizada por el Teorema [matemática] 1 [/ matemática]. Multiplicar las dos ecuaciones produce
[matemática] 1 = (ar + ms) (bt + mu) = ab (rs) + m (aru + bst + msu) [/ matemática].
Se deduce que si [math] d \ mid ab [/ math] y [math] d \ mid m [/ math], entonces [math] d \ mid 1 [/ math]. Entonces, si [math] d> 0 [/ math], entonces [math] d = 1 [/ math]. Por lo tanto, [math] \ gcd (ab, m) = 1 [/ math]. [matemáticas] \ blacksquare [/ matemáticas]
Prueba [matemáticas] 2 [/ matemáticas]. [matemática] ([/ matemática] Prueba directa [matemática]) [/ matemática] Si [matemática] \ gcd (ab, m)> 1 [/ matemática], debe existir una prima [matemática] p [/ matemática] tal que [matemáticas] p \ mid ab [/ matemáticas] y [matemáticas] p \ mid m [/ matemáticas]. Como [math] p \ mid ab [/ math] implica [math] p \ mid a [/ math] o [math] p \ mid b [/ math], esto lleva a divisiones [math] p [/ math] tanto [matemática] a [/ matemática] como [matemática] m [/ matemática] o [matemática] p [/ matemática] divide tanto [matemática] b [/ matemática] como [matemática] m [/ matemática]. Cada uno es imposible porque [math] \ gcd (a, m) = \ gcd (b, m) = 1 [/ math]. Por lo tanto, [math] \ gcd (ab, m) = 1 [/ math]. [matemáticas] \ blacksquare [/ matemáticas]
Teorema. El conjunto [math] {\ mathbb Z} _p = \ {\ overline {1}, \ overline {2}, \ overline {3}, \ ldots, \ overline {p-1} \} [/ math] forma un grupo bajo módulo de multiplicación [matemática] p [/ matemática].
Observación. Este grupo es cíclico .
Denominemos el módulo de multiplicación de operación [math] p [/ math] por [math] {\ oplus} _p [/ math]. Recuerde que [matemáticas] \ overline {a} \: {\ oplus} _p \: \ overline {b} = \ overline {c} [/ math] si y solo si [math] ab \ equiv c \ pmod {p} [/matemáticas].
Deje [math] \ overline {a}, \ overline {b} \ in {\ mathbb Z} _p [/ math], y suponga que [math] \ overline {a} \: {\ oplus} _p \: \ overline { b} = \ overline {0} [/ math]. Entonces [math] p \ mid ab [/ math], de modo que [math] p \ mid a [/ math] o [math] p \ mid b [/ math]. Por lo tanto, [matemática] \ overline {a} = \ overline {0} [/ math] o [math] \ overline {b} = \ overline {0} [/ math], y esto es imposible ya que [math] \ overline { 0} \ notin {\ mathbb Z} _p [/ math].
Por lo tanto, [matemática] \ overline {a} \: {\ oplus} _p \: \ overline {b} \ en {\ mathbb Z} _p [/ math] siempre que [math] \ overline {a}, \ overline {b} \ en {\ mathbb Z} _p [/ math].
Por lo tanto, [math] {\ oplus} _p [/ math] define una operación binaria en [math] {\ mathbb Z} _p [/ math].
De [math] a (bc) = (ab) c [/ math] válido para [math] a, b, c \ in \ mathbb Z [/ math] se deduce que [math] {\ oplus} _p [/ math ] es asociativo .
De [math] a \ cdot 1 = 1 \ cdot a = a [/ math] válido para [math] a \ in \ mathbb Z [/ math] se deduce que [math] \ overline {a} \: {\ oplus } _p \: \ overline {1} = \ overline {1} \: {\ oplus} _p \: \ overline {a} = \ overline {a} [/ math]. Por lo tanto, [math] \ overline {1} [/ math] es el elemento de identidad en [math] {\ mathbb Z} _p [/ math].
Deje [math] \ overline {a} \ in {\ mathbb Z} _p [/ math]. Entonces [math] \ gcd (a, p) = 1 [/ math], y entonces existen enteros [math] r [/ math], [math] s [/ math] tal que [math] ar + ps = 1 [/matemáticas]. Por lo tanto, [math] ra = ar \ equiv 1 \ pmod {p} [/ math], y así [math] \ overline {a} \: {\ oplus} _p \: \ overline {r} = \ overline {r} \: {\ oplus} _p \: \ overline {a} = \ overline {1} [/ math]. Por lo tanto, [math] \ overline {r} [/ math] es el inverso de [math] \ overline {a} [/ math] en [math] {\ mathbb Z} _p [/ math].
Por lo tanto, [math] \ big ({\ mathbb Z} _p, {\ oplus} _p \ big) [/ math] es un grupo . [matemáticas] \ blacksquare [/ matemáticas]