Prime iff Coprime to all Smaller Positive Integers

From ProofWiki
Jump to: navigation, search

Theorem

Let $p$ be a prime number

Then:

$\forall x \in \Z, 0 < x < p: x \perp p$

That is, $p$ is relatively prime to all smaller (strictly) positive integers.


Proof

From Prime not Divisor implies Coprime, if $p$ does not divide an integer $x$, it is relatively prime to $x$.

From Integer Absolute Value not less than Divisors: Corollary, $p$ does not divide an integer smaller than $p$.

It follows that $p$ is relatively prime to all smaller (strictly) positive integers.

The special case when $x = 0$ is excluded as from Integers Coprime to Zero, $p$ is not relatively prime to $0$.

$\blacksquare$


Sources