Famous Theorems of Mathematics/Number Theory/Prime Numbers

From Wikibooks, open books for an open world
< Famous Theorems of Mathematics‎ | Number Theory
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:  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.