Coprime

related topics
{math, number, function}

In mathematics, two integers a and b are said to be coprime (also spelled co-prime) or relatively prime if they have no common positive factor other than 1 or, equivalently, if their greatest common divisor is 1.[1] The notation a  \perp  b is sometimes used to indicate that a and b are relatively prime.[2].

For example, 6 and 35 are coprime, but 6 and 27 are not, because they are both divisible by 3. The number 1 is coprime to every integer.

A fast way to determine whether two numbers are coprime is given by the Euclidean algorithm.

Euler's totient function (or Euler's phi function) φ(n) for a positive integer n outputs the number of integers between 1 and n which are coprime to n.

Contents

Properties

There are a number of conditions which are equivalent to a and b being coprime:

As a consequence, if a and b are coprime and brbs (mod a), then rs (mod a) (because we may "divide by b" when working modulo a). Furthermore, if a and b1 are coprime, and a and b2 are coprime, then a and b1b2 are also coprime (because the product of units is a unit).

Another consequence is that if ba-1 ≡ 1 mod a, then a and ba-1 are coprime, hence a and b must also be coprime.

If a and b are coprime and a divides the product bc, then a divides c. This can be viewed as a generalization of Euclid's lemma, which states that if p is prime, and p divides a product bc, then either p divides b or p divides c.

The two integers a and b are coprime if and only if the point with coordinates (a, b) in a Cartesian coordinate system is "visible" from the origin (0,0), in the sense that there is no point with integer coordinates between the origin and (a, b). (See figure 1.)

Full article ▸

related documents
Real analysis
P-complete
Tree (graph theory)
Nial
Epimorphism
Chomsky hierarchy
Codomain
Consistency
Quotient group
Referential transparency (computer science)
Local field
Dual number
Lagrange inversion theorem
Mathematical singularity
Zorn's lemma
Statistical independence
Arithmetic shift
Associativity
Linear cryptanalysis
Group isomorphism
Elementary group theory
Examples of groups
Functional analysis
Arithmetic function
Legendre symbol
Intermediate value theorem
Venn diagram
Grep
Axiom of pairing
Distributivity