Coprime

	Email		Print
	Bookmark		Link

Coprime

In mathematics

Mathematics

Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere....
, the integer

Integer

The integers are natural numbers including 0 and their negative and non-negative numberss . They are numbers that can be written without a fractional or decimal component, and fall within the set ....
s a and b are said to be coprime or relatively prime if they have no common factor

Divisor

In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder....
other than 1 or, equivalently, if their greatest common divisor

Greatest common divisor

In mathematics, the greatest common divisor , sometimes known as the greatest common factor or highest common factor , of two non-zero integers, is the largest positive integer that divisor both numbers without remainder....
is 1. The notation a b is sometimes used.

For example, 6

6 (number)

6 is the natural number following 5 and preceding 7 .The SI prefix for 10006 is exa , and for its reciprocal atto ....
and 35

35 (number)

35 is the natural number following 34 and preceding 36 ....
are coprime, but 6

6 (number)

6 is the natural number following 5 and preceding 7 .The SI prefix for 10006 is exa , and for its reciprocal atto ....
and 27

27 (number)

27 is the natural number following 26 and preceding 28 . Twenty-seven is the smallest positive integer requiring four syllables to name in English, though it can be unambiguously defined in just two: "three cubed."...
are not coprime because they are both divisible by 3. The number 1

1 (number)

1 is a number, number names, and the name of the glyph representing that number.It represents a single entity, the unit of counting or measurement....
is coprime to every integer.

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

Euclidean algorithm

In number theory, the Euclidean algorithm is an algorithm to determine the greatest common divisor of two elements of any Euclidean domain . Its major significance is that it does not require factorization the two integers, and it is also significant in that it is one of the oldest algorithms known, dating back to the ancient Greeks....
.

Euler's totient function

Euler's totient function

