Definition:Coprime/Euclidean Domain

From ProofWiki
Jump to navigation Jump to search

Definition

Let $\struct {D, +, \times}$ be a Euclidean domain.

Let $U \subseteq D$ be the group of units of $D$.

Let $a, b \in D$ such that $a \ne 0_D$ and $b \ne 0_D$


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

Then $a$ and $b$ are coprime if and only if $d \in U$.


That is, two elements of a Euclidean domain are coprime if and only if their greatest common divisor is a unit of $D$.


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


Sources