Algebra Superior, 7.10.99.

Tarea No. 9 (Para entregar el 21 de Oct. 99)

1. Hacer tablas de multiplicación (mod n) para 2 ≤ n ≤ 9.

2. Se dice que un entero a es invertible (mod n) si existe un entero b tal que ab ≡ 1 (mod n). Se dice que b (en caso que existe) es una inversa (o reciproco) de a (mod n). Notacion: b ≡ \frac{1}{a} (mod n).

(a) Usando las tablas que construiste en el problemas anterior, encuentra para cada n en el rango 2 ≤ n ≤ 9, cuales son los números invertibles en el rango {0, 1, …, n − 1}.

(b) Sean a, a′ dos enteros congruentes (mod n). Demuestra que a es invertible (mod n) si y solo si a′ es invertible (mod n). Concluye que el adjetivo “invertible (mod n)” se puede aplicar, sin ambiguedad, a una clase de congruencia (mod n).

(c) Sean a, a′ dos enteros congruentes (mod n). Demuestra que (a, n) = (a′, n). Concluye que el adjetivo “prima relativa (mod n)” se puede aplicar, sin ambiguedad, a una clase de congruencia (mod n).

(d) Demuestra que una clase de congruencia (mod n) es invertible (mod n) si y solo si es prima relativa a n.

3. Sea n un entero ≥ 2. Definimos a ϕ(n) como el número de clases de congruencia invertibles (mod n). (Se conoce a ϕ como “la función de Euler.”)

(a) Calcula ϕ(n) para 2 ≤ n ≤ 9.

(b) Demuestra que ϕ(p) = p − 1 para p primo.

(c) Calcula el ϕ(p^{k}) para p primo, k ≥ 1.

(d) Demuestra que ϕ(nm) = ϕ(n)ϕ(m) para todo n, m ≥ 2 que son primos relativos.

(e) Calcular ϕ(1000000).