números enteros coprimos

En teoría de números , dos enteros a y b son coprimos , primos relativos o mutuamente primos si el único entero positivo que es divisor de ambos es 1. ^{[ 1 ]} En consecuencia, cualquier número primo que divida a no divide a b , y viceversa. Esto es equivalente a que su máximo común divisor (MCD) sea 1. ^{[ 2 ]} También se dice que a es primo con b o que a es coprimo con b .

Los números 8 y 9 son coprimos, a pesar de que ninguno de ellos —considerado individualmente— es 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 simplificada son coprimos por definición.

Cuando los enteros a y b son coprimos, la forma estándar de expresar este hecho en notación matemática es indicar que su máximo común divisor es uno, mediante la fórmula mcd( a , b ) = 1 o ( a , b ) = 1 . En su libro de texto de 1989, Concrete Mathematics , Ronald Graham , Donald Knuth y Oren Patashnik propusieron una notación alternativa.${\displaystyle a\perp b}$para indicar que a y b son primos relativos y que se utilice el término "primo" en lugar de coprimo (como en a es primo a b ). ^{[ 3 ]}

Una forma rápida de determinar si dos números son coprimos es mediante el algoritmo euclidiano y sus variantes más rápidas, como el algoritmo del MCD binario o el algoritmo del MCD de Lehmer .

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

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

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

Varias condiciones son equivalentes a que a y b sean coprimos:

• Ningún número primo divide a a y a b .
• Existen enteros x, y tales que ax + by = 1 (véase la identidad de Bézout ).
• El entero b tiene un inverso multiplicativo módulo a , lo que significa que existe un entero y tal que b ≡ 1 (mod a ) . En lenguaje de teoría de anillos, b es una unidad en el anillo .${\displaystyle \mathbb {Z} /a\mathbb {Z} }$de enteros módulo a .
• Cada par de relaciones de congruencia para un entero desconocido x , de la forma x ≡ k (mod a ) y x ≡ m (mod b ) , tiene una solución ( teorema chino del resto ); de hecho, las soluciones se describen mediante una única relación de congruencia módulo ab .
• El mínimo común múltiplo de a y b es igual a su producto ab , es decir, mcm( a , b ) = ab . ^{[ 4 ]}

Como consecuencia del tercer punto, si a y b son coprimos y br ≡ bs (mod a ) , entonces r ≡ s (mod a ) . ^{[ 5 ]} Es decir, podemos "dividir por b " cuando trabajamos módulo a . Además, si b ₁ , b ₂ son ambos 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); ^{[ 6 ]} esto también se deduce del primer punto por el 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 cualesquiera potencias a ^k y b ^m .

Si a y b son coprimos y a divide el producto bc , entonces a divide a c . ^{[ 7 ]} Esto puede considerarse una generalización del lema de Euclides.

Los dos números enteros a y b son coprimos si y solo si el punto con coordenadas ( a , b ) en un sistema de coordenadas cartesianas es "visible" a través de una línea de visión despejada desde el origen (0, 0) , en el sentido de que no existe ningún punto con coordenadas enteras en el segmento de recta entre el origen y ( a , b ) . (Véase la figura 1).

En un sentido que se puede precisar, la probabilidad de que dos enteros elegidos al azar sean coprimos es 6/ π ² , que es aproximadamente el 61% (véase §  Probabilidad de coprimalidad , más abajo).

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

${\displaystyle \gcd \left(n^{a}-1,n^{b}-1\right)=n^{\gcd(a,b)}-1.}$

Un conjunto de números enteros${\displaystyle S=\{a_{1},a_{2},\dots ,a_{n}\}}$También se puede decir que un conjunto es coprimo o coprimo por conjunto si el máximo común divisor de todos los elementos del conjunto es 1. Por ejemplo, los números enteros 6, 10 y 15 son coprimos porque 1 es el único entero positivo que los divide a todos.

