Prime numbers

Definition: Coprime

Let . If , are called coprime.

From Bézout's identity Bézout's identity we thus have that for any coprime numbers there are such that .

Theorem

Let . If and are coprime and , then .

Proof:
We know there are such that . Multiply by and we get Since , divides the left hand side, so it also divides .

Definition: Prime number

A number is prime if and are the divisors of . If a number is not prime, it is called composite.

Theorem

Let be prime and such that . Then for some .

Proof:
We induct on . If the theorem is clear. Now suppose the theorem is true for some , and take numbers such that . If we are done. Otherwise, since is prime, so by Theorem Theorem, which by our induction hypothesis means divides one of .

Theorem: Fundamental Theorem of Arithmetic

Let where . Then can be written uniquely (up to permutation) as a product of prime numbers.

Proof:
We use induction. We know the theorem is true for . Now suppose the theorem is true for every . If is prime, the theorem is also true for . Otherwise, by definition where and . It follows that , so both and can be written as products of prime numbers by our induction hypothesis. Since , we have proven the existence of a prime factorization for every .

Now suppose there are numbers with non-unique prime factorizations. Let be the least such integer. Then for primes and . We know , which by Theorem Theorem means divides some , WLOG, let it be . Since they are both prime, we know . Thus , which contradicts the minimality of .