# Coprimality Relation is Non-Transitive

Jump to navigation
Jump to search

## Theorem

Consider the coprimality relation on the set of integers:

- $\forall x, y \in \Z: x \perp y \iff \gcd \set {x, y} = 1$

where $\gcd \set {x, y}$ denotes the greatest common divisor of $x$ and $y$.

Then:

- $\perp$ is non-transitive.

## Proof

We have:

\(\displaystyle \gcd \set {2, 3}\) | \(=\) | \(\displaystyle 1\) | |||||||||||

\(\displaystyle \gcd \set {3, 4}\) | \(=\) | \(\displaystyle 1\) | |||||||||||

\(\displaystyle \gcd \set {2, 4}\) | \(=\) | \(\displaystyle 2\) |

Hence we have:

- $2 \perp 3$ and $3 \perp 4$

However, it is not the case that $2 \perp 4$.

Thus $\perp$ is not transitive.

Then we have:

\(\displaystyle \gcd \set {2, 3}\) | \(=\) | \(\displaystyle 1\) | |||||||||||

\(\displaystyle \gcd \set {3, 5}\) | \(=\) | \(\displaystyle 1\) | |||||||||||

\(\displaystyle \gcd \set {2, 5}\) | \(=\) | \(\displaystyle 1\) |

- $2 \perp 3$ and $3 \perp 5$

and also:

- $2 \perp 5$

Thus $\perp$ is not antitransitive either.

The result follows by definition of non-transitive relation.

$\blacksquare$

## Sources

- 1975: T.S. Blyth:
*Set Theory and Abstract Algebra*... (previous) ... (next): $\S 6$. Indexed families; partitions; equivalence relations: Exercise $4 \ \text{(a)}$