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): $\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