# Definition:Coprime/Integers

## Contents

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

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: $\neg a \perp a$ except when $a = \pm 1$
- $(2): \quad$ Symmetric: $a \perp b \iff b \perp a$
- $(3): \quad$ Not antisymmetric: $\neg \paren {a \perp b \land b \perp a \implies a = b}$
- $(4): \quad$ Non-transitive: Consider:
- $2 \perp 3, 3 \perp 4, \neg 2 \perp 4$
- $2 \perp 3, 3 \perp 5, 2 \perp 5$

## Also see

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

## Sources

- 1958: Martin Davis:
*Computability and Unsolvability*... (previous) ... (next): Appendix $1$: Some Results from the Elementary Theory of Numbers: Definition $3$ - 1964: Iain T. Adamson:
*Introduction to Field Theory*... (previous) ... (next): $\S 1.1$: Example $4$ - 1964: Walter Ledermann:
*Introduction to the Theory of Finite Groups*(5th ed.) ... (previous) ... (next): $\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): $\S 3.12$ - 1971: George E. Andrews:
*Number Theory*... (previous) ... (next): $\S 2.2$: Definition $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 - 1982: P.M. Cohn:
*Algebra Volume 1*(2nd ed.) ... (previous) ... (next): $\S 2.2$: Divisibility and factorization in $\mathbf Z$ - 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