Teoría de Números

Question 1

Definición de la relación divide

a|b

Answer 1

a|b ssi ∃ k ∈ ℤ tal que b = ka

Question 2

Definición de relación equivalencia módulo n

a ≡ₙ b

Answer 2

a ≡ₙ b ssi n | (b - a)

(b - a) es divisible por n

Question 3

Fundación de la aritmética modular

Answer 3

ℤₙ = ℤ / ≡ₙ
[i] + [j] = [i + j]
[i] ⋅ [j] = [i ⋅ j]

[a] se renombra como simplemente a

Question 4

La operación módulo está definida como

a mod n

Answer 4

El resto de dividir a por n

a % n

Question 5

Redefinición de la aritmética modular en base a la operación módulo

Answer 5

ℤₙ = ℤ / ≡ₙ
[i] + [j] = (i + j) mod n
[i] ⋅ [j] = (i ⋅ j) mod n

Question 5

Con la operación módulo, todo número puede ser descompuesto en términos de n con la forma…

Answer 5

a = α ⋅ n + β

Donde α es la división entera y β el resto

Alternativamente, β = (a mod n)

Question 6

Algoritmo euclidiano

Answer 6

Question 7

Identidad de Bezout

Answer 7

Dado d = gcd(a, b) existen x, y tal que ax + by = d

Question 8

Primos relativos

o coprimos

Answer 8

Cuando gcd(x, y) = 1

Question 9

Algoritmo extendido para GCD

Answer 9

Question 10

Identidad de Bezout para coprimos

Answer 10

Question 11

Definición de inverso modular

Answer 11

b es inverso de a en módulo n si a ⋅ b ≡ₙ 1

Puede ser denotado a⁻¹

Question 12

¿Cuándo existe el inverso modular?

Answer 12

Cuando gcd(a, n) = 1

Es decir, a y n son coprimos

Esto yace de que a ⋅ b ≡ₙ 1 puede ser reescrito como a ⋅ b - k ⋅ n = 1 para algun k, lo que es la identidad de bezout con coprimos a, n

Question 13

¿Cómo encontrar el inverso modular?

Answer 13

Usando el algoritmo euclidiano extendido

s ⋅ a + t ⋅ n = 1
Donde s es el inverso de n en módulo n

Question 14

Notación equivalente a…

a ≡ b  (mod n)

Answer 14

a ≡ₙ b

Question 15

Notación equivalente a…

a ≡ₙ b

Answer 15

a ≡ b  (mod n)

Question 16

Forma de una ecuación de congruencia lineal

Answer 16

ax ≡ b  (mod n)

Donde n ∈ ℕ − {0}, a, b ∈ ℤ y x es una variable

Question 17

En una ecuación de congruencia lineal, si a y n son primos relativos, entonces…

Answer 17

ax ≡ b  (mod n) tiene solución en ℤₙ

Question 18

¿Cómo resolver una ecuación de congruencia lineal?

Answer 18

Dado ax ≡ b  (mod n), encontramos a⁻¹ y multiplicamos por ambos lados.

Esto nos da x ≡ a⁻¹ ⋅ b   (mod n)

Si es que esto no está disponible, dividir por gcd(a, n) los tres terminos de la ecuacion para ponerlo en la forma correcta, asumiendo que b sea divisible por gcd(a, n). Luego x_i = x’ + i + n’ (mod n) donde i es 1..gcd(a,n)

Question 19

Ecuación de congruencia lineal que representa el inverso modular

Answer 19

ax ≡ 1  (mod n)

Question 20

Teorema Chino del Resto

Answer 20

Para un sistema de congruencias lineales sobre la misma variable en distintos módulos, existe una solución siempre que los módulos sean emparejadamente coprimos

Question 21

Demostración del Teorema Chino del Resto

Answer 21

1. Existencia: Construcción directa por medio de Σ xᵢ Nᵢ bᵢ donde xᵢ inverso a Nᵢ en mod nᵢ
2. Unicidad: Contradicción al establecer transitividad entre dos soluciones hasta llegar a que son la misma solución