State/Integers are relatively prime iff they have no common prime factors

From SlugmathWiki

Proposition
Proof

Proposition: (Integers are relatively prime iff they have no common prime factors) Suppose that $x,y \in \ZZ$. Then the following two statements are equivalent:

$GCD(x,y) = 1$, i.e. $x$ and $y$ are relatively prime.
There does not exist a prime number $p$ such that $p$ divides $x$ and $p$ divides $y$.

Logical Connections

This statement logically relies on the following definitions and statements: State/Natural numbers can be factored into primes

The following statements and definitions rely on the material of this page: State/Being relatively prime to a product is equivalent to being relatively prime to the factors

To visualize the logical connections between this statements and other items of mathematical knowledge, you can visit the following cluster(s), and click the "Visualize" tab: Clust/Basic number theory

State/Integers are relatively prime iff they have no common prime factors

From SlugmathWiki

Logical Connections

Views

Personal tools

Navigation

Mathematics

Pegagogy

Search

Toolbox

	Suppose that $x,y \in \ZZ$.
	If there exists a prime number $p$ such that $p$ divides $x$ and $p$ divides $y$, then $p$ divides $GCD(x,y)$. It follows that $GCD(x,y) \geq p$, so $GCD(x,y) \neq 1$. Conversely, suppose that $GCD(x,y) \neq 1$. Then, since natural numbers can be factored into primes, it follows that there exists a prime number $p$ dividing $GCD(x,y)$. Since $p$ divides $GCD(x,y)$, and $GCD(x,y)$ divides both $x$ and $y$, it follows that $p$ divides $x$ and $p$ divides $y$.
	Hence $GCD(x,y) = 1$ if and only if there does not exist a prime number $p$ such that $p$ divides $x$ and $p$ divides $y$.