Teoría de Números Flashcards
Definición de la relación divide
a|b
a|b ssi ∃ k ∈ ℤ tal que b = ka
Definición de relación equivalencia módulo n
a ≡ₙ b
a ≡ₙ b ssi n | (b - a)
(b - a) es divisible por n
Fundación de la aritmética modular
ℤₙ = ℤ / ≡ₙ
[i] + [j] = [i + j]
[i] ⋅ [j] = [i ⋅ j]
[a] se renombra como simplemente a
La operación módulo está definida como
a mod n
El resto de dividir a por n
a % n
Redefinición de la aritmética modular en base a la operación módulo
ℤₙ = ℤ / ≡ₙ
[i] + [j] = (i + j) mod n
[i] ⋅ [j] = (i ⋅ j) mod n
Con la operación módulo, todo número puede ser descompuesto en términos de n con la forma…
a = α ⋅ n + β
Donde α es la división entera y β el resto
Alternativamente, β = (a mod n)
Algoritmo euclidiano
Identidad de Bezout
Dado d = gcd(a, b) existen x, y tal que ax + by = d
Primos relativos
o coprimos
Cuando gcd(x, y) = 1
Algoritmo extendido para GCD
Identidad de Bezout para coprimos
Definición de inverso modular
b es inverso de a en módulo n si a ⋅ b ≡ₙ 1
Puede ser denotado a⁻¹
¿Cuándo existe el inverso modular?
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
¿Cómo encontrar el inverso modular?
Usando el algoritmo euclidiano extendido
s ⋅ a + t ⋅ n = 1
Donde s es el inverso de n en módulo n
Notación equivalente a…
a ≡ b (mod n)
a ≡ₙ b
Notación equivalente a…
a ≡ₙ b
a ≡ b (mod n)
Forma de una ecuación de congruencia lineal
ax ≡ b (mod n)
Donde n ∈ ℕ − {0}, a, b ∈ ℤ y x es una variable
En una ecuación de congruencia lineal, si a y n son primos relativos, entonces…
ax ≡ b (mod n) tiene solución en ℤₙ
¿Cómo resolver una ecuación de congruencia lineal?
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)
Ecuación de congruencia lineal que representa el inverso modular
ax ≡ 1 (mod n)
Teorema Chino del Resto
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
Demostración del Teorema Chino del Resto
- Existencia: Construcción directa por medio de Σ xᵢ Nᵢ bᵢ donde xᵢ inverso a Nᵢ en mod nᵢ
- Unicidad: Contradicción al establecer transitividad entre dos soluciones hasta llegar a que son la misma solución
