User:Ascii/Coprime Relation for Integers is Non-transitive

From ProofWiki
Jump to navigation Jump to search

Theorem

The relation "is coprime to" on the integers is not non-transitive.


That is, it is neither transitive:

$\neg \, \forall m, n, p \in \Z: m \perp n \land n \perp p \implies m \perp p$

nor antitransitive:

$\neg \, \forall m, n, p \in \Z: m \perp n \land n \perp p \implies m \not \perp p$

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


Proof

Coprime Relation for Integers is Not Transitive

Suppose it is the case that:

$\forall m, n, p \in \Z: m \perp n \land n \perp p \implies m \perp p$


Consider when $m = 2$, $n = 1$, and $p = 2$.

From Divisors of One, the divisors of $1$ are $1$ and $-1$.

From One Divides all Integers, $1$ is a divisor of $2$.

So, $1$ is the greatest common divisor of $1$ and $2$:

$\gcd \set { 2, 1 } = 1$

and by definition of coprime:

$2 \perp 1$ (or $m \perp n$)

From Coprime Relation for Integers is Symmetric we also have:

$1 \perp 2$ (or $n \perp p$)


Now to consider if $2 \perp 2$ (or $m \perp p$).

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$ (or $m \not \perp p$).


Thus from Proof by Counterexample, it is not the case that:

$\forall m, n, p \in \Z: m \perp n \land n \perp p \implies m \perp p$

$\Box$

Coprime Relation for Integers is Not Antitransitive

Suppose it is the case that:

$\forall m, n, p \in \Z: m \perp n \land n \perp p \implies m \not \perp p$


Consider when $m = 1$, $n = -1$, and $p = 1$.

From Divisors of One, the divisors of $1$ are $1$ and $-1$.

So, $1$ is the greatest common divisor of $1$ and $-1$.

So, $1 \perp -1$ (or $m \perp n$).

From Coprime Relation for Integers is Symmetric we also have $-1 \perp 1$ (or $n \perp p$).


However, $1 \perp 1$ (or $m \perp p$).


Thus from Proof by Counterexample, it is not the case that:

$\forall m, n, p \in \Z: m \perp n \land n \perp p \implies m \perp p$

$\blacksquare$

Retrieved from "https://proofwiki.org/w/index.php?title=User:Ascii/Coprime_Relation_for_Integers_is_Non-transitive&oldid=517475"