# Prime Number

A natural number is called prime (or a prime number) if its only positive divisors are 1 and itself. Otherwise, is called composite.

Problems:

### Propositions and Theorems (From MATH135)

Prime Factorization (PF) Every natural number can be written as a product of prime.

Euclid’s Theorem (ET) The number of primes is infinite.

Euclid’s Lemma (EL) For all integers and , and prime numbers , if , then or .

Proposition 14 Let be a prime number, be a natural number, and be integers. If , then for some

Unique Factorization Theorem (UFT) Every natural number can be written as a product of prime factors uniquely, apart from the order of factors.

Finding a Prime Factor (FPF) Every natural number is either prime or has a prime factor less than or equal to .

Divisors From Prime Factorization (DFPF) Let and be positive integers, and let
be a way to express as a product of the distinct primes where some or all of the exponents may be zero. The integer

GCD From Prime Factorization (GCD PF) Let and be positive integers, and let
, and be ways to express and as products of the distinct primes , where some or all of the exponents may be zero. We have