Definition:Coprime/Integers

Definition

Let $a$ and $b$ be integers such that $b \ne 0$ and $a \ne 0$ (i.e. they are not both zero).

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

If $\gcd \left\{{a, b}\right\} = 1$, then $a$ and $b$ are coprime, or relatively prime.

Alternatively we can say $a$ is prime to $b$, and at the same time that $b$ is prime to $a$.

As Euclid defined it:

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

(The Elements: Book VII: Definition $12$)

Relatively Composite

If two integers are not coprime, they are relatively composite.

As Euclid defined it:

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

(The Elements: Book VII: Definition $14$)

Notation

If $\gcd \left\{{a, b}\right\} = 1$, then the notation $a \perp b$ is encouraged.

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$

Sources

• Iain T. Adamson: Introduction to Field Theory (1964)... (previous)... (next): $\S 1.1$: Example $4$
• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.4$
• C.R.J. Clapham: Introduction to Abstract Algebra (1969)... (previous)... (next): $\S 3.12$
• George E. Andrews: Number Theory (1971): $\S 2.2$: Definition $2.3$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 23$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 12$