Famous Theorems of Mathematics/Number Theory/Prime Numbers

This page will contain proofs relating to prime numbers. Because the definitions are quite similar, proofs relating to irreducible numbers will also go on this page.

Definition of Prime

A prime number p>1 is one whose only positive divisors are 1 and p.

Basic results

Theorem: $p$ is prime and $p|ab$ implies that $p|a$ or $p|b$.

Proof: Let's assume that $p$ is prime and $p|ab$, and that $p\nmid a$. We must show that $p|b$.

Let's consider $gcd(p,a)$. Because $p$ is prime, this can equal $1$ or $p$. Since $p\nmid a$ we know that $gcd(p,a)=1$.

By the gcd-identity, $gcd(p,a)=1=px+ay$ for some $x,y\in \mathbb{Z}$.

When this is multiplied by $b$ we arrive at $b=pbx+aby$.

Because $p|p$ and $p|ab$ we know that $p|(pbx+aby)$, and that $p|b$, as desired.