Enteros coprimos
En matemáticas , dos números enteros a y b son primos entre sí , relativamente primos o primos entre sí si el número entero único positivo que es un divisor de ambos es 1. [1] En consecuencia, cualquier número primo que divide un no divide b , y vice al revés. Esto es equivalente a que su máximo común divisor (mcd) sea 1. [2] También se dice que a es primo ab o que a es coprimo con b .
El numerador y el denominador de una fracción reducida son coprimos. Los números 14 y 25 son coprimos, a pesar de que ninguno de los dos considerados individualmente es un número primo, ya que 1 es su único divisor común. Por otro lado, 14 y 21 no son coprimos, porque ambos son divisibles por 7.
Notaciones estándar para números enteros primos entre una y b son: mcd ( a , b ) = 1 y ( a , b ) = 1 . En su 1989 libro de texto, Ronald Graham , Donald Knuth , y Oren Patashnik propusieron que la notación se utiliza para indicar que una y b son primos entre sí y que el término "primer" utilizar en lugar de primos entre sí (como en una es primordial a b ) . [3]
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.
