Famous Theorems of Mathematics/Number Theory/Prime Numbers

From Wikibooks, open books for an open world
Jump to: navigation, search

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.