Definition:Coprime/Integers

(Redirected from Definition:Coprime Integers)

Definition

Let $a$ and $b$ be integers.

Let $\gcd \set {a, b}$ denote the greatest common divisor of $a$ and $b$.

Then $a$ and $b$ are coprime if and only if:

$\gcd \set {a, b}$ exists

and:

$\gcd \set {a, b} = 1$.

In the words of Euclid:

Numbers prime to one another are those which are measured by an unit alone as a common measure.

Relatively Composite

If $\gcd \left\{{a, b}\right\} > 1$, then $a$ and $b$ are relatively composite.

That is, two integers are relatively composite if they are not coprime.

In the words of Euclid:

Numbers composite to one another are those which are measured by some number as a common measure.

Notation

Let $a$ and $b$ be objects which in some context are coprime, that is, such that $\gcd \set {a, b} = 1$.

Then the notation $a \perp b$ is preferred on $\mathsf{Pr} \infty \mathsf{fWiki}$.

If $\gcd \set {a, b} \ne 1$, the notation $a \not \!\! \mathop \perp b$ can be used.

Also denoted as

The notation $\perp$ is not universal.

Other notations to indicate the concept of coprimality include:

• $\gcd \set {a, b} = 1$
• $\map \gcd {a, b} = 1$
• $\tuple {a, b} = 1$

However, the first two are unwieldy and the third notation $\tuple {a, b}$ is overused.

Hence the decision by $\mathsf{Pr} \infty \mathsf{fWiki}$ to use $\perp$.

Also defined as

Some sources gloss over the fact that at least one of $a$ and $b$ must be non-zero for $\gcd \set{ a, b }$ to be defined.

Some sources insist that both $a$ and $b$ be non-zero or strictly positive.

Some sources define $\gcd \set {a, b} = 0$ for $a = b = 0$.

Also known as

The statement $a$ and $b$ are coprime can also be expressed as:

$a$ and $b$ are relatively prime
$a$ and $b$ are mutually prime
$a$ is prime to $b$, and at the same time that $b$ is prime to $a$.

Notation

Let $a$ and $b$ be objects which in some context are coprime, that is, such that $\gcd \set {a, b} = 1$.

Then the notation $a \perp b$ is preferred on $\mathsf{Pr} \infty \mathsf{fWiki}$.

If $\gcd \set {a, b} \ne 1$, the notation $a \not \!\! \mathop \perp b$ can be used.

Examples

$2$ and $5$

$2$ and $5$ are coprime.

$3$ and $8$

$3$ and $8$ are coprime.

$7$ and $27$

$7$ and $27$ are coprime.

$-9$ and $16$

$-9$ and $16$ are coprime.

$-27$ and $-35$

$-27$ and $-35$ are coprime.

Also see

• Results about coprime integers can be found here.