# 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.