Enteros coprimos

En matemáticas, dos números enteros a y b son coprimos, relativamente primos o mutuamente primos si el único entero positivo que es divisor de ambos es 1. En consecuencia, cualquier número primo que divide a no divide b, y viceversa. Esto es equivalente a que su máximo común divisor (MCD) sea 1. Se dice también que a es primo de b o a es coprimo con b.

Los números 8 y 9 son coprimos, a pesar de que ninguno considerado individualmente es un número primo, ya que 1 es su único divisor común. Por otro lado, 6 y 9 no son coprimos, porque ambos son divisibles por 3. El numerador y el denominador de una fracción reducida son coprimos, por definición.

Notación y prueba

Notas estándar para números enteros relativamente primos a y b son: gcd(a, b) = 1 y ()a, b) = 1. En su libro de texto de 1989 Matemáticas concretas, Ronald Graham, Donald Knuth y Oren Patashnik propusieron que la notación a⊥ ⊥ b{displaystyle aperp b} ser utilizado para indicar que a y b son relativamente primos y que el término "prime" se utiliza en lugar de coprime (como en a es primo a b).

El algoritmo euclidiano y sus variantes más rápidas, como el algoritmo GCD binario o el algoritmo GCD de Lehmer, proporcionan una forma rápida de determinar si dos números son coprimos.

El número de enteros coprimos con un entero positivo n, entre 1 y n, está dada por la función totient de Euler, también conocida como función phi de Euler, φ(n ).

Un conjunto de enteros también se puede llamar coprimos si sus elementos no comparten ningún factor positivo común excepto 1. Una condición más fuerte en un conjunto de enteros es coprimos por pares, lo que significa que a y b son coprimos para cada par (a, b) de diferentes enteros en el conjunto. El conjunto {2, 3, 4} es coprimo, pero no es coprimo por pares ya que 2 y 4 no son primos relativos.

Propiedades

Los números 1 y −1 son los únicos números enteros coprimos con todos los números enteros, y son los únicos números enteros coprimos con 0.

Varias condiciones son equivalentes a a y b siendo coprimos:

• Ningún número primo divide ambos a y b.
• Existen números enteros x y Sí. tales que ax + por = 1 (ver la identidad de Bézout).
• El entero b tiene un modulo inverso multiplicativo a, significando que existe un entero Sí. tales que por (modelo) a). En el lenguaje teórico del anillo, b es una unidad en el anillo Z/aZ de enteros modulo a.
• Cada par de relaciones de congruencia para un entero desconocido x, de la forma x ↑ k (modelo) a) y x ↑ m (modelo) b), tiene una solución (teorema del resto chino); de hecho las soluciones se describen por un solo modulo de relación con la congruencia ab.
• El múltiplo menos común de a y b es igual a su producto ab, es decir. lcm(a, b) ab.

Como consecuencia del tercer punto, si a y b son coprimos y br ≡ bs (mod a), luego r ≡ s (mod a). Es decir, podemos "dividir entre b" cuando se trabaja módulo a. Además, si b₁ y b₂ son coprimos con a, entonces también lo es su producto b₁b₂ (es decir, módulo a es un producto de elementos invertibles, y por lo tanto invertible); esto también se sigue del primer punto del lema de Euclides, que establece que si un número primo p divide un producto bc, entonces p divide al menos uno de los factores b, c.

Como consecuencia del primer punto, si a y b son coprimos, entonces también lo son las potencias a^k y b^m.

Si a y b son coprimos y a divide el producto bc, entonces a divide c. Esto puede verse como una generalización del lema de Euclides.

Gráfico 1. Los números 4 y 9 son coprime. Por lo tanto, la diagonal de un 4 × 9 lattice no intersecciona ningún otro punto de celo

Los dos enteros a y b son coprimos si y solo si el punto con coordenadas (a, b) en un sistema de coordenadas cartesianas sería "visible" a través de una línea de visión sin obstrucciones desde el origen (0,0), en el sentido de que no hay ningún punto con coordenadas enteras en ningún lugar del segmento de línea entre el origen y (a, b). (Ver figura 1.)

