= Coprime integers
{wiki}
= Coprimality
{synonym}
= Coprime
{synonym}
Two <integers> $a,b$ are \b[coprime] when their <greatest common divisor> is one:
$$
a,b\text{ are coprime}\quad\Longleftrightarrow\quad\gcd(a,b)=1.
$$
For <positive integers>, this says that the only positive common <divisor> is one. For signed <integers>, use $\gcd(a,b)=\gcd(|a|,|b|)$, with <absolute values>; changing either sign leaves <coprimality> unchanged. With the convention $\gcd(0,0)=0$, zero is <coprime> precisely to $1,-1$, because $\gcd(a,0)=|a|$. Both $1,-1$ are <coprime> to every <integer>. https://darijgrinberg.gitlab.io/floor.pdf[Darij Grinberg, MIT 18.781, Section 1.2: greatest common divisors and coprimality]{ref}
The word concerns shared <prime factors>, not whether either input is a <prime number>. For instance $8=2^3$ and $9=3^2$ are <coprime> <composite numbers>, even though neither is a <square-free integer>. Conversely, $6=2\cdot3$ and $10=2\cdot5$ are <square-free integers> but are not <coprime>. Consecutive <integers> are always <coprime>: any common <divisor> of $n,n+1$ divides their difference one. Thus $14,15$ provide another pair of <coprime> <composite numbers>.
For <positive integers>, let $P(n)$ be the <prime support of an integer>. The equivalent test is
$$
\gcd(a,b)=1\quad\Longleftrightarrow\quad P(a)\cap P(b)=\varnothing.
$$
The <set intersection> of the two <prime supports of an integer> must be the <empty set>. Indeed, any positive common <divisor> greater than one has a <prime factor>, and any shared <prime factor> is a common <divisor> greater than one. Hence <coprimality> depends on which <prime factors> occur, rather than on their <prime valuations>; replacing either input by its <radical of an integer> preserves <coprimality>.
For a list of at least two <integers>, distinguish <pairwise coprimality>, requiring every pair to be <coprime>, from <joint coprimality>, requiring only the <greatest common divisor> of the entire list to be one. For example,
$$
\gcd(6,10,15)=1,\qquad
\gcd(6,10)=2,\quad\gcd(6,15)=3,\quad\gcd(10,15)=5.
$$
No <prime factor> belongs to all three <prime supports of an integer>, yet each pair shares one. By contrast, $4,9,25$ have <pairwise coprimality>. The distinction is presented by Poritz under the names pairwise and mutually relatively prime. https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Yet_Another_Introductory_Number_Theory_Textbook_-_Cryptology_Emphasis_(Poritz)/01:_Well-Ordering_and_Division/1.05:_The_Greatest_Common_Divisor[Jonathan A. Poritz, Yet Another Introductory Number Theory Textbook, Section 1.5]{ref}
\Image[/coprime-squarefree-integers-prime-sharing.png]
{title=<Prime support of an integer> distinguishes <coprime> pairs, <joint coprimality> and <pairwise coprimality>}
{description=Filled cells mark membership in the <prime support of an integer>; empty cells mean the <prime number> does not divide the row label. The first panel has two <coprime integers>; the middle has <joint coprimality> but fails <pairwise coprimality>; the last has <pairwise coprimality>. The columns exhaust all <prime factors> of these eight row entries. This original finite arithmetic diagram shows exact <divisibility>, not sampled probabilities.}
One use is simplifying <fractions>. For a <fraction> $a/b$ with <integer> entries and $b>0$, divide its <numerator> and <denominator> by $d=\gcd(a,b)$ to obtain a <reduced fraction> with <coprime> entries. For example, $42/30=7/5$ since $d=6$, and $-42/30=-7/5$ uses the same $d$. A further common <divisor> would make $d$ too small, so the reduction is complete. In particular, the <reduced fraction> for zero is $0/1$.
Another use is reversible <modular arithmetic>: for an <integer modulus> $m>1$, an <integer> $a$ has a <modular inverse> precisely when $a,m$ are <coprime>. The proof outline uses <Bézout's identity>: $ua+vm=1$ makes $u$ a <modular inverse>, and any inverse relation $ua-km=1$ forces every common <divisor> to divide one. For example, $3\cdot5-2\cdot7=1$ gives $5^{-1}\equiv3\pmod7$, whereas $6$ has no <modular inverse> modulo $10$. Thus <coprimality> is the exact condition allowing division by a residue in <modular arithmetic>. https://ocw.mit.edu/courses/18-200-principles-of-discrete-applied-mathematics-spring-2024/mit18_200_s24_lec15.pdf[Ankur Moitra, MIT 18.200, Lecture 15, Lemmas 1–2 and modular inverses]{ref}
Back to article page
