Enteros coprimos

A collection of numbers whose only common factor is 1

Busque coprime en Wiktionary, el diccionario gratuito.

En la teoría de números , dos números enteros un y b son primos entre sí , relativamente primos o mutuamente prime ^[1] si el número entero único positivo que uniformemente divisiones (es un divisor de) ambos de ellos es 1. Uno dice también una es primo a b o una es coprime con b . En consecuencia, cualquier número primo que divida a uno de a o b no divide al otro. Esto equivale a que su máximo común divisor (mcd) sea 1. ^[2]

El numerador y denominador de una fracción reducida son coprimos. Los números 14 y 25 son coprimos, ya que 1 es su único divisor común. Por otro lado, 14 y 21 no son coprimos, porque ambos son divisibles por 7.

Notación y pruebas

Notaciones estándar para números enteros primos entre una y b son: mcd ( a , b ) = 1 y ( a , b ) = 1 . En un documento de 1989, Graham , Knuth , y Patashnik propusieron que la notación se utiliza para indicar que un y b son primos entre sí y que el término "primer" usarse en lugar de primos entre sí (como en una es primordial para b ). ^[3]${\displaystyle a\perp b}$

El algoritmo euclidiano y sus variantes más rápidas, como el algoritmo binario GCD 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 , 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 primos entre sí si sus elementos comparten ningún factor positivo común excepto condición 1. A más fuerte en un conjunto de números enteros es primos entre sí por pares , lo que significa que un y b son primos entre sí para cada par ( un , b ) de diferente 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 primos coprimos con cada número entero, y son los únicos números enteros que son coprimos con 0.

Una serie de condiciones son equivalentes a una y b ser primos entre sí:

• No hay números primos divide tanto a y b .
• Existen enteros x e y tales que ax + por = 1 (véase la identidad de Bézout ).
• El entero b tiene un módulo inverso multiplicativo 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 Z / a Z de números 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 un y b es igual a su producto ab , es decir, lcm ( un , b ) = ab . ^[4]

Como consecuencia de la tercera punto, si un y b son coprimos y br ≡ ancho ( mod a ), entonces r ≡ s (mod una ). ^[5] Es decir, podemos "dividir por b " cuando trabajamos módulo a . Además, si b ₁ y b ₂ son coprime 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 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 un y b son primos entre sí y un divide el producto bc , a continuación, un 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 celosía de 4 × 9 no se cruza con ningún otro punto de celosía.

Los dos números enteros un y b son primos entre sí si y sólo si el punto con coordenadas ( un , b ) en un sistema de coordenadas cartesianas es "visible" desde el origen (0,0), en el sentido de que no hay ningún punto con coordenadas enteras en el segmento de línea entre el origen y ( a , b ). (Ver figura 1.)

En un sentido que se puede precisar, la probabilidad de que dos enteros elegidos al azar sean coprimos es 6 / π ² (ver pi ), que es aproximadamente el 61%. Vea abajo.

Dos números naturales a y b son primos entre sí si y sólo si los números 2 ^a - 1 y 2 ^b - 1 son primos entre sí. ^[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.}$

Coprimalidad en conjuntos

