Skip to content
Home

Coprime (Relatively Prime) Numbers

Two integers are coprime when their greatest common divisor is 1. This article covers definitions, notation, properties, examples, history, and key applications in arithmetic and cryptography.

Author: Created: Updated:

In elementary number theory, two whole numbers are called coprime or relatively prime when they share no positive divisor greater than 1. Formally, integers a and b are coprime if their greatest common divisor equals 1. You can read a standard introduction in mathematics references, while the underlying objects are ordinary integers. Common notations include gcd(a,b)=1, (a,b)=1, or the perpendicular-like symbol a ⟂ b.

Definition and notation

Being coprime is a statement about the absence of shared prime factors. It is independent of sign: −8 and 9 are coprime because their absolute values share no prime factors. When gcd(a,b)=1 the fraction a/b is in lowest terms and a has a multiplicative inverse modulo b. The condition is purely multiplicative: it does not require either number to be prime itself.

Basic properties and useful consequences

  • Euclid's lemma: if gcd(a,b)=1 and a divides b·c, then a divides c. This underpins the uniqueness of prime factorization.
  • Modular inverses: a has an inverse modulo b exactly when gcd(a,b)=1; this fact is central to solving linear congruences.
  • Totient and counting: Euler's totient function φ(n) counts integers less than n that are coprime to n.
  • Arithmetic simplification: fractions reduce to lowest terms precisely when numerator and denominator are coprime.

Examples and illustrations

Simple examples make the idea concrete. The pair 6 and 35 are coprime because 6=2·3 while 35=5·7 share no primes. In contrast, 6 and 27 are not coprime because both are divisible by 3. Two distinct prime numbers are always coprime—see general properties of prime numbers—but a prime and a multiple of the same prime are not. For instance, 4 and 5 are coprime, while 10 and 5 are not.

History and development

The notion of numbers without a common divisor goes back to ancient arithmetic and is implicit in Euclid's work on greatest common divisors and prime factorization. The modern language of gcd and relative primality developed alongside algorithmic procedures such as the Euclidean algorithm. While historical terminology varied, the concept has been central to classical number theory for millennia and to modern computational applications.

Applications, extensions and distinctions

Coprimality appears throughout mathematics and computer science: it is essential in modular arithmetic, cryptographic protocols (for example when choosing keys in public-key systems), and in counting problems. The idea extends beyond integers—for example to polynomials or elements of rings, where two elements are coprime if they generate the whole ring. Two related concepts often contrasted are pairwise coprime (every two distinct members of a set are coprime) and setwise coprime (the gcd of the whole set is 1 even if some pairs share factors). For technical background on computing gcd one can consult resources about the greatest common divisor and algorithms for it.

Examples

  • The numbers 12 and 77 are alien to each other, because their prime factorizations 12 = 2 - 2 - 3 and 77 = 7 - 11 do not contain any common prime factors.
  • The numbers 15 and 25 are not alien to each other, because in their prime factorizations 15 = 3 - 5 and 25 = 5 - 5 the 5 occurs, which is also the ggT(15, 25).
  • The numbers 9, 17, 64 are pairs of divisors, because all three pairs 9 and 17, 17 and 64, 9 and 64 are pairs of divisors.

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

Divisor strangeness occurs, often as a condition, in many number theoretic problems. For example, a condition for the ChineseRemainder Theorem is that the moduli are divisor alien. The Eulerian φ-function assigns to each natural number n the number of numbers that are divisor alien to n in . \{1,\dots ,n\}

Properties

Divider strangeness is a binary relation

{\displaystyle {\text{Teilerfremdheit}}=\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 alien to each other, as are 3 and 4, but not 2 and 4.

The asymptotic probability that two randomly chosen integers aand bare divisorally distinct is

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

where is \zeta the Riemann ζ-function and π \pi is the circle number. This theorem was first proved by Ernesto Cesàro in 1881.

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

Related articles

Author

AlegsaOnline.com Coprime (Relatively Prime) Numbers

URL: https://en.alegsaonline.com/art/22977

Share