|
In number theory, two integers ''a'' and ''b'' are said to be relatively prime, mutually prime, or coprime (also spelled co-prime)〔Eaton, James S. Treatise on Arithmetic. 1872. May be downloaded from: http://archive.org/details/atreatiseonarit05eatogoog〕 if the only positive integer that evenly divides both of them is 1. That is, the only common positive factor of the two numbers is 1. This is equivalent to their greatest common divisor being 1. The numerator and denominator of a reduced fraction are coprime. In addition to and the notation is sometimes used to indicate that ''a'' and ''b'' are relatively prime. For example, 14 and 15 are coprime, being commonly divisible by only 1, but 14 and 21 are not, because they are both divisible by 7. The numbers 1 and −1 are the only integers coprime to every integer, and they are the only integers to be coprime with 0. A fast way to determine whether two numbers are coprime is given by the Euclidean algorithm. The number of integers coprime to a positive integer ''n'', between 1 and ''n'', is given by Euler's totient function (or Euler's phi function) ''φ''(''n''). A set of integers can also be called coprime if its elements share no common positive factor except 1. A set of integers is said to be pairwise coprime if ''a'' and ''b'' are coprime for every pair (''a'', ''b'') of different integers in it. == Properties == A number of conditions are individually equivalent to ''a'' and ''b'' being coprime: *No prime number divides both ''a'' and ''b''. *There exist integers ''x'' and ''y'' such that ''ax'' + ''by'' = 1 (see Bézout's identity). *The integer ''b'' has a multiplicative inverse modulo ''a'': there exists an integer ''y'' such that ''by'' ≡ 1 (mod ''a''). In other words, ''b'' is a unit in the ring Z/''a''Z of integers modulo ''a''. *Every pair of congruence relations for an unknown integer ''x'', of the form ''x'' ≡ ''k'' (mod ''a'') and ''x'' ≡ ''l'' (mod ''b''), has a solution, as stated by the Chinese remainder theorem; in fact the solutions are described by a single congruence relation modulo ''ab''. *The least common multiple of ''a'' and ''b'' is equal to their product ''ab'', i.e. LCM(''a'', ''b'') = ''ab''. As a consequence of the third point, if ''a'' and ''b'' are coprime and ''br'' ≡ ''bs'' (mod ''a''), then ''r'' ≡ ''s'' (mod ''a''). That is, we may "divide by ''b''" when working modulo ''a''. Furthermore, if ''b''1 and ''b''2 are both coprime with ''a'', then so is their product ''b''1''b''2 (modulo ''a'' it is a product of invertible elements, and therefore invertible); this also follows from the first point by Euclid's lemma, which states that if a prime number ''p'' divides a product ''bc'', then ''p'' divides at least one of the factors ''b'', ''c''. As a consequence of the first point, if ''a'' and ''b'' are coprime, then so are any powers ''a''''k'' and ''b''''l''. 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. 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 on the line segment between the origin and (''a'', ''b''). (See figure 1.) In a sense that can be made precise, the probability that two randomly chosen integers are coprime is 6/π2 (see pi), which is about 61%. 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. As a generalization of this, following easily from Euclidean algorithm in base ''n'' > 1: : 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Coprime integers」の詳細全文を読む スポンサード リンク
|