## Coprime integers |

Look up in Wiktionary, the free dictionary.coprime |

In *a* and *b* are said to be **relatively prime**, **mutually prime**,^{[1]} or **coprime** (also written **co-prime**) if the only positive integer (^{[2]}

The numerator and denominator of a

Standard notations for relatively prime integers a and b are: gcd(*a*, *b*) = 1 and (*a*, *b*) = 1. Graham, Knuth and Patashnik have proposed that the notation be used to indicate that *a* and *b* are relatively prime and that the term "prime" be used instead of coprime (as in a is *prime* to b).^{[3]}

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

The number of integers coprime to a positive integer *n*, between 1 and *n*, is given by *φ*(*n*).

A **coprime** if its elements share no common positive factor except 1. A stronger condition on a set of integers is **pairwise coprime**, which means that *a* and *b* are coprime for every pair (*a*, *b*) of different integers in the set. The set {2, 3, 4} is coprime, but it is not pairwise coprime since 2 and 4 are not relatively prime.

- properties
- coprimality in sets
- coprimality in ring ideals
- probability of coprimality
- generating all coprime pairs
- see also
- notes
- references
- further reading

The numbers 1 and −1 are the only integers coprime to every integer, and they are the only integers that are coprime with 0.

A number of conditions are 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 (seeBézout's identity ). - The integer
*b*has amultiplicative inverse modulo*a*, meaning that there exists an integer*y*such that*by*≡ 1 (mod*a*). In ring-theoretic language,*b*is aunit in thering **Z**/*a***Z**ofintegers modulo *a*. - Every pair of
congruence relations for an unknown integer*x*, of the form*x*≡*k*(mod*a*) and*x*≡*m*(mod*b*), has a solution (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*.^{[4]}

As a consequence of the third point, if *a* and *b* are coprime and *br* ≡ *bs* (*a*), then *r* ≡ *s* (mod *a*).^{[5]} 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} (i.e., modulo *a* it is a product of invertible elements, and therefore invertible);^{[6]} this also follows from the first point by *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*^{m}.

If *a* and *b* are coprime and *a* divides the product *bc*, then *a* divides *c*.^{[7]} 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 *a*, *b*). (See figure 1.)

In a sense that can be made precise, the ^{2} (see

Two *a* and *b* are coprime if and only if the numbers 2^{a} − 1 and 2^{b} − 1 are coprime.^{[8]} As a generalization of this, following easily from the *n* > 1:

Other Languages

العربية: أعداد أولية فيما بينها

বাংলা: সহ-মৌলিক

български: Взаимно прости числа

bosanski: Uzajamno prosti brojevi

català: Nombres coprimers

čeština: Nesoudělná čísla

dansk: Indbyrdes primisk

Deutsch: Teilerfremdheit

eesti: Ühisteguriteta arvud

Ελληνικά: Σχετικά πρώτοι

emiliàn e rumagnòl: Intēr coprìm

español: Números primos entre sí

Esperanto: Interprimo

فارسی: متباین

français: Nombres premiers entre eux

galego: Números primos entre si

한국어: 서로소 아이디얼

Հայերեն: Փոխադարձ պարզ թվեր

Bahasa Indonesia: Koprima (bilangan)

íslenska: Ósamþátta

italiano: Interi coprimi

עברית: מספרים זרים

қазақша: Өзара жай сандар

latviešu: Savstarpēji pirmskaitļi

magyar: Relatív prímek

മലയാളം: സഹ-അഭാജ്യം

монгол: Харилцан анхны тоонууд

Nederlands: Relatief priem

日本語: 互いに素

norsk: Relativt primisk

Plattdüütsch: Relativ prim

polski: Liczby względnie pierwsze

português: Números primos entre si

română: Numere prime între ele

русский: Взаимно простые числа

Simple English: Coprime

slovenčina: Nesúdeliteľnosť

slovenščina: Tuje število

српски / srpski: Узајамно прости бројеви

srpskohrvatski / српскохрватски: Uzajamno prosti brojevi

suomi: Keskenään jaottomat luvut

svenska: Relativt prima

தமிழ்: சார்பகா முழுஎண்கள்

ไทย: จำนวนเฉพาะสัมพัทธ์

тоҷикӣ: Ададҳои байнан сода

Türkçe: Aralarında asal

українська: Взаємно прості числа

Tiếng Việt: Số nguyên tố cùng nhau

粵語: 相對質數

中文: 互質