Coprime

Two natural numbers and are relatively prime ( ) if there is no natural number other than the one that divides both numbers . Synonym is relatively prime , from the English relatively prime or coprime . If two natural numbers don't have a prime factor in common , they are relatively prime . From this definition it follows that every natural number is coprime to 1, including the number 1 itself. A fraction of two coprime numbers cannot therefore be reduced . ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle a \ perp b}$

To prove coprime, one usually calculates the greatest common factor : two numbers are coprime if and only if 1 is their greatest common factor.

More than two natural numbers are called pairwise relatively prime (ger .: pairwise coprime) if any two of them are prime to each other, and as a prime , if there is no prime factor in common to all these numbers. Numbers that are coprime pairs are also always coprime. The reverse direction does not apply, because, for example, 6, 10, 15 are coprime, but not pairwise coprime (e.g. because of gcd (10, 15) = 5).

Examples

The numbers 12 and 77 are relatively prime , because their prime factorization 12 = 2 · 2 · 3 and 77 = 7 · 11 do not contain any common prime factors.

The numbers 15 and 25 are not coprime, because in their prime factorization 15 = 3 · 5 and 25 = 5 · 5 there is the 5, which is also GCD (15, 25).

The numbers 9, 17, 64 are coprime pairs, because all three pairs 9 and 17, 17 and 64, 9 and 64 are coprime.

Obviously, two different prime numbers are always prime, since they only have themselves as a prime factor. Other examples of coprime numbers are two numbers whose difference is 1 or two odd numbers whose difference is 2.

Coprime is often a condition in many number theoretic problems. For example, a prerequisite for the Chinese remainder theorem is that the modules are coprime. The Euler φ function assigns each natural number n the number of n prime numbers in to. ${\ displaystyle \ {1, \ dots, n \}}$

properties

Coprime is a binary relation

{\ displaystyle {\ text {coprime number}} = \ left \ {\ left (a, b \ right) \ in \ mathbb {N} \ times \ mathbb {N} \ \ vert \ \ operatorname {ggT} (a, b) = 1 \ right \}}

This relation is not transitive , because for example 2 and 3 are relatively prime, as are 3 and 4, but not 2 and 4.

The asymptotic probability that two randomly chosen integers and are relatively prime is ${\ displaystyle a}$ ${\ displaystyle b}$

{\ displaystyle P (\ operatorname {ggT} (a, b) = 1) = {\ frac {1} {\ zeta (2)}} = {\ frac {6} {\ pi ^ {2}}} \ approx 61 \, \%,}

where is the Riemann ζ-function and the circle number . This theorem was first proven in 1881 by Ernesto Cesàro . ${\ displaystyle \ zeta}$ ${\ displaystyle \ pi}$

General is the asymptotic density of tuples with greatest common divisor . ${\ displaystyle 1 / (r ^ {n} \, \ zeta (n))}$ ${\ displaystyle n}$ ${\ displaystyle r}$

Coprime in rings

The concept of coprime can be transferred from the natural numbers to commutative rings with one element . In such a ring the units divide all elements. Two elements of the ring are called coprime if the units are their only common factors.

In the ring of integers , for example, the numbers 2 and −3 are prime, since their only common factors are the units 1 and −1.

Similar properties

Incommensurability with real numbers

supporting documents

↑ Peter Bundschuh : Introduction to Number Theory. 6th edition. Springer-Verlag, Berlin 2008, ISBN 978-3-540-76490-8 , p. 19 f. , P. 51 f.
^ Eckford Cohen: Arithmetical functions associated with arbitrary sets of integers. ( PDF ; 2.1 MB), Acta Arithmetica 5, 1959, pp. 407–415 (English; Errata , ( PDF ; 327 kB) statement is “Corollary 3.3” on p. 413).

[1] Peter Bundschuh : Introduction to Number Theory. 6th edition. Springer-Verlag, Berlin 2008, ISBN 978-3-540-76490-8 , p. 19 f. , P. 51 f.

[2] Eckford Cohen: Arithmetical functions associated with arbitrary sets of integers. ( PDF ; 2.1 MB), Acta Arithmetica 5, 1959, pp. 407–415 (English; Errata , ( PDF ; 327 kB) statement is “Corollary 3.3” on p. 413).