Sigue esta ruta para aprender teoría de números de manera progresiva. Los temas están ordenados por dificultad.
El estudio de los números enteros y sus propiedades.
Cuando un entero divide a otro exactamente, sin dejar residuo.
Enteros mayores a 1 que solo tienen como divisores al 1 y a ellos mismos.
Pruebas rápidas para saber si un número es divisible entre 2, 3, 4, 5, 6, 8, 9, 10 u 11.
a = bq + r, con 0 ≤ r < b.
Criterios básicos de divisibilidad.
El último dígito es par.
La suma de los dígitos es múltiplo de 3.
La suma de los dígitos es múltiplo de 9.
Los últimos dos dígitos son múltiplos de 4.
El último dígito es 0 o 5.
Divisible entre 2 y 3 a la vez.
Todo entero mayor a 1 tiene una factorización única en números primos.
Para a, b > 0, existen q y r únicos tales que a = bq + r con 0 ≤ r < b.
El entero más grande que divide tanto a 'a' como a 'b'.
Algoritmo para encontrar todos los números primos hasta n.
El entero positivo más pequeño que es divisible entre 'a' y 'b'.
Si fueran finitos, considera p1·p2·...·pn + 1.
Suma, resta y multiplicación mod n.
Usando factorización prima o el mcd.
Cualquier n > 1 se puede expresar como producto de primos.
Tachar los múltiplos de cada número primo.
Demostrando que q y r son únicos.
mcm(a,b) · mcd(a,b) = ab.
Criterios un poco más avanzados.
Uso de suma de dígitos y sumas alternadas.
(a + b) mod n = ((a mod n) + (b mod n)) mod n.
Varios criterios de prueba.
Reglas para (a × b) mod n.
Los últimos tres dígitos son múltiplos de 8.
Suma alternada de los dígitos.
Aritmética basada en los residuos de las divisiones.
Congruencias, clases de residuos, suma y multiplicación módulo n.
Hay infinitos números primos (prueba de Euclides y sus variantes).
Calculando σ(n) con la factorización prima.
φ(n) = n∏(1 - 1/p).
Hay soluciones si y solo si mcd(a,b)|c.
Cómo hallar las soluciones de ax ≡ b (mod n).
Calcular el mcd(a,b) mediante divisiones sucesivas: mcd(a,b) = mcd(b, a mód b).
Usando a=m²-n², b=2mn, c=m²+n².
aᵖ ≡ a (mod p) para cualquier primo p.
Usando el algoritmo de Euclides extendido.
Clases de equivalencia mod n.
Cómo sacar todas las soluciones de una sola.
τ(n) = (a1+1)(a2+1)...
Usar la criba para contar cuántos primos hay hasta n.
La factorización es única, sin importar el orden.
mcd(a,b) = ax + by.
Usando Legendre para calcular v₅(n!).
Ternas donde el mcd(a,b,c)=1.
Hallar a⁻¹ mod n cuando mcd(a,n)=1.
Números donde σ(n) = 2n.
Reducir exponentes usando mod p-1.
A partir de (m²-n²)² + (2mn)² = (m²+n²)².
a^k ≡ a^(k mod (p-1)) mod p.
a⁻¹ existe si y solo si mcd(a,n) = 1.
x = x₀ + (b/d)t, y = y₀ - (a/d)t.
ax + by = c tiene solución si mcd(a,b) divide a c.
φ(p) = p - 1.
min(v₂(n!), v₅(n!)) = v₅(n!).
Primero hallar ax + by = mcd(a,b).
φ(p^k) = p^k - p^(k-1).
Calcular n^k mod 10 o mod 100.
Multiplicar ternas primitivas por k.
Algoritmo de Euclides extendido.
φ(n) = n × ∏(1 - 1/p).
Exponenciación binaria (cuadrados repetidos).
Funciones definidas en los enteros positivos, como la de divisores o la de Euler.
Ecuaciones polinomiales donde solo nos interesan las soluciones enteras.
Sistema x ≡ aᵢ (mod nᵢ) con nᵢ coprimos.
ax + by = c tiene soluciones enteras si y solo si el mcd(a,b) divide a c.
d(n) es el número de divisores y σ(n) es la suma de los mismos.
Soluciones enteras de x² + y² = z², con la forma (m²-n², 2mn, m²+n²).
Cómo resolver ecuaciones de la forma ax ≡ b (mód n).
Usando Nᵢ = N/nᵢ e inversos.
Resolver sistemas y calcular módulo n grandes.
Si p es primo y mcd(a,p) = 1, entonces a^(p-1) ≡ 1 (mód p).
mcd(a,b) = ax + by para algunos enteros x, y.
φ(n) es la cantidad de enteros entre 1 y n que son coprimos con n.
El k más pequeño tal que aᵏ ≡ 1.
aᵠ⁽ⁿ⁾ ≡ 1 (mod n) cuando mcd(a,n)=1.
(p-1)! ≡ -1 (mod p).
f(mn) = f(m)f(n) cuando m y n son coprimos.
n = a² + b² si no hay p≡3(4) con potencia impar.
vp(n!) = ∑⌊n/pᵏ⌋.
Usando números de Fermat y otros métodos.
φ(mn) = φ(m)φ(n) cuando mcd(m,n)=1.
φ, τ y σ son multiplicativas.
Calcular a⁻¹ ≡ aᵖ⁻² (mod p).
Reducir exponentes usando mod φ(n).
Si (n-1)! ≡ -1 mod n, entonces n es primo.
Resolver varias congruencias (sin usar el TRC).
Encontrar x, y tales que ax + by = mcd(a,b).
∑φ(d) = n para todos los divisores d de n.
Probando con los divisores de φ(n).
vₚ(n!) = Σ⌊n/pᵏ⌋.
vₚ(n!) para los factores primos de b.
Cómo hallar restricciones para el parámetro.
Contando múltiplos de p, p², p³, ...
a⁻¹ ≡ a^(p-2) mod p.
Resolver sistemas de congruencias con módulos que son coprimos entre sí.
vₚ(n!) = Σ⌊n/pᵏ⌋ para k = 1, 2, ...
Funciones donde f(mn) = f(m)f(n) siempre que mcd(m,n) = 1.
n = a² + b² si los primos ≡ 3 (mód 4) en su factorización tienen exponente par.
Si mcd(a,n) = 1, entonces a^φ(n) ≡ 1 (mód n).
(p-1)! ≡ -1 (mód p) si y solo si p es un número primo.
N(a+bi) = a² + b².
a^((p-1)/2) ≡ (a/p) (mod p).
El enunciado de (p/q)(q/p) = (-1)^((p-1)/2·(q-1)/2).
¿Cuándo existen las raíces primitivas?
Cómo hallar la solución positiva más pequeña.
(a/p) puede ser 0, 1 o -1.
vp(C(m+n,n)) es igual a los acarreos en base p.
vp(aⁿ - bⁿ) cuando p divide a a-b.
Propiedad de que ord(a) | φ(n).
Para ver si a es un residuo cuadrático mod p.
Propiedad de (ab/p) = (a/p)(b/p).
Fórmulas para (-1/p) y (2/p).
Cualquier entero positivo es suma de 4 cuadrados.
Cuidado especial cuando p es igual a 2.
Generando todas las soluciones posibles.
Hay φ(φ(n)) raíces primitivas.
Para saber cuándo p divide a C(n,k).
Cuáles enteros de Gauss son primos.
x_{n+1} + y_{n+1}√D = (x₁ + y₁√D)^(n+1).
p ≡ 3 (mod 4) se queda primo; p ≡ 1 (mod 4) se factoriza.
N(αβ) = N(α)N(β).
Condiciones especiales y fórmula.
Fórmula de vₚ(aⁿ - bⁿ) cuando p | a-b.
vₚ(C(m+n,n)) = acarreos en base p.
(-1/p) = (-1)^((p-1)/2).
(p/q)(q/p) = (-1)^((p-1)(q-1)/4).
(a/p) = 0, 1 o -1.
a^((p-1)/2) ≡ (a/p) mod p.
Siempre existen para los números primos.
Convergentes de √D.
Cuando n es impar.
α | β implica que N(α) | N(β).
2 = -i(1+i)², se ramifica.
Tabla de soluciones fundamentales.
Usando potencias de matrices.
ord(aᵏ) = ord(a)/mcd(k,ord(a)).
Existen para primos impares.
Usando el pequeño teorema de Fermat.
Usando el criterio de Euler.
Para saber si a es un residuo cuadrático mód p.
(2/p) = (-1)^((p²-1)/8).
Resolviendo problemas de vₚ(aⁿ ± bⁿ).
Solo para 1, 2, 4, p^k y 2p^k.
Orden multiplicativo y generadores de grupos cíclicos.
Números que son cuadrados módulo n y el uso del símbolo de Legendre.
Valuación p-ádica vₚ(n), que es el exponente de p en la factorización de n.
a es un residuo cuadrático mód p si y solo si a^((p-1)/2) ≡ 1 (mód p).
El entero positivo k más pequeño tal que a^k ≡ 1 (mód n).
vₚ(C(m+n,m)) es igual al número de acarreos al sumar m y n en base p.
Elementos que tienen orden φ(n) y generan el grupo (Z/nZ)*.
(a/p) vale 1 si a es residuo cuadrático, -1 si no lo es, y 0 si p divide a 'a'.
Una operación sobre funciones aritméticas que corresponde a la multiplicación de series de Dirichlet.
Resolver x² - Dy² = 1 cuando D no es un cuadrado, usando fracciones continuas.
Una fórmula que permite recuperar una función aritmética a partir de su función sumatoria usando la función de Möbius.
Diversos métodos y trucos para resolver ecuaciones diofánticas.
Probar que no hay soluciones demostrando que una solución implicaría otra más pequeña.
aⁿ - bⁿ tiene un divisor primo primitivo.
Pasando soluciones de mod p a mod pᵏ.
Cómo hallar raíces cuadradas mod pᵏ.
Casos donde el teorema no se cumple.
Cuándo se puede resolver x² - Dy² = -1.
Factorización única salvo unidades.
f(a) ≡ 0, f'(a) ≢ 0 mod p.
2⁶ - 1 y algunos casos específicos.
a_{k+1} = a_k - f(a_k)/f'(a_k).
Vínculo entre Kummer y Lucas.
Caso especial para a = 2, b = 1.
Para probar que ciertos primos existen.
LTE, Zsigmondy, lema de Hensel y enteros algebraicos.
Fórmula para calcular vₚ(aⁿ - bⁿ) bajo ciertas condiciones.
La asombrosa relación entre (p/q) y (q/p) para primos impares.
Para todo primo p >= 5, el coeficiente binomial C(2p, p) ≡ 2 (mod p^3).
Usar las fórmulas de Vieta para encontrar nuevas soluciones y aplicar descenso.
aⁿ - bⁿ tiene un divisor primo que no divide a aᵏ - bᵏ para k < n (con excepciones).
Cómo elevar soluciones de mod p a mod pᵏ.
Z[i] = {a + bi : a, b ∈ Z}, con factorización única.