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

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

## Basic resultsEdit

Theorem: ${\displaystyle p}$  is prime and ${\displaystyle p|ab}$  implies that ${\displaystyle p|a}$  or ${\displaystyle p|b}$ .

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

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

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

When this is multiplied by ${\displaystyle b}$  we arrive at ${\displaystyle b=pbx+aby}$ .

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