Division and Prime

In this note, we will discuss the basic concepts of number theory. In short, number theory is the study of .

Division

For two integers 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.

Lemma

For prime number , .

Proof By definition of a prime, the only possible divisors of are and . Since , we have .

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

Greatest Common Divisor

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

Proof The existence of is guaranteed by the Bézout’s identity below. The uniqueness of is guaranteed by the definition.

Bézout’s Identity

Let , not both zero. Then the set

has a least element , and .

Euclid's Lemma

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

Proof Suppose , then by the lemma above. By Bézout’s identity, there exists such that . Multiplying both sides by , we have . Since , we have .

Proposition

For integers with , .

Proof We will show that divides and vice versa. Let , then and . Thus and , so . Conversely, let , then and . Note that by Bézout’s identity, there exists such that , so , thus . Therefore, we have .

Euclidean Algorithm

The Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers and .

1. Given two integers .
2. Apply the division algorithm to obtain , where .
3. If , then . Otherwise, replace by and by , and repeat step 2.
   

e.g. To compute , we have the following steps:

1. ;
2. ;
3. .

Thus, .

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 .