Definition:Coprime/Integers

From ProofWiki
Jump to navigation Jump to search

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.

(The Elements: Book $\text{VII}$: Definition $12$)


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.

(The Elements: Book $\text{VII}$: Definition $14$)


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.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Coprime/Integers&oldid=670189"