En un sentido que puede precisarse, la probabilidad de que dos números enteros elegidos al azar sean coprimos es 6/π², que es alrededor del 61% (ver § Probabilidad de coprimalidad, a continuación).

Dos números naturales a y b son coprimos si y solo si los números 2^a − 1 y 2^b − 1 son coprimos. Como generalización de esto, siguiendo fácilmente el algoritmo euclidiano en base n > 1:

gcd()na− − 1,nb− − 1)=ngcd()a,b)− − 1.{displaystyle gcd left(n^{a}-1,n^{b}-1right)=n^{gcd(a,b)}-1.}

Coprimalidad en conjuntos

Un conjunto de enteros S = {a₁, a₂,.... a_n} también se puede llamar coprime o setwise coprime si el máximo común divisor de todos los elementos del conjunto es 1. Por ejemplo, los enteros 6, 10, 15 son coprimos porque 1 es el único entero positivo que los divide a todos.

Si cada par en un conjunto de números enteros es coprimo, entonces se dice que el conjunto es coprimo por pares (o primo relativo por pares, mutuamente coprimos o primos mutuos). La coprimalidad por pares es una condición más fuerte que la coprimalidad por conjuntos; cada conjunto finito coprimo por pares también es coprimo por conjuntos, pero lo contrario no es cierto. Por ejemplo, los números enteros 4, 5, 6 son coprimos (por conjuntos) (porque el único número entero positivo que los divide a todos es 1), pero no son coprimos por pares (porque mcd(4, 6) = 2).

El concepto de coprimalidad por pares es importante como hipótesis en muchos resultados de la teoría de números, como el teorema chino del resto.

Es posible que un conjunto infinito de enteros sea coprimo por pares. Los ejemplos notables incluyen el conjunto de todos los números primos, el conjunto de elementos en la secuencia de Sylvester y el conjunto de todos los números de Fermat.

Coprimalidad en ideales de anillo

Dos ideales A y B en un anillo conmutativo R se denominan coprimos (o comáximos) si A + B = R. Esto generaliza la identidad de Bézout: con esta definición, dos ideales principales (a) y (b) en el anillo de los números enteros Z son coprimos si y solo si a y b son coprimos. Si los ideales A y B de R son coprimos, entonces AB = A ∩B; además, si C es un tercer ideal tal que A contiene BC, entonces A contiene C. El teorema del resto chino se puede generalizar a cualquier anillo conmutativo, utilizando ideales coprimos.

Probabilidad de coprimalidad

Dados dos enteros elegidos al azar a y b, es razonable preguntar qué tan probable es que a y b son coprimos. En esta determinación, es conveniente utilizar la caracterización de que a y b son coprimos si y solo si ningún número primo los divide a ambos (ver Teorema fundamental de la aritmética).

Informalmente, la probabilidad de que cualquier número sea divisible por un primo (o de hecho cualquier entero) p{displaystyle p} es 1/p{displaystyle 1/p}; por ejemplo, cada 7o entero es divisible por 7. De ahí la probabilidad de que dos números sean divisibles por p es 1/p2{displaystyle 1/p^{2}, y la probabilidad de que al menos uno de ellos no es 1− − 1/p2{displaystyle 1-1/p^{2}. Cualquier colección finita de eventos de divisibilidad asociados a principios distintos es mutuamente independiente. Por ejemplo, en el caso de dos eventos, un número es divisible por primos p y q si es divisible por pq; este último evento tiene probabilidad 1/pq. Si uno hace la suposición heurística de que tal razonamiento puede ser extendido a infinitamente muchos eventos de divisibilidad, se conduce a adivinar que la probabilidad de que dos números son coprime es dada por un producto sobre todos los principios,

∏ ∏ primop()1− − 1p2)=()∏ ∏ primop11− − p− − 2)− − 1=1Especificaciones Especificaciones ()2)=6π π 2.. 0.607927102.. 61% % .{displaystyle prod _{text{ {}p}left(1-{1}{p^{2}}right)=left(prod) - ¿Qué? {1}{1-p^{-2}}derecha)}{-1}={frac {1}{zeta (2)}={frac {6}{pi} {f} {f} {fn} {fnf} {f}} {fnK}} {f}}} {fnf} {f}}}}} {f} {f}}}}}f}}}}f}}}}}}}f} {f} {f}f} {f} {f} {f} {f}f}f}f}f}f}f}}f}f}}fnKf}}}}}}}}}f}}}}}fnf}f}f}}f}}}}fnfnKf}}}}fnKf}f}}}}}}}fn ^{2}approx 0.607927102approx 61%.}

