User:Ascii/Coprime Relation for Integers is Not Reflexive

From ProofWiki
Jump to navigation Jump to search

Theorem

The relation "is coprime to" on the integers is not reflexive.


That is:

$\exists n \in \Z: \neg n \perp n$

where $\perp$ denotes "is coprime to".


Proof

Consider $2$.

From Integer Divides Itself, $2$ is a divisor of $2$.

From Absolute Value of Integer is not less than Divisors, $2$ is the greatest divisor of $2$.

So, the greatest common divisor of $2$ and itself is $2$: $\gcd \set {2, 2} = 2$

Hence $\neg \, 2 \perp 2$ and $\perp$ is not reflexive.

$\blacksquare$