Definition:Coprime/Integers

From ProofWiki
Jump to: navigation, search

Definition

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

Let $\gcd \left\{{a, b}\right\}$ be the greatest common divisor of $a$ and $b$.


Then $a$ and $b$ are coprime if and only if $\gcd \left\{{a, b}\right\} = 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$)


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


Notation

Let $a$ and $b$ be coprime integers, that is, such that $\gcd \left\{{a, b}\right\} = 1$.

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

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


Coprime as a Relation


It can be seen that considered as a relation, $\perp$ is:

$(1): \quad$ Non-reflexive: $a \not \!\! \mathop{\perp} a$ except when $a = \pm 1$
$(2): \quad$ Symmetric: $a \perp b \iff b \perp a$
$(3): \quad$ Not antisymmetric: $\neg \left({a \perp b \land b \perp a \implies a = b}\right)$
$(4): \quad$ Non-transitive: Consider:
$2 \perp 3, 3 \perp 4, 2 \not \!\! \mathop{\perp} 4$
$2 \perp 3, 3 \perp 5, 2 \perp 5$


Also see

  • Results about coprime integers can be found here.


Sources