Un conjunto de enteros S = { a ₁ , a ₂ , .... a _n } también se puede llamar coprime o coprime setwise 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 primos relativos por pares , primos entre sí o primos entre sí ). La coprimalidad por pares es una condición más fuerte que la coprimalidad por pares; cada conjunto finito de coprimos por pares también es coprimo por pares, pero lo contrario no es cierto. Por ejemplo, los enteros 4, 5, 6 son coprimos (setwise) (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 enteros sea coprime 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 los ideales del anillo

Dos ideales A y B en un anillo conmutativo R se llaman primos entre sí (o comaximal ) si A + B = R . Esto generaliza la identidad de Bézout : con esta definición, dos ideales principales ( una ) y ( b ) en el anillo de los enteros Z son primos entre sí, si y sólo si un y b son primos entre sí. Si los ideales A y B de R son coprimos, entonces AB = A∩ B ; Además, si C es tercera ideales tales que A contiene BC , a continuación, A contiene C . El teorema del resto chino se puede generalizar a cualquier anillo conmutativo, utilizando ideales coprimos.

Probabilidad de coprimalidad

Dados dos números enteros escogidos al azar a y b , es razonable preguntarse qué tan probable es que una y b son primos entre sí. En esta determinación, es conveniente utilizar la caracterización que un y b son primos entre sí si y sólo si no hay divisiones número primo ambos de ellos (ver 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 número entero) es ; 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 , y la probabilidad de que al menos uno de ellos no lo sea 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 números primos p y q si y sólo si es divisible por pq ; el último evento tiene probabilidad 1 / pq${\displaystyle p}$${\displaystyle 1/p}$${\displaystyle 1/p^{2}}$${\displaystyle 1-1/p^{2}}$. Si se hace la suposición heurística de que tal razonamiento puede extenderse a un número infinito de eventos de divisibilidad, se puede suponer que la probabilidad de que dos números sean coprimos viene 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 relativa del producto sobre números primos a ζ (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 número entero positivo al azar para que cada número entero positivo ocurra con la misma probabilidad, pero las afirmaciones sobre "números 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 , con el trabajo ^[9] se puede demostrar que en el límite a medida que la probabilidad se acerca .${\displaystyle \{1,2,\ldots ,N\}}$${\displaystyle 6/\pi ^{2}}$${\displaystyle N\to \infty }$${\displaystyle P_{N}}$${\displaystyle 6/\pi ^{2}}$

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

Generando todos los pares coprime

El orden de generación de pares coprime por este algoritmo. El primer nodo (2,1) está marcado en rojo, sus tres hijos se muestran en naranja, la tercera generación es amarilla y así sucesivamente en el orden del arco iris.

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

• 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.

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 primarios. Cuando se desea una relación de engranajes 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 son coprime por pares. ^{[12] [13] [14] [15]}

Ver también

• Número de superpartiente

Notas

1. Eaton, James S. Tratado sobre aritmética. 1872. Puede descargarse de: https://archive.org/details/atreatiseonarit05eatogoog
2. Hardy y Wright 2008 , p. 6
3. Graham, RL; Knuth, DE; Patashnik, O. (1989), Matemáticas concretas / Una fundación para la informática , Addison-Wesley, p. 115, ISBN 0-201-14236-8
4. Mineral de 1988 , p. 47
5. Niven y Zuckerman , 1966 , p. 22, Teorema 2.3 (b)
6. Niven y Zuckerman , 1966 , p. 6, teorema 1.8
7. Niven y Zuckerman , 1966 , p.7, Teorema 1.10
8. Rosen 1992 , p. 140
9. Este teorema fue demostrado por Ernesto Cesàro en 1881. Para una demostración, consulte Hardy & Wright 2008 , Theorem 332
10. Saunders, Robert & Randall, Trevor (julio de 1994), "El árbol genealógico de los trillizos pitagóricos revisitado", Mathematical Gazette , 78 : 190-193, doi : 10.2307 / 3618576.
11. Mitchell, Douglas W. (julio de 2001), "Una caracterización alternativa de todas las tripletas pitagóricas primitivas", Mathematical Gazette , 85 : 273-275, doi : 10.2307 / 3622017.
12. Klaus Pommerening. "Criptología: Generadores de claves con períodos prolongados" .
13. David Mowry. "Máquinas de cifrado alemanas de la Segunda Guerra Mundial" . 2014. p. dieciséis; pag. 22.
14. Dirk Rijmenants. "Orígenes de la libreta de un solo uso" .
15. Gustavus J. Simmons. "Cifrado Vernam-Vigenère" .

Referencias

• Hardy, GH ; Wright, EM (2008), Introducción a la teoría de los números (6a 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 (2a 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 (3a ed.), Addison-Wesley, ISBN 978-0-201-57889-8

Lectura adicional

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