Enteros coprimos

En teoría de números , dos números enteros $a$ y $b$ son coprimos , primos relativos o primos mutuos 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 equivale a que su máximo común divisor (MCD) sea 1. ^[2] 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 de los dos, considerados 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 reducida son coprimos, por definición.

Notación y pruebas

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 relativos y que se usara el término "primo" en lugar de coprimo (como en $a$ es primo de $b$ ). . ^[3] $a\perp b$

Una forma rápida de determinar si dos números son coprimos viene dada por 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 se puede llamar 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 diferentes números 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 cada número entero, y son los únicos números enteros que son coprimos con 0.

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

Ningún número primo divide tanto $a$ como $a b$ .
Existen números enteros $x, y$ tales que $ax + by = 1$ (ver identidad de Bézout ).
El número entero $b$ tiene un módulo inverso multiplicativo $a$ , lo que significa que existe un número entero $y$ tal que $por \equiv 1 (mod a)$ . En lenguaje de teoría de anillos, $b$ es una unidad en el anillo de números enteros módulo $a$ . $\mathbb {Z} /a\mathbb {Z}$
Cada par de relaciones de congruencia para un entero desconocido $x$ , de la forma $x \equiv k (mod a)$ y $x \equiv 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, $lcm(a, b) = ab$ . ^[4]

Como consecuencia del tercer punto, si $a$ y $b$ son coprimos y $br \equiv bs (mod a)$ , entonces $r \equiv s (mod a)$ . ^[5] Es decir, podemos "dividir por $b$ " cuando trabajamos con el módulo $a$ . Además, si $b 1, b 2$ son ambos coprimos con $a$ , entonces también lo es su producto $b 1 b 2$ (es decir, módulo $a$ es un producto de elementos invertibles y, por lo tanto, invertible); ^[6] esto también se desprende 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, 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 $c$ . ^[7] Esto puede verse como una generalización del lema de Euclides.

Figura 1. Los números 4 y 9 son coprimos. Por lo tanto, la diagonal de una red de 4 × 9 no corta ningún otro punto de la red.

Los dos números enteros $a$ y $b$ son coprimos si y sólo si el punto con coordenadas $(a, b)$ en un sistema de coordenadas cartesiano 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 recta entre el origen y $(a, b)$ . (Ver figura 1.)

En un sentido que se puede precisar, la probabilidad de que dos números enteros elegidos al azar sean coprimos es $6/ π 2$ , que es aproximadamente el 61% (ver § Probabilidad de coprimalidad, más abajo).

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

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

Coprimalidad en conjuntos

Un conjunto de números enteros también se puede llamar coprimo o coprimo por conjuntos 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 divide a todos a ellos. $S=\{a_{1},a_{2},\dots,a_{n}\}$

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 , coprimo mutuo o primo 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 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 sea coprimo por pares. 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 .

Coprimalidad en los ideales del ring

Dos ideales $A$ y $B$ en un anillo conmutativo $R$ se llaman coprimos (o comaximal ) 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 sólo 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, utilizando ideales coprimos. $A+B=R.$ $\mathbb {Z}$ $AB=A\cap B;$

Probabilidad de coprimalidad

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 sólo si ningún número primo los divide a ambos (ver 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, cualquier número entero) $p$ es , por ejemplo, cada séptimo número entero es divisible por 7. Por lo tanto, la probabilidad de que dos números sean divisibles por $p$ es y la probabilidad de que al menos uno de ellos no es 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 sólo si es divisible por $pq$ ; este último evento tiene probabilidad. Si uno asume heurísticamente que tal razonamiento puede extenderse a una infinidad de eventos de divisibilidad, se llega a suponer que la probabilidad de que dos números sean coprimos está dada por un producto de todos los primos, ${\tfrac {1}{p}};$ ${\tfrac {1}{p^{2}}},$ $1-{\tfrac {1}{p^{2}}}.$ ${\tfrac {1}{pq}}.$

