Fundamentos de Aritmética Modular y Complejidad Algorítmica

Teoría de Números

Teorema 12.7: Teorema Chino del Resto

Sean a₁, a₂, ..., a_n ∈ ℤ y p₁, p₂, ..., p_n ∈ ℤ tales que (p_i, p_j) = 1 si i ≠ j. Entonces:

• i) Existe a ∈ ℤ tal que a ≡ a_i (mod p_i), ∀i = 1, 2, ..., n.
• ii) Si ∃ a' ∈ ℤ tal que a' ≡ a_i (mod p_i), ∀i = 1, 2, ..., n, ⇒ a ≡ a' (mod p₁ · p₂ · ... · p_n).

Ecuaciones Diofánticas

Una ecuación diofántica es una ecuación de la forma: ax + by = c, donde a, b, c ∈ ℤ - {0} y se buscan soluciones enteras.

Teorema 11.7: Teorema de Caracterización

Sean a, b, c ∈ ℤ - {0} y d = mcd(a, b). Entonces, la ecuación ax + by = c admite solución en ℤ si y sólo si d | c; es decir, si existe k en ℤ tal que c = d · k.

Teorema Fundamental de la Aritmética

Todo número entero distinto de ±1 y 0 admite una descomposición única (salvo el orden y opuestos) como producto de números primos positivos, es decir: ∀a ∈ ℤ - {0, ±1}, a = ±p₁^α₁ · p₂^α₂ · ... · p_n^α_n con p_i < p_j si i < j.

Teorema Fundamental de la Numeración

Sea b ≥ 2 un número entero. Cualquier entero positivo n se puede escribir de forma única en base b como:

n = d_kb^k + ... + d₂b² + d₁b¹ + d₀b⁰

Con d_i ∈ ℕ y 0 ≤ d_i < b, ∀i = 0, 1, ..., k. Para abreviar, escribiremos n = (d_k d_k-1 ... d₁ d₀)_b.

Complejidad Algorítmica

• Algoritmo: Conjunto finito de instrucciones precisas que resuelven un problema o realizan un cálculo.
• Complejidad en tiempo: Número de operaciones que tiene que realizar el algoritmo.
• Tratable: Decimos que un problema es tratable si se puede resolver usando un algoritmo con complejidad polinómica en el peor caso.
• Intratable: Decimos que un problema es intratable si no se puede resolver usando un algoritmo con complejidad polinómica en el peor caso.
• Resolubles: Decimos que un problema es resoluble si se puede probar que existen algoritmos que pueden resolverlo.
• Irresolubles: Decimos que un problema es irresoluble si se puede probar que no existen algoritmos que puedan resolverlo.

Notación Asintótica

• f(x) es O(g(x)): Decimos que f(x) es O(g(x)) si y sólo si ∃ c, k constantes tales que |f(x)| ≤ c|g(x)| ∀ x > k.
• f(x) es Ω(g(x)): Decimos que f(x) es Ω(g(x)) si y sólo si ∃ c, k constantes tales que |f(x)| ≥ c|g(x)| ∀ x > k.
• f(x) es Θ(g(x)): Decimos que f(x) es Θ(g(x)) si f(x) es O(g(x)) y Ω(g(x)). Decimos que f(x) es Θ(g(x)) si podemos encontrar dos números reales C₁ y C₂ y un positivo k tal que: C₁|g(x)| ≤ |f(x)| ≤ C₂|g(x)| ∀ x > k.