Division and Prime

Division

For two natural numbers and , we say divides , written as if there exists integer such that .

Prime

A prime number (or a prime) is a natural number greater than that is not a product of two smaller natural numbers.

e.g. are prime numbers.

Euclidean's Lemma

Let be a prime number. If divides the product , then or .

Fundamental Theorem of Arithmetic

Every integer greater than can either be prime or represented uniquely as a product of prime numbers.

Proof Clearly is a prime. Assume all integers less than or equal to are primes or a product of prime numbers. Suppose is not prime. Then there exists that divides . Thus is a product of primes. Therefore, by principle of induction, we have all integers are either prime or a product of prime numbers.

Corollary

There are infinitely many primes.

Proof Assume there are only finitely many primes, say . Let . Clearly is not a member of thus not prime. Hence is a product of primes. Therefore there exists prime such that , it follows that , yielding a contradiction.

Greatest Common Divisor

The greatest common divisor of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers, denoted as in two integers case.

Lemma

For prime number , .

Euclidean Algorithm

Fermat’s Little Theorem

For every two integers that are coprime, then we have , where is the Euler’s totient function. In particular if is a prime number then .

Proof