Coprime

In mathematics, the integers a and b are said to be coprime or relatively prime if they have no common factor other than 1 or, equivalently, if their greatest common divisor is 1. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French In Mathematics, a divisor of an Integer n, also called a factor of n, is an integer which evenly divides n without In Mathematics, the greatest common divisor (gcd, sometimes known as the greatest common factor (gcf or highest common factor (hcf, of two non-zero

For example, 6 and 35 are coprime, but 6 and 27 are not coprime because they are both divisible by 3. In mathematics Six is the second smallest Composite number, its proper Divisors being 1, 2 and 3. 35 ( thirty-five) is the Natural number following 34 and preceding 36. In mathematics Six is the second smallest Composite number, its proper Divisors being 1, 2 and 3. 27 ( twenty-seven) is the Natural number following 26 and preceding 28. The number 1 is coprime to every integer. Mathematics For any number x: x ·1 = 1· x = x (1 is the multiplicative identity

A fast way to determine whether two numbers are coprime is given by the Euclidean algorithm. In Number theory, the Euclidean algorithm (also called Euclid's algorithm) is an Algorithm to determine the Greatest common divisor (GCD

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

1 Properties
2 Cross notation, group
3 Generalizations
4 Probabilities
5 See also

Properties

Figure 1. The numbers 4 and 9 are coprime because the diagonal does not intersect any other lattice points

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). In Number theory, Bézout's identity or Bézout's lemma is a linear Diophantine equation.
The integer b has a multiplicative inverse modulo a: there exists an integer y such that by ≡ 1 (mod a). In Mathematics, a multiplicative inverse for a number x, denoted by 1&frasl x or x &minus1 is a number which In Mathematics, modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic) is a system of Arithmetic for Integers In other words, b is a unit in the ring Z/aZ of integers modulo a. In Mathematics, a unit in a ( Unital) ring R is an invertible element of R, i In Mathematics, a ring is an Algebraic structure which generalizes the algebraic properties of the Integers though the rational, real In Mathematics, modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic) is a system of Arithmetic for Integers

As a consequence, if a and b are coprime and br ≡ bs (mod a), then r ≡ s (mod a) (because we may "divide by b" when working modulo a). In Mathematics, modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic) is a system of Arithmetic for Integers 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).

If a and b are coprime and a divides a product bc, then a divides c. This can be viewed as a generalisation 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. Euclid's lemma ( Greek) is a generalization of Proposition 30 of Book VII of Euclid's Elements. In Mathematics, a prime number (or a prime) is a Natural number which has exactly two distinct natural number Divisors 1

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). In Mathematics, the Cartesian coordinate system (also called rectangular coordinate system) is used to determine each point uniquely in a plane (See figure 1. )

The probability that two randomly chosen integers are coprime is 6/π² (see pi), which is about 60%. Probability is the likelihood or chance that something is the case or will happen IMPORTANT NOTICE Please note that Wikipedia is not a database to store the millions of digits of π please refrain from adding those to Wikipedia as it could cause technical problems See below.

Two natural numbers a and b are coprime if and only if the numbers 2^a − 1 and 2^b − 1 are coprime. In Mathematics, a natural number (also called counting number) can mean either an element of the set (the positive Integers or an

Cross notation, group

If n≥1 is an integer, the numbers coprime to n, taken modulo n, form a group with multiplication as operation; it is written as (Z/nZ)^× or Z_n^*. The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French In Mathematics, modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic) is a system of Arithmetic for Integers In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element

Generalizations

Two ideals A and B in the commutative ring R are called coprime if A + B = R. In Ring theory, a branch of Abstract algebra, an ideal is a special Subset of a ring. In Mathematics, commutativity is the ability to change the order of something without changing the end result In Mathematics, a ring is an Algebraic structure which generalizes the algebraic properties of the Integers though the rational, real This generalizes Bézout's identity: with this definition, two principal ideals (a) and (b) in the ring of integers Z are coprime if and only if a and b are coprime. In Number theory, Bézout's identity or Bézout's lemma is a linear Diophantine equation. 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

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 is an important statement about coprime ideals. The Chinese remainder theorem is a result about congruences in Number theory and its generalizations in Abstract algebra.

The concept of being relatively prime can also be extended any finite set of integers S = {a₁, a₂, . In Mathematics, a set is called finite if there is a Bijection between the set and some set of the form {1 2. . . . a_n} to mean that the greatest common divisor of the elements of the set is 1. In Mathematics, the greatest common divisor (gcd, sometimes known as the greatest common factor (gcf or highest common factor (hcf, of two non-zero If every pair of integers in the set is relatively prime, then the set is called pairwise relatively prime. In Mathematics, especially Number theory, a set of Integers is said to be pairwise coprime (or pairwise relatively prime, also known as mutually

Every pairwise relatively prime set is relatively prime; however, the converse is not true: {6, 10, 15} 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 $A$ and $B$ , it is reasonable to ask how likely it is that $A$ and $B$ are coprime. In this determination, it is convenient to use the characterization that $A$ and $B$ are coprime if and only if no prime number divides both of them (see Fundamental theorem of arithmetic). In Number theory, the fundamental theorem of arithmetic (or unique-prime-factorization theorem) states that every Natural number greater than 1 can be written

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

$\prod_p^{\infty} \left(1-\frac{1}{p^2}\right) = \left( \prod_p^{\infty} \frac{1}{1-p^{-2}} \right)^{-1} = \frac{1}{\zeta(2)} = \frac{6}{\pi^2}.$

Here ζ refers to the Riemann zeta function, the identity relating the product over primes to ζ(2) is an example of an Euler product, and the evaluation of ζ(2) as π²/6 is the Basel problem, solved by Leonhard Euler in 1735. In Mathematics, the Riemann zeta function, named after German mathematician Bernhard Riemann, is a function of great significance in In Number theory, an Euler product is an Infinite product expansion indexed by Prime numbers p, of a Dirichlet series. The Basel problem is a famous problem in Number theory, first posed by Pietro Mengoli in 1644 and solved by Leonhard Euler in 1735 In general, the probability of $k$ randomly chosen integers being coprime is $1 / ζ(k)$ .

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 $N$ . Then for each upper bound $N$ , there is a probability $P N$ that two randomly chosen numbers are coprime. This will never be exactly $6 / π 2$ , but in the limit as $N \to \infty$ , $P_N \to 6/\pi^2$ .

Dictionary

-adjective

(mathematics, of two or more positive integers) Having no positive integer factors in common, aside from 1.
(mathematics, of a positive integer) Having no positive integer factors, aside from 1, in common with one or more specified other positive integers.

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents