# What is a co-prime?

I've never encountered this question in any of my math classes and it just shows up randomly in my comsci class with no further info about it. I've wiki'ed it, but can't even understand that. Could someone explain to me exactly what it is?

-
"Coprime" is a condition on a collection of numbers (usually a pair), not a number; it means they have no common factors. – Qiaochu Yuan Sep 12 '11 at 22:05

As others have said, two numbers are coprime if their highest common factor (or greatest common divisor if you must) is $1$.

You can have the set of positive integers which are coprime to a given number: for example those coprime to $12$ are $1, 5, 7, 11, 13,17,19,23,25,$ and so on.

-
Thanks. I guess other answers are "better" but I stated that I couldn't understand the wiki page on the term. Thanks for understanding that. – Jonathan Sep 13 '11 at 14:00

A number $a$ is not "a coprime"; rather, "coprimeness" is a relation that may or may not hold between two numbers $a$ and $b$. In other words, $a$ and $b$ may or not be "coprime to each other".

What does it mean for $a$ and $b$ to be coprime? That they share no common factors other than $1$, or equivalently, $\gcd(a,b)=1$ (where $\gcd$ denotes the greatest common divisor, see here).

For example, $2$ and $5$ are coprime, because if $d$ is a factor of $2$ and $d$ is also a factor of $5$ (i.e., $d$ is a common factor of $2$ and $5$), then $d$ has to be $1$ (or $-1$, technically). In other words, $\gcd(2,5)=1$.

However, $2$ and $6$ are not coprime, because they share the common factor $2$; and $\gcd(2,6)=2$.

As Qiaochu says, we can extend the definition of coprimeness to any collection of two or more numbers by declaring the set of numbers $\{a_1,a_2,\ldots\}$ to be coprime when any $a_i$ and $a_j$ are coprime (for $i\neq j$).

-
But I think that coprime generalizes relatively prime , meaning $gcd (a,b)=1$ , to $gcd (a,b,c,d,..)=1$ (finite collection, of course) – gary Sep 12 '11 at 22:11
@gary: I think I would treat "coprime" and "relatively prime" as synonyms. Maybe I would say "pairwise" before either term if I wanted to be precise, but I don't think it's necessary. – Zev Chonoles Sep 12 '11 at 22:14
@gary: In the latter case we say the numbers are "pairwise coprime." The pairwiseness means you 'copy and paste' a relation meant for two numbers to every pair of numbers in a collection. – anon Sep 12 '11 at 22:15

By definition, a pair of integers $\rm\:a,b\:$ are coprime if they have only trivial common factors, i.e. $\rm\:gcd(a,b) = 1\:,\:$ i.e. $\rm\:c\ |\ a,b\ \Rightarrow\ c\:|\:1\:.\:$ A set of integers is pairwise coprime if every pair from the set is coprime. The same definition works over any integral domain.

Coprime sets of integers share many of the properties of sets primes, e.g. factorizations into coprimes are unique. In fact in many number theoretic problems it suffices (and is more efficient) to work with coprimes rather than primes, e.g. see section $4.8$ on the concept of a gcd-free basis in Bach and Shallit: Algorithmic Number Theory.

Note: For ideals, some authors use coprime as a synonym for comaximal, i.e. $\rm\:I + J = 1\:.\:$

-

Two numbers are said to be co-prime if they do not have a common factor other than $1$. For example, the factors of $3$ are $1$ and $3$.

-
While what you say is true, it only makes sense to add an answer, especially after so much time and after several good answers have been given, if there is something more to be added. Your answer does not seem to add anything not found in one of the other answers. – robjohn Apr 21 '13 at 16:35

## protected by Jyrki Lahtonen♦Jun 26 '15 at 11:20

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?