Si cada par de enteros en un conjunto es coprimo, entonces se dice que el conjunto es coprimo por pares (o coprimo relativo por pares , coprimo mutuo o coprimo relativo mutuo ). La coprimalidad por pares es una condición más fuerte que la coprimalidad por conjuntos; todo conjunto finito coprimo por pares también es coprimo por conjuntos, pero lo contrario no es cierto. Por ejemplo, los enteros 4, 5, 6 son coprimos (por conjuntos) (porque el único 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 sean coprimos entre sí. Ejemplos notables incluyen el conjunto de todos los números primos, el conjunto de elementos de la secuencia de Sylvester y el conjunto de todos los números de Fermat .

Dados dos enteros elegidos al azar, a y b , es razonable preguntarse qué probabilidad hay de que a y b sean coprimos. Para determinarlo, conviene utilizar la caracterización de que a y b son coprimos si y solo si ningún número primo los divide a ambos (véase el Teorema Fundamental de la Aritmética ).

De manera informal, la probabilidad de que cualquier número sea divisible por un número primo (o de hecho por cualquier número entero ) p es${\displaystyle {\tfrac {1}{p}};}$Por ejemplo , cada séptimo entero es divisible por 7. Por lo tanto , la probabilidad de que dos números sean ambos divisibles por p es${\displaystyle {\tfrac {1}{p^{2}}},}$y la probabilidad de que al menos uno de ellos no lo sea es${\displaystyle 1-{\tfrac {1}{p^{2}}}.}$Cualquier conjunto finito de eventos de divisibilidad asociados a primos distintos es mutuamente independiente. Por ejemplo, en el caso de dos eventos, un número es divisible por los primos p y q si y solo si es divisible por pq ; el último evento tiene probabilidad${\displaystyle {\tfrac {1}{pq}}.}$Si uno hace la suposición heurística de que tal razonamiento puede extenderse a infinitos eventos de divisibilidad, se le lleva a adivinar que la probabilidad de que dos números sean coprimos está dada por un producto sobre todos los primos,

${\displaystyle \prod _{{\text{prime }}p}\left(1-{\frac {1}{p^{2}}}\right)=\left(\prod _{{\text{prime }}p}{\frac {1}{1-p^{-2}}}\right)^{-1}={\frac {1}{\zeta (2)}}={\frac {6}{\pi ^{2}}}\approx 0.607927102\approx 61\%.}$

Aquí ζ se refiere a la función zeta de Riemann , la identidad que relaciona el producto sobre los 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 forma de elegir un entero positivo al azar de manera que cada entero positivo ocurra con igual probabilidad, pero las afirmaciones sobre "enteros elegidos al azar" como las anteriores pueden formalizarse utilizando la noción de densidad natural . Para cada entero positivo N , sea P _N la probabilidad de que dos números elegidos al azar en${\displaystyle \{1,2,\ldots ,N\}}$son coprimos. Aunque P _N nunca será exactamente igual a 6/ π ² , con trabajo ^{[ a ]} ​​se puede demostrar que en el límite cuando${\displaystyle N\to \infty ,}$La probabilidad P _N se aproxima a 6/ π ² .

De forma más general, la probabilidad de que k enteros elegidos al azar sean coprimos entre sí es${\displaystyle {\tfrac {1}{\zeta (k)}}.}$[ ^{9 ]​}

Todos los pares de números coprimos positivos ( m , n ) (con m > n ) se pueden organizar en dos árboles ternarios completos disjuntos , un árbol que comienza en (2, 1) (para pares par-impar e impar-par), ^{[ 10 ]} y el otro árbol que comienza en (3, 1) (para pares impar-impar). ^{[ 11 ]} Los hijos de cada vértice ( m , n ) se generan de la siguiente manera:

• Sucursal 1:${\displaystyle (2m-n,m)}$
• Sucursal 2:${\displaystyle (2m+n,m)}$
• Sucursal 3:${\displaystyle (m+2n,n)}$

Este esquema es exhaustivo y no redundante, sin miembros inválidos. Esto se puede probar observando que, si${\displaystyle (a,b)}$es un par coprimo con${\displaystyle a>b,}$entonces

• si${\displaystyle a>3b,}$entonces ${\displaystyle (a,b)}$es hijo de${\displaystyle (m,n)=(a-2b,b)}$a lo largo de la rama 3;
• si${\displaystyle 2b<a<3b,}$entonces${\displaystyle (a,b)}$es hijo de${\displaystyle (m,n)=(b,a-2b)}$a lo largo de la rama 2;
• si${\displaystyle b<a<2b,}$entonces${\displaystyle (a,b)}$es hijo de${\displaystyle (m,n)=(b,2b-a)}$a lo largo de la rama 1.

En todos los casos${\displaystyle (m,n)}$es un par coprimo "más pequeño" con${\displaystyle m>n.}$Este proceso de "calcular al padre" solo puede detenerse si se cumple alguna de las siguientes condiciones:${\displaystyle a=2b}$o${\displaystyle a=3b.}$En estos casos, la coprimalidad implica que el par es o${\displaystyle (2,1)}$o${\displaystyle (3,1).}$

Otra forma (mucho más sencilla) de generar un árbol de pares coprimos positivos ( m , n ) (con m > n ) es mediante dos generadores.${\displaystyle f:(m,n)\rightarrow (m+n,n)}$y${\displaystyle g:(m,n)\rightarrow (m+n,m)}$, comenzando por la raíz${\displaystyle (2,1)}$El árbol binario resultante , el árbol de Calkin-Wilf , es exhaustivo y no redundante, lo que se puede ver de la siguiente manera. Dado un par de primos coprimos, se aplica recursivamente${\displaystyle f^{-1}}$o${\displaystyle g^{-1}}$dependiendo de cuál de ellos produzca un par coprimo positivo con m > n . Como solo uno lo hace, el árbol no es redundante. Dado que mediante este procedimiento se llega inevitablemente a la raíz, el árbol es exhaustivo.

En el diseño de maquinaria, se logra un desgaste uniforme de los engranajes eligiendo que el número de dientes de los dos engranajes que engranan sea relativamente primo. Cuando se desea una relación de transmisión de 1:1 , se puede insertar entre ellos un engranaje relativamente primo con respecto a los dos engranajes de igual tamaño.

En la criptografía preinformática , algunas máquinas de cifrado Vernam combinaban varias cintas de clave de diferentes longitudes. Muchas máquinas de rotor combinan rotores con diferente número de dientes. Estas combinaciones funcionan mejor cuando el conjunto completo de longitudes son coprimas por pares. ^{[ 12 ] [ 13 ] [ 14 ] [ 15 ]}

Este concepto puede extenderse a otras estructuras algebraicas además de${\displaystyle \mathbb {Z}$ ;} ⁠ por ejemplo,los polinomioscuyomáximo común divisores 1 se denominanpolinomios coprimos.

• El huerto de Euclides
• Número superpartito

• Hardy, GH ; Wright, EM (2008), Introducción a la teoría de los números (6.ª  ed.), Oxford University Press , ISBN 978-0-19-921986-5
• Niven, Ivan; Zuckerman, Herbert S. (1966), Introducción a la teoría de los números (2.ª  ed.), John Wiley & Sons
• Ore, Oystein (1988) [1948], Teoría de los números y su historia , Dover, ISBN 978-0-486-65620-5
• Rosen, Kenneth H. (1992), Teoría elemental de números y sus aplicaciones (3.ª  ed.), Addison-Wesley, ISBN 978-0-201-57889-8

• Lord, Nick ( marzo de 2008), "Una construcción uniforme de algunas secuencias coprimas infinitas", Mathematical Gazette , 92 : 66–70.