Aquí ζ se refiere a la función zeta de Riemann, la identidad que relaciona el producto sobre números primos con ζ(2) es un ejemplo de un producto de Euler, y la evaluación de ζ(2) como π²/6 es el problema de Basilea, resuelto por Leonhard Euler en 1735.

No hay manera de elegir un entero positivo al azar para que cada entero positivo se produzca con igual probabilidad, pero las declaraciones sobre "integers elegidos raramente" como los anteriores pueden ser formalizadas usando la noción de densidad natural. Para cada entero positivo N, vamos P_N ser la probabilidad de que dos números elegidos al azar en {}1,2,...... ,N}{displaystyle {1,2,ldotsN}} son coprime. Aunque P_N nunca igual 6/π π 2{displaystyle 6/pi ^{2} exactamente, con el trabajo uno puede mostrar que en el límite como N→ → JUEGO JUEGO {displaystyle Nto infty, la probabilidad PN{displaystyle P_{N} enfoques 6/π π 2{displaystyle 6/pi ^{2}.

Más generalmente, la probabilidad de k aleatoriamente elegidos enteros siendo coprime es 1/Especificaciones Especificaciones ()k){displaystyle 1/{zeta (k)}.

Generando todos los pares coprimos

El orden de generación de pares coprime por este algoritmo. El primer nodo (2,1) es rojo marcado, sus tres hijos se muestran en naranja, tercera generación es amarilla, y así sucesivamente en el orden del arco iris. Hay pares coprime cerca de los ejes y en algunos de los huecos, pero con puntos demasiado pequeños para ver aquí.

Todos los pares de números de coprime positivos ()m,n){displaystyle (m,n)} (con n}" xmlns="http://www.w3.org/1998/Math/MathML">m■n{displaystyle m prendan}n" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/637039c4a193f33fee72ebfeb6cb003593696160" style="vertical-align: -0.338ex; width:6.534ex; height:1.843ex;"/>) puede ser arreglado en dos árboles ternarios completos descomunados, un árbol a partir de ()2,1){displaystyle (2,1)} (por pares, incluso oidos y extraños), y el otro árbol a partir de ()3,1){displaystyle (3,1)} (para pares extraños). Los hijos de cada vértice ()m,n){displaystyle (m,n)} se generan de la siguiente manera:

• Subdivisión 1: ()2m− − n,m){displaystyle (2m-n,m)}
• Rama 2: ()2m+n,m){displaystyle (2m+n,m)}
• Subdivisión 3: ()m+2n,n){displaystyle (m+2n,n)}

Este esquema es exhaustivo y no redundante sin miembros inválidos.

Aplicaciones

En el diseño de máquinas, se logra un desgaste uniforme y parejo de los engranajes eligiendo el número de dientes de los dos engranajes que engranan entre sí para que sean relativamente primos. Cuando se desea una relación de engranajes de 1:1, se puede insertar entre ellos un engranaje relativamente principal con respecto a los dos engranajes de igual tamaño.

En la criptografía anterior a la computadora, algunas máquinas de cifrado de Vernam combinaban varios bucles de cinta clave de diferentes longitudes. Muchas máquinas de rotor combinan rotores de diferente número de dientes. Tales combinaciones funcionan mejor cuando todo el conjunto de longitudes son coprimos por pares.

Generalizaciones

Este concepto se puede ampliar a otras estructuras algebraicas que Z{displaystyle mathbb {Z}; por ejemplo, polinomios cuyo mayor divisor común es 1 se llaman polinomios coprime.