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

edit

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

Basic results

edit

Theorem:   is prime and   implies that   or  .

Proof: Let's assume that   is prime and  , and that  . We must show that  .

Let's consider  . Because   is prime, this can equal   or  . Since   we know that  .

By the gcd-identity,   for some  .

When this is multiplied by   we arrive at  .

Because   and   we know that  , and that  , as desired.