In number theory, the totient of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n....
(or Euler's phi function) of a positive integer n is the number of integers between 1 and n which are coprime to n.

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

As a consequence, if a and b are coprime and br ≡ bs (mod
Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value — the modulus....
a), then r ≡ s (mod a) (because we may "divide by b" when working modulo a).

Discussion

Ask a question about 'Coprime'

Start a new discussion about 'Coprime'

Answer questions from other users

Full Discussion Forum

Encyclopedia

In mathematics
Mathematics

Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere....
, the integer
Integer

The integers are natural numbers including 0 and their negative and non-negative numberss . They are numbers that can be written without a fractional or decimal component, and fall within the set ....
s a and b are said to be coprime or relatively prime if they have no common factor
Divisor

In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder....
other than 1 or, equivalently, if their greatest common divisor
Greatest common divisor

In mathematics, the greatest common divisor , sometimes known as the greatest common factor or highest common factor , of two non-zero integers, is the largest positive integer that divisor both numbers without remainder....
is 1. The notation a b is sometimes used.

For example, 6
6 (number)

6 is the natural number following 5 and preceding 7 .The SI prefix for 10006 is exa , and for its reciprocal atto ....
and 35
35 (number)

35 is the natural number following 34 and preceding 36 ....
are coprime, but 6
6 (number)

6 is the natural number following 5 and preceding 7 .The SI prefix for 10006 is exa , and for its reciprocal atto ....
and 27
27 (number)

27 is the natural number following 26 and preceding 28 . Twenty-seven is the smallest positive integer requiring four syllables to name in English, though it can be unambiguously defined in just two: "three cubed."...
are not coprime because they are both divisible by 3. The number 1
1 (number)

1 is a number, number names, and the name of the glyph representing that number.It represents a single entity, the unit of counting or measurement....
is coprime to every integer.

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

In number theory, the Euclidean algorithm is an algorithm to determine the greatest common divisor of two elements of any Euclidean domain . Its major significance is that it does not require factorization the two integers, and it is also significant in that it is one of the oldest algorithms known, dating back to the ancient Greeks....
.

Euler's totient function
Euler's totient function

In number theory, the totient of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n....
(or Euler's phi function) of a positive integer n is the number of integers between 1 and n which are coprime to n.

Properties

There are a number of conditions which are equivalent to a and b being coprime:
There exist integers x and y such that ax + by = 1 (see Bézout's identity
Bézout's identity

In number theory, B?zout's identity or B?zout's lemma is a linear equation diophantine equation. It states that if a and b are nonzero integers with greatest common divisor d, then there exist integers x and y such thatAdditionally, d is the least positive integer for which there are integer solutions x and...
).
The integer b has a multiplicative inverse
Multiplicative inverse

In mathematics, a multiplicative inverse or reciprocal for a number x, denoted by 1⁄x or x −1, is a number which when multiplied by x yields the multiplicative identity, 1....
modulo
Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value — the modulus....
a: there exists an integer y such that by ≡ 1 (mod a). In other words, b is a unit
Unit (ring theory)

In mathematics, a unit in a ring R is an invertible element of R, i.e. an element u such that there is a v in R withThat is, u is an invertible element of the multiplicative monoid of R....
in the ring
Ring (mathematics)

In mathematics, a ring is a type of algebraic structure. There is some variation among mathematicians as to exactly what properties a ring is required to have, as described in detail below....
Z/aZ of integers modulo
Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value — the modulus....
a.

As a consequence, if a and b are coprime and br ≡ bs (mod
Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value — the modulus....
a), then r ≡ s (mod a) (because we may "divide by b" when working modulo a). Furthermore, if a and b₁ are coprime, and a and b₂ are coprime, then a and b₁b₂ are also coprime (because the product of units is a unit).

Another consequence is that if b^a-1 ≡ 1 mod a, then a and b^a-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 generalisation of Euclid's lemma
Euclid's lemma

Euclid's lemma is a generalization of Proposition 30 of Book VII of Euclid's Elements. The lemma states thatThis can be written in notation:...
, which states that if p is prime
Prime number

In mathematics, a prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. An infinitude of prime numbers exists, as demonstrated by Euclid around 300 BC....
, 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
Cartesian coordinate system

In mathematics, the Cartesian coordinate system is used to determine each Point uniquely in a Plane through two numbers, usually called the x-coordinate or abscissa and the y-coordinate or ordinate of the point....
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.)

The probability
Probability

Probability, or wikt:chance, is a way of expressing knowledge or belief that an Event will occur or has occurred. In mathematics the concept has been given an exact meaning in probability theory, that is used extensively in such areas of study as mathematics, statistics, finance, gambling, science, and philosophy to draw conclusions about t...
that two randomly chosen integers are coprime is 6/π² (see pi
Pi

Pi or p is a mathematical constant whose value is the ratio of any circle's circumference to its diameter in Euclidean geometry; this is the same value as the ratio of a circle's area to the square of its radius....
), which is about 60%. See below.

Two natural number
Natural number

In mathematics, a natural number can mean either an element of the Set = *n = = ? = ? ...
s a and b are coprime if and only if the numbers 2a − 1 and 2b − 1 are coprime. As a generalization of this, following easily from Euclidean algorithm
Euclidean algorithm

In number theory, the Euclidean algorithm is an algorithm to determine the greatest common divisor of two elements of any Euclidean domain . Its major significance is that it does not require factorization the two integers, and it is also significant in that it is one of the oldest algorithms known, dating back to the ancient Greeks....
in base
Base (mathematics)

In arithmetic, the base refers to the number b in an expression of the form bn. The number n is called the exponent and the expression is known formally as exponentiation of b by n or the exponential of n with base b....
n > 1.

Cross notation, group
If n≥1 and is an integer
Integer

The integers are natural numbers including 0 and their negative and non-negative numberss . They are numbers that can be written without a fractional or decimal component, and fall within the set ....
, the numbers coprime to n, taken modulo
Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value — the modulus....
n, form a group
Group (mathematics)

In mathematics, a group is an algebraic structure consisting of a set together with an Binary operation that combines any two of its element to form a third element....
with multiplication as operation; it is written as (Z/nZ)^× or Z_n^*.

Generalizations

Two ideals A and B in the commutative ring R are called coprime if A + B = R. This generalizes Bézout's identity
Bézout's identity

In number theory, B?zout's identity or B?zout's lemma is a linear equation diophantine equation. It states that if a and b are nonzero integers with greatest common divisor d, then there exist integers x and y such thatAdditionally, d is the least positive integer for which there are integer solutions x and...
: with this definition, two principal ideal
Principal ideal

In ring theory, a branch of abstract algebra, a principal ideal is an ideal I in a ring R that is generated by a single element a of R....
s (a) and (b) in the ring of integers Z are coprime if and only if a and b are coprime.

If the ideals A and B of R are coprime, then AB = A∩B; furthermore, if C is a third ideal such that A contains BC, then A contains C. The Chinese remainder theorem
Chinese remainder theorem

The Chinese remainder theorem is a result about modular arithmetic in number theory and its generalizations in abstract algebra....
is an important statement about coprime ideals.

The concept of being relatively prime can also be extended any finite
Finite set

In mathematics, finite set is a Set that has a finite number of element . For example,is a finite set with five elements. The number of elements of a finite set is a natural number , and is called the cardinality of the set....
set of integers S = to mean that the greatest common divisor
Greatest common divisor

In mathematics, the greatest common divisor , sometimes known as the greatest common factor or highest common factor , of two non-zero integers, is the largest positive integer that divisor both numbers without remainder....
of the elements of the set is 1. If every pair of integers in the set is relatively prime, then the set is called pairwise relatively prime.

Every pairwise relatively prime set is relatively prime; however, the converse is not true: is relatively prime, but not pairwise relative prime. (In fact, each pair of integers in the set has a non-trivial common factor.)

Probabilities

Given two randomly chosen integers and , it is reasonable to ask how likely it is that and are coprime. In this determination, it is convenient to use the characterization that and are coprime if and only if no prime number divides both of them (see Fundamental theorem of arithmetic
Fundamental theorem of arithmetic

In number theory and algebraic number theory, the Fundamental Theorem of Arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers....
).

Intuitively, the probability that any number is divisible by a prime (or any integer), is . Hence the probability that two numbers are both divisible by this prime is , and the probability that at least one of them is not is . Thus the probability that two numbers are coprime is given by a product over all primes,

˜ 0.607927102 ˜ 61%.

Here ζ refers to the Riemann zeta function
Riemann zeta function

In mathematics, the Riemann zeta function, named after Germany mathematician Bernhard Riemann, is a prominent function of great significance in number theory because of its relation to the prime number theorem....
, the identity relating the product over primes to ζ(2) is an example of an Euler product
Euler product

In number theory, an Euler product is an infinite product expansion, indexed by prime numbers p, of a Dirichlet series. The name arose from the case of the Riemann zeta function, where such a product representation was proved by Euler....
, and the evaluation of ζ(2) as π²/6 is the Basel problem
Basel problem

The Basel problem is a famous problem in number theory, first posed by Pietro Mengoli in 1644, and solved by Leonhard Euler in 1735. Since the problem had withstood the attacks of the leading mathematicians of the day, Euler's solution brought him immediate fame when he was twenty-eight....
, solved by Leonhard Euler
Leonhard Euler

Leonhard Paul Euler was a pioneering Swiss mathematician and physicist who spent most of his life in Russia and Germany.Euler made important discoveries in fields as diverse as calculus and graph theory....
in 1735. In general, the probability of randomly chosen integers being coprime is .

There is often confusion about what a "randomly chosen integer" is. One way of understanding this is to assume that the integers are chosen randomly between 1 and an integer . Then for each upper bound , there is a probability that two randomly chosen numbers are coprime. This will never be exactly , but in the limit as , .