enteros coprimos
En matemáticas , dos números enteros a y b son coprimos , primos relativos o primos entre sí si el único número entero positivo que es divisor de ambos es 1. [1] En consecuencia, cualquier número primo que divide a no divide a b , y viceversa 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 bo 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 considerado 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.
Las notaciones estándar para los números enteros primos a y b son: mcd( a , b ) = 1 y ( a , b ) = 1 . En su libro de texto de 1989, Ronald Graham , Donald Knuth y Oren Patashnik propusieron que la notación se use para indicar que a y b son primos relativos y que se use el término "primo" en lugar de coprimo (como en a es primo de b ) . [3]
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 GCD binario o el algoritmo GCD de Lehmer .
El número de enteros coprimos con un entero positivo n , entre 1 y n , está 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 coprimos 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 coprimos por pares, lo que significa que a y b son coprimos para cada par ( a , b ) de números diferentes . 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.
