Teoría de Números - Tarea núm. 5

(para entregar el jueves 27 de sept, 2001)

Definiciones vistas en la clase:

Sea N un entero > 1. Se dice que dos enteros a, b son congruentes (mod N) si N divide a a - b.
La clase de congruencia (mod N) de un entero a se define como el conjunto [a] de todos los enteros que son congruentes con a (mod N).
El conjunto de las clases de congruencias (mod N) se denota por Z_N. (Es el grupo cociente Z / NZ).
Se dice que una clase [a] en Z_N es invertible si a tiene una inversa (multiplicativa) (mod N); o sea, existe un entero b tal que ab es congruente con 1 (mod N).
Al conjunto de las clases de congruencia invertibles en Z_N se denota por Z_N^*. El número de elementos en Z_N^* se denota por fi(N) (la función tociente de Euler.)
Se dice que una clase [a] en Z_N^* es primitiva si genera a todo Z_N^*; o sea, si Z_N^*={ [aⁿ] | n en Z}.
Sea N un entero mayor que 1 y a un entero primo relativo con N. Se define el orden de a (mod N) como el mínimo entero positivo n tal que aⁿ es congruente con 1 (mod N). (Es tambien el orden del subgrupo de Z_N^* generado por la clase de congruencia de a).
Un conjunto A con una operacion m: A x A -> A se llama un grupo abeliano si
1. m(m(a, b), c) = m(a, m(b, c)), para todo a, b, c en A.
2. m(a, b) = m(b, a) para todo a, b en A.
3. Existe un elemento e en A tal que m(a, e) = a para todo a en A.
4. Para cada a en A existe un b en A tal que m(a, b) = e (b es el inverso de a y se denota por a^-1).
Un subconjunto B de un grupo abeliano A se llama un subgrupo si está cerrado bajo multiplicación e inversa. Para un subgrupo B el grupo cociente A/B se define como el conjunto de las clases de equivalencia de la relación a ~ a' ssi a/a' está en B, y la multiplicacion inducida por la de A.

Algunas afirmaciones vistas en la clase:

Z_N^* es un grupo (con respecto a la operación de multiplicación módulo N).
Si N es un entero mayor que 1 y a es un entero primo relativo con N entonces a es invertible (mod N).
El orden de un elemento de Z_N^* divide al número de elementos en Z_N^*.
Sea p un primo. Entonces el número de elementos en Z_p^* es p - 1.
Sea b un entero mayor que 1 y p un primo. Consideramos el desarrollo de un racional q/p en la base b, donde 0 < q < p (en la clase vimos b=10, p=13). Entonces el desarrollo es periódico con periodo el orden de b (mod p).

Problemas

Demuestra que si a y a' son congruentes (mod N), y b y b' son congruentes (mod N), entonces ab y a'b' son congruentes (mod N), y a+b y a' + b' son congruentes (mod N).
Demuestra que la multiplicación en Z_N dada por [a][b]:=[ab] está bien definida (no depende de los representantes de las clases de congruencia).
Sea N un entero mayor que 1 y a un entero invertible (mod N). Demuestra que a y N son primos relativos.
Encuentra a todas las clases primitivas en Z₁₃^*.
(Opcional) Demostrar las siguientes dos propiedades de la función tociente de Euler:
1. fi( p^a ) = p^a - p^{a -}1, para todo primo p y entero positivo a.
2. fi(ab)=fi(a) fi(b), para todo a, b enteros positivos primos relativos.
Sugerencias: para (1), demuestra que el número de elementos no invertibles en Z_{p ^a}, o sea los elementos divisibles por p, es p^{a -}1. Para (2), demuestra que la aplicación Z_ab^* --> Z_a^* x Z_b^* dada por x |--> (x mod a, x mod b) está bien definida y define un isomorfismo de grupos.
¿Cuántos elementos hay en Z₁₀₀^* ?
Encuentra el inverso de 3 mod 1000.
Sea N un entero mayor que 1 y a un entero primo relativo con N. Denotamos por f el número de elementos en Z_N^*.
1. Demuestra que a ^f es congruente con 1 (mod N). (Esto es el famoso "Teorema de Euler-Fermat").
  Sugerencia: recuerda que el orden de a divide a f.
2. Demuestra que si N es libre de cuadrados (no tiene divisor cuadrado mayor que 1; o en otras palabras, es un producto de primos distintos), entonces para cualquier dos enteros positivos n₁, n₂, a ^n₁ es congruente con a ^n₂ (mod N) si n₁ es congruente con n₂ (mod f).
  Solución
3. (Opcional) ¿Será cierto el inciso anterior cuando a no es primo relativo con N?
4. Encuentra una potencia de 3 que termina con 01.