Números enteros coprimos

En teoría de números , dos números enteros a y b son coprimos , primos entre sí o mutuamente primos si el único número entero positivo que es divisor de ambos es 1. ^[1] En consecuencia, cualquier número primo que divida a 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 de b o que a es coprimo de b .

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

Cuando los números 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 para indicar que a y b son primos entre sí y que se utilizara el término "primo" en lugar de coprimo (como en a es primo de b ). ^[3]${\estilo de visualización a\perp b}$

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

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

Un conjunto de números enteros también puede llamarse coprimo si sus elementos no comparten ningún factor positivo común excepto 1. Una condición más fuerte en un conjunto de números enteros es coprimo por pares, lo que significa que a y b son coprimos para cada par ( a , b ) de números enteros diferentes 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 números enteros coprimos con todo número entero, y son los únicos números enteros coprimos con 0.

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

• Ningún número primo divide a y b .
• Existen números 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 por ≡ 1 (mod a ) . En el lenguaje de la teoría de anillos, b es una unidad en el anillo ⁠ ⁠${\displaystyle \mathbb {Z} /a\mathbb {Z} }$ de los 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 del resto chino ); 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 sigue del primer punto por el lema de Euclides , que establece que si un número primo p divide a un producto bc , entonces p divide al menos a 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 al producto bc , entonces a divide a c . ^[7] Esto puede verse como 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 sería "visible" a través de una línea de visión sin obstáculos 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 ) . (Véase la figura 1.)

En un sentido que puede precisarse, la probabilidad de que dos números enteros elegidos al azar sean coprimos es 6/ π ² , lo que supone 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 2 ^a – 1 y 2 ^b – 1 son coprimos. ^[8] Como generalización de esto, siguiendo fácilmente del 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 también puede llamarse 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, 15 son coprimos porque 1 es el único entero positivo que los divide a todos.${\displaystyle S=\{a_{1},a_{2},\dots ,a_{n}\}}$

Si cada par de números enteros en un conjunto es coprimo, entonces se dice que el conjunto es coprimo por pares (o primo relativo por pares , coprimo mutuo o primo relativo mutuo ). 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 inverso no es cierto. Por ejemplo, los números 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 del resto chino .

Es posible que un conjunto infinito de números enteros sean coprimos por pares. Algunos ejemplos notables son el conjunto de todos los números primos, el conjunto de elementos de la sucesión de Sylvester y el conjunto de todos los números de Fermat .

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

Dados dos números enteros a y b elegidos al azar , es razonable preguntarse qué probabilidad hay de que a y b sean 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 (véase Teorema fundamental de la aritmética ).

De manera informal, la probabilidad de que cualquier número sea divisible por un primo (o de hecho cualquier 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 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 colección finita 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, uno es llevado a suponer 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 de los 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 modo que cada entero positivo ocurra con la misma probabilidad, pero las afirmaciones sobre "enteros elegidos al azar" como las anteriores se pueden formalizar 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 sean coprimos. Aunque P _N nunca será exactamente igual a 6/ π ² , con el trabajo ^[9] se puede demostrar que en el límite a medida que la probabilidad P _N se acerca a 6/ π ² .${\displaystyle \{1,2,\ldots ,N\}}$${\displaystyle N\to \infty ,}$

De manera más general, la probabilidad de que k números enteros elegidos al azar sean coprimos es${\displaystyle {\tfrac {1}{\zeta (k)}}.}$

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:

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

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

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

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

En el diseño de máquinas, se logra un desgaste uniforme y parejo de los engranajes eligiendo que el número de dientes de los dos engranajes que engranan entre sí sea relativamente primo. Cuando se desea una relación de engranajes 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 anterior a la informática , algunas máquinas de cifrado Vernam combinaban varios bucles de cinta de claves de diferentes longitudes. Muchas máquinas de rotor combinan rotores de diferentes cantidades de dientes. Estas combinaciones funcionan mejor cuando todo el conjunto de longitudes son coprimos por pares. ^{[12] [13] [14] [15]}

Este concepto se puede extender a otras estructuras algebraicas además de , por${\displaystyle \mathbb {Z} ;}$ ejemplo, los polinomios cuyo máximo común divisor es 1 se denominan polinomios coprimos .

Busque coprimo en Wikcionario, el diccionario libre.

• El huerto de Euclides
• Número de superpartido

• Hardy, GH ; Wright, EM (2008), Introducción a la teoría de 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 números (2.ª ed.), John Wiley & Sons
• Ore, Oystein (1988) [1948], Teoría de 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 infinitas de coprimos", Mathematical Gazette , 92 : 66–70.