\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 números primos con $ζ (2)$ es un ejemplo de producto de Euler , y la evaluación de $ζ$ $(2)$ como $π 2/6$ es el problema de Basilea , resuelto por Leonhard Euler en 1735.

No hay forma de elegir un número entero positivo al azar para que cada número 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 sean coprimos. Aunque $P$ $N$ nunca será igual a $6/$ $π$ $2$ exactamente, con el trabajo ^[9] se puede demostrar que en el límite a medida que la probabilidad $P$ $N$ se aproxima a $6/$ $π$ $2$ . $\{1,2,\ldots ,N\}$ $N\to \infty ,$

De manera más general, la probabilidad de que $k$ enteros elegidos aleatoriamente sean coprimos es ${\tfrac {1}{\zeta (k)}}.$

Generando todos los pares coprime

El árbol con raíz en (2, 1). La raíz (2, 1) está marcada en rojo, sus tres hijos se muestran en naranja, la tercera generación en amarillo, y así sucesivamente en el orden del arco iris.

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

Rama 1: $(2m-n,m)$
Rama 2: $(2m+n,m)$
Rama 3: $(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 $(a,b)$ $a>b,$

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

En todos los casos hay un par coprimo "más pequeño" con Este proceso de "cálculo del padre" puede detenerse sólo si o En estos casos, la coprimalidad implica que el par es o $(m,n)$ $m>n.$ $a=2b$ $a=3b.$ $(2,1)$ $(3,1).$

Aplicaciones

En el diseño de máquinas, se logra un desgaste uniforme y uniforme 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 transmisión de 1:1 , se puede insertar entre ellos un engranaje relativamente cebado con respecto a los dos engranajes del mismo tamaño.

En la criptografía anterior a la computadora , algunas máquinas de cifrado Vernam combinaban varios bucles de cinta de claves de diferentes longitudes. Muchas máquinas de rotor combinan rotores de diferente número de dientes. Estas combinaciones funcionan mejor cuando todo el conjunto de longitudes es coprimo por pares. ^[12]^[13]^[14]^[15]

Generalizaciones

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

Ver también

Busque coprime en Wikcionario, el diccionario gratuito.

Notas

^ Eaton, James S. (1872). Tratado de aritmética. Boston: Thompson, Bigelow y Brown. pag. 49 . Consultado el 10 de enero de 2022 . Dos números son primos entre sí cuando ningún número entero, excepto uno, puede dividir a cada uno de ellos.
^ Hardy y Wright 2008, pág. 6
^ Graham, RL; Knuth, DE; Patashnik, O. (1989), Matemáticas concretas / Una base para la informática , Addison-Wesley, p. 115, ISBN 0-201-14236-8
^ Mineral 1988, pag. 47
^ Niven y Zuckerman 1966, pág. 22, Teorema 2.3(b)
^ Niven y Zuckerman 1966, pág. 6, Teorema 1.8
^ Niven y Zuckerman 1966, p.7, Teorema 1.10
^ Rosen 1992, pág. 140
^ Este teorema fue demostrado por Ernesto Cesàro en 1881. Para una demostración, consulte Hardy & Wright 2008, Teorema 332.
^ Saunders, Robert & Randall, Trevor (julio de 1994), "Revisión del árbol genealógico de los trillizos pitagóricos", Mathematical Gazette , 78 : 190–193, doi :10.2307/3618576.
^ Mitchell, Douglas W. (julio de 2001), "Una caracterización alternativa de todos los triples pitagóricos primitivos", Mathematical Gazette , 85 : 273–275, doi :10.2307/3622017.
^ Klaus Pommering. "Criptología: generadores de claves con períodos prolongados".
^ David Mowry. "Máquinas de cifrado alemanas de la Segunda Guerra Mundial". 2014. pág. dieciséis; pag. 22.
^ Dirk Rijmenants. "Orígenes del bloc de notas de un solo uso".
^ Gustavus J. Simmons. "Cifrado Vernam-Vigenère".

Referencias

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, Iván; 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

Otras lecturas

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