17
$\begingroup$

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?

  • 12
    "Coprime" is a condition on a collection of numbers (usually a pair), not a number; it means they have no common factors.2011-09-12

4 Answers 4

17

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.

  • 0
    Just to add, any integer is coprime with 1. https://proofwiki.org/wiki/Integer_is_Coprime_to_12016-11-30
8

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$).

For more info see the Wikipedia page.

  • 0
    @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.2011-09-12
4

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\:.\:$

4

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$.

  • 9
    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.2013-04-21