Definition:Coprime

From ProofWiki
Jump to navigation Jump to search

Definition

GCD Domain

Let $\struct {D, +, \times}$ be a GCD 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 GCD domain are coprime if and only if their greatest common divisor is a unit of $D$.


Euclidean Domain

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


Integers

Let $a$ and $b$ be integers such that $b \ne 0$ and $a \ne 0$ (that is, they are both non-zero).

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} = 1$.


Also known as

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

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