Famous Theorems of Mathematics/Number Theory/Prime Numbers

From Wikibooks, open books for an open world
Jump to navigation Jump to 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.