# Definition:Coprime/Integers

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

### $5$ and $12$

$5$ and $12$ are coprime.

### $7$ and $27$

$7$ and $27$ are coprime.

### $-9$ and $16$

$-9$ and $16$ are coprime.

### $-18$ and $35$

$-18$ and $35$ are coprime.

### $-27$ and $-35$

$-27$ and $-35$ are coprime.

### $72$ and $91$

$72$ and $91$ are coprime.

## Also see

- Coprime Integers cannot Both be Zero where it is made explicit that coprimality cannot happen if $a = b = 0$

- Coprimality Relation is Non-Reflexive: $\neg a \perp a$ except when $a = \pm 1$

- Coprimality Relation is Symmetric: $a \perp b \iff b \perp a$

- Coprimality Relation is not Antisymmetric: $\neg \paren {a \perp b \land b \perp a \implies a = b}$

- Coprimality Relation is Non-Transitive: for example $2 \perp 3, 3 \perp 4, \neg 2 \perp 4$, and also $2 \perp 3, 3 \perp 5, 2 \perp 5$

- Results about
**coprime integers**can be found**here**.

## Sources

- 1964: Iain T. Adamson:
*Introduction to Field Theory*... (previous) ... (next): Chapter $\text {I}$: Elementary Definitions: $\S 1$. Rings and Fields: Example $4$ - 1964: Walter Ledermann:
*Introduction to the Theory of Finite Groups*(5th ed.) ... (previous) ... (next): Chapter $\text {I}$: The Group Concept: $\S 6$: Examples of Finite Groups: $\text{(iii)}$: Footnote $*$ - 1968: Ian D. Macdonald:
*The Theory of Groups*... (previous) ... (next): Appendix: Elementary set and number theory - 1969: C.R.J. Clapham:
*Introduction to Abstract Algebra*... (previous) ... (next): Chapter $3$: The Integers: $\S 12$. Primes - 1971: George E. Andrews:
*Number Theory*... (previous) ... (next): $\text {2-2}$ Divisibility: Definition $\text {2-3}$ - 1971: Allan Clark:
*Elements of Abstract Algebra*... (previous) ... (next): Chapter $1$: Properties of the Natural Numbers: $\S 23$ - 1978: John S. Rose:
*A Course on Group Theory*... (previous) ... (next): $0$: Some Conventions and some Basic Facts - 1978: Thomas A. Whitelaw:
*An Introduction to Abstract Algebra*... (previous) ... (next): $\S 12$: Highest common factors and Euclid's algorithm - 1980: David M. Burton:
*Elementary Number Theory*(revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Definition $2 \text{-} 3$ - 1982: P.M. Cohn:
*Algebra Volume 1*(2nd ed.) ... (previous) ... (next): Chapter $2$: Integers and natural numbers: $\S 2.2$: Divisibility and factorization in $\mathbf Z$ - 1982: Martin Davis:
*Computability and Unsolvability*(2nd ed.) ... (previous) ... (next): Appendix $1$: Some Results from the Elementary Theory of Numbers: Definition $3$ - 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next):**coprime** - 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next):**relatively prime (coprime)** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next):**coprime** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next):**relatively prime (coprime)** - 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next):**relatively prime**