Coprimality Relation is Symmetric

From ProofWiki
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 symmetric.


Proof

\(\ds x\) \(\perp\) \(\ds y\)
\(\ds \leadsto \ \ \) \(\ds \gcd \set {x, y}\) \(=\) \(\ds 1\)
\(\ds \leadsto \ \ \) \(\ds \gcd \set {y, x}\) \(=\) \(\ds 1\)
\(\ds \leadsto \ \ \) \(\ds y\) \(\perp\) \(\ds x\)

Hence the result by definition of symmetric relation.

$\blacksquare$


Sources