Algebra Superior, 4.11.99

Tarea num. 12

Para entregar el 11 de nov. 99

1. (a) Sea n = pq donde p y q son dos primos distintos. Demuestra que a^{t+1} ≡ a (mod n) para todo a ∈ ℤ, donde t = (p − 1)(q − 1). (Sugerencia: escribe a = da_{1} donde (a_{1}, n) = 1 y d = (a, n). Puedes dividir en 4 casos segun d = 1, p, q o pq. Para el primer caso usa el teorema de Euler. Para el segundo caso demuestra que A ≡ B (mod q) ⟹ pA ≡ pB (mod pq). De aqui sigue que p^{t+1} ≡ p (mod n). Luego aplica el teorema de Euler para demostrar que a_{1}^{t+1} ≡ a_{1} (mod n).)

(b) Terminologia: un entero positivo n es “libre de cuadrado” (square-free, en ingles) si no es divisible por ningun cuadrado m^{2} > 1. Definición equivalente: en la factorización prima de n cada primo aparece con multiplicidad 1. Por ejemplo, 100 no es libre de cuadrado (porque 4 lo divide) pero 102 = 2 · 3 · 17 lo es. Demuestra que las dos definiciones son equivalentes.

(c) Demuestra que si n es libre de cuadrado entonces a^{t+1} ≡ a (mod n), donde t = ϕ(n). (Sugerencia: escribe a = da_{1} donde (a_{1}, n) = 1 y d = (a, n) = p_{1}p_{2} … p_{k}.)

(d) ^{∗} (Reto, opcional, no se como hacerlo). Encuentra la generalización del teorema de Euler para n y a general.

2. Sean a, b, n ∈ ℤ, n > 1. Demuestra los siguientes incisos:

(a) La congruencia ax ≡ b (mod n) tiene solución si y solo si (a, n)|b.

(b) Si (a, n)|b, la congruencia ax ≡ b (mod n) tiene exactamente (a, n) soluciones distintas (mod n).

3. (El “Teorema Chino de los Residuos”.) Sean m_{1}, …, m_{k} enteros > 1 tales que (m_{i}, m_{j}) = 1 si i ≠ j.

(a) Demuestra que para todos enteros b_{1}, …, b_{k} existe un entero x, único módulo m_{1}m_{2} ⋯ m_{k}, tal que x ≡ b_{i} (mod m_{i}), 1 ≤ i ≤ k. (Sugerencia: Sea n = m_{1}m_{2} ⋯ m_{k}, n_{i} = n/m_{i}. Demuestra que existe un x_{i} tal que n_{i}x_{i} ≡ b_{i} (mod m_{i}). Toma x = ∑_{i} n_{i}x_{i}. No se te olvide la unicidad.)

(b) ^{∗} (Opcional). Formular y demostrar un resultado similar acerca de las soluciones de un sistema de congruencias de la forma a_{i}x ≡ b_{i} (mod m_{i}), 1 ≤ i ≤ k.

4. Sea n un entero > 1, sean d_{1}, d_{2}, …, d_{r} sus divisores positivos y p_{1}, p_{2}, …, p_{s} sus divisores primos.

(a) Demuestra que n = ϕ(d_{1}) + ϕ(d_{2}) + … + ϕ(d_{r}).

Por ejemplo: 15 = ϕ(15) + ϕ(5) + ϕ(3) + ϕ(1) = 8 + 4 + 2 + 1.

(b) Demuestra que ϕ(n) = n (1 − \frac{1}{p_{1}} ) (1 − \frac{1}{p_{2}} ) ⋯ (1 − \frac{1}{p_{s}} ) .

Por ejemplo: 8 = ϕ(15) = 15 (1 − \frac{1}{3}) (1 − \frac{1}{5}) .

5. ^{∗} (Opcional). Un entero positivo se llama perfecto si es igual a la suma de sus divisores positivos menores que el. Por ejemplo, 6 = 3 + 2 + 1 es perfecto.

(a) Verfique que 28 y 496 son perfectos.

(b) Demuestra que un número par es perfecto si y solo si es de la forma 2^{p−1}(2^{p} − 1), donde p y 2^{p} − 1 son primos. (Nota: aun no se sabe si existe un número perfecto impar).

(c) Demuestra que 2,096,128 no es perfecto pero 33,550,336 lo es.