coprimos

Los coprimos, en matemáticas, son enteros cuyo máximo común divisor es 1. En su uso habitual se refiere a dos números; también puede hablarse de conjuntos de números que son pares o conjuntos de números mutuamente coprimos, es decir, donde cada par de elementos es coprimo.

Una característica fundamental es la identidad de Bezout: si gcd(a,b)=1, existen enteros x e y tales que ax + by = 1. Esta propiedad implica que a tiene inverso modular mod b, y viceversa, siempre que se mantenga la misma condición de coprimalidad. En general, si gcd(a,m)=1, existe el inverso de a módulo m. Para un solo número n, el número de enteros entre 1 y n que son coprimos con n está dado por la función totiente φ(n), y si n tiene descomposición en primos n = p1^k1 ... pr^kr, entonces φ(n) = n ∏ (1 - 1/p_i).

En conjuntos, dos números son coprimos si su gcd es 1; un conjunto es coprimo de forma colectiva o universal cuando el gcd de todos sus elementos es 1, o de forma par a par cuando cada par es coprimo. Si dos módulos m y n son coprimos, el teorema chino del resto garantiza una correspondencia entre residuos módulo mn y pares de residuos módulos m y n.

Aplicaciones típicas abarcan aritmética modular, resolución de ecuaciones diofánticas, criptografía (RSA y similares), y problemas de conteo que involucran números coprimos.