Discrete Mathematics (H) Lecture 7-9 Notes

Number Theory

The number theory is a branch of mathematics that explores integers and their properties, is the basis of cryptography, coding theory, computer security, e-commerce, etc.

Division

Definition: Division

If and are integers with , we say that divides if there is an integer s.t. , or equivalently is an integer. In this case, we say that is a factor or divisor of , and is a multiple of . We use the notations and .

All integers divisible by can be enumerated as

Example

Let and be two positive integers. How many positive integers not exceeding are divisible by ?

Solution. We count the numbers of integers s.t. . Therefore, there are such positive integers.

Properties of Divisibility

Let be integers. Then the following hold:

• if and , then
• if then for all integers
• if and , then

Corollary

If are integers, where , s.t. and , then whenever and are integers.

Proof. By part (ii) and part (i) of the properties.

Definition: Divisor, Divident, Quotient, and Remainder

If is an integer and a positive integer, then there are unique integers and , with , s.t. . In this case, is called the divisor, is called the dividend, is called the quotient, and is called the remainder. We use the notations and .

Congruence Relation

Definition: Congruence Relation

If and are integers and is a positive integer, then is congruent to modulo if divides , denoted by . This is called congruence and is its modulus.

Tip

Let be a positive integer. The integers and are congruent modulo iff there is an integer s.t. .

and are different:

• is a relation on the set of integers.
• In , the notation denotes a function.

Theorem

Let and be integers, and let be a positive integer. Then iff .

Proof. “If” direction: Since , then , so Let , , . Then But we also have , so This implies . However, since , we have The only multiple of in this inteval is . Therefore Hence, .

“Only if” direction: We have Subtracting we get So , which means

Theorem

Let be a positive integer. If and , then and .

Algebraic Manipulation of Congruences

If , then

• , if

Corollary

Let be a positive integer and let be integers. Then

Arithmetic Modulo

Let be the set of nonnegative integers less than : . We define the following two operations:

Example

We can prove the following properties of the set and the two operations:

• Closure: if , then
• Associativity: if , then and
• Identity elements: and
• Additive inverses: if and , then is an additive inverse of modulo
• Commutativity: if , then
• Distributivity: if , then and

All of these properties made the set and the two operations together a commutative ring.

Group, Ring, Domain

Group

Definition: Group

A set of elements, along with a binary operation , must satisfy the following 4 properties to be called a group:

• Closure: If , then also belongs to
• Associativity:
• Identity element: There is a unique element , s.t. for every , we have
• Inverse: For every , there exists an element, denoted by , s.t.

We use the notation to represent the group.

Definition: Permutation Group

Let denote a sequence of integers through . Denote by the set of all permutations of the sequence .

Define a binary operation on the elements of : for , denotes a re-permutation of the elements of according to the elements of .

Then is called a permutation group.

We can easily verify the properties of group on . But it is not a abelian group.

Definition: Abelian Group

Let be a group, if the operation on the set elements is commutative (i.e. ), the group is called an abelian group.

Ring

Definition: Ring

If is an abelian group, we define one more operation (denoted as multiplication for convenience) to have a ring satisfying the following extra properties:

• Closure: must be closed w.r.t.
• Associativity:
• Distributivity: ,

Definition: Commutative Ring

A ring is commutative if the multiplication operation is commutative for all elements in the ring, i.e. .

Definition: Integral Domain

An integral domain is a commutative ring that satisfies the following two additional properties:

• Identity element: there exists , s.t.
• Nonzero product: for any two nonzero elements, if , then either or must be .

Field

Definition: Field

A field, denoted by , is an integral domain whose elements satisfy the following additional property:

• Multiplicative inverse: for every , there exists an elements , denoted by . s.t. .

Representations of Integers

We may use decimal or binary or octal or hexadecimal or other notations to represent integers.

Definition: Representation of Integers

Let be an integer. Then if is a positive integer, it can be expressed uniquely in the form where is nonnegative, ’s are nonnegative integers less than . The representation of is called the base- expansion of and is denoted by .

To construct the base- expansion of an integer ,

• Divide by to obtain , with .
• The remainder is the rightmost digit in the base- expansion of . Then divide by to get with .
• is the second digit from the right. Continue by successively dividing the quotients by until the quotient is .

Binary Addition of Integers

The time complexity is obviously .

Binary Multiplication of Integers

This algorithm takes shifts and bit additions.

Computing and

This algorithm takes bit operations. But there exist more efficient algorithms with complexity , where : This algorithm takes bit operations.

Binary Modular Exponentiation

We need to successively find , and multiplies together the terms where . This will require bit operations.

Primes and Composites

Definition: Prime

A positive integer that is greater than and is divisible only by and by itself is called a prime.

Definition: Composite

A positive integer that is greater then and is not a prime is called a composite.

Fundamental Theorem of Arithmetic

Every integer greater than can be written uniquely as a prime or as the product of two or more primes where the prime factor are written in order of nondecreasing size.

Theorem

If is composite, then has a prime divisor less than or equal to .

Proof. If is composite, then it has a positive integer factor s.t. by definition. This means that , where is an integer greater than .

Assume that and . Then , contradiction. So either or .

Thus has a divisor less than .

By the Fundamental Theorem of Arithmetic, this divisor is either prime, or is a product of primes. In either case, has a prime divisor less than .

Theorem: Infinite Primes

There are infinitely many primes.

Greatest Common Divisor

Definition: Greatest Common Divisor

Let and be integers, not both . The largest integer s.t. and is called the greatest common divisor of and , denoted by .

Definition: Relatively Prime

The integers and are relatively prime if their greatest common divisor is .

A systematic way to find the gcd is factorization. Let and . Then .

Least Common Multiple

Definition: Least Common Multiple

Let and be integers, not both . The least common multiple of and is the smallest positive integer that is divisible by both and , denoted by .

We can also use the factorization to find the lcm. Let and . Then . From this we can also get

Euclidean Algorithm

Factorization can be cumbersome and time-consuming. But luckily we know a very efficient algorithm to compute the gcd. The Euclidean algorithm: The number of divisions required to find is , where .

Correctness

Lemma

Let , where and are integers. Then .

Proof. Suppose that and . Then also divides . Hence, any common divisor of and must also be a common divisor of and .

Suppose that and . Then also divides . Hence, any common divisor of and must also be a common divisor of and .

Therefore .

Then we can use this lemma to prove the correctness of Euclidean algorithm:

Suppose that and are positive integers with . Let and . So

GCD as Linear Combinations

Theorem: Bezout’s Theorem

If and are positive integers, then there exist integers and s.t. . This is called the Bezout’s identity.

We may use extended Euclidean algorithm to find Bezout’s identity.

Example

So

Corollary of Bezout’s Theorem (1)

If are positive integers s.t. and , then .

Proof. Since , by Bezout’s Theorem there exists and s.t. . This yields . Since , we have , and then .

Corollary of Bezout’s Theorem (2)

If is prime and , then for some .

Uniqueness of Prime Factorization

We prove that a prime factorization of a positive integer where the primes are in nondecreasing order is unique.

Proof. Suppose that the positive integer can be written as a product of primes in two distinct ways Remove all common primes from the factorization to get It then follows that divides for some , contradicting the assumption that and are distinct primes.

Dividing Congruences by an Integer

Theorem

Let be a positive integer and let be integers. If and , then .

Proof. Since , we have . Because , it follows that .

Some Fun Facts About Primes

Definition: Mersenne Primes

Prime numbers of the form , where is a prime, is known as the Mersenne primes.

Goldbach’s Conjecture

Every even integer , is the sum of two primes.

Twin-prime Conjecture

There are infinitely many twin primes, i.e., prime numbers that differ by .

Linear Congruences

Definition: Linear Congruence

A congruence of the form , where is a positive integer, and are integers, and is a variable, is called a linear congruence.

The solutions to a linear congruence are all integers that satisfy the congruence.

Definition: Modular Inverse

An integer s.t. is said to be an inverse of modulo .

One method of solving linear congruences makes use of an inverse if it exists. From , it follows that and then .

Theorem

If and are relatively prime integers and , then an inverse of modulo exists. Furthermore, the inverse is unique modulo .

Proof. Since , there are integers and s.t. . Hence . Since , it follows that . This means that is an inverse of modulo .

To find inverses by hand, we can use the extended Euclidean algorithm:

Example

Find an inverse of modulo :

After finding the inverse, we can solve the congruence by multiplying both sides by .

Theorem

Let and . The congruence has solutions iff . If , then there are exactly solutions. If is a solution, then the other solutions are given by .

Proof.

• “only if” direction: If is a solution, then . Thus, . Since divides , we must have .
• “if” direction: Suppose that . Let . There exist integers s.t. . Multiply both sides by . Then . Let . Then .
• , imply that and . This implies further that , where .

The Chinese Remainder Theorem

Theorem: The Chinese Remainder Theorem

Let be pairwise relatively prime positive integers greater than and arbitrary integers. Then the system has a unique solution modulo .

Proof. Let for and . Since , there is an integer , an inverse of modulo s.t. . Let It is checked that is a solution to the congruences.

Example

Solution. Let , , , . Then and If , i.e., This means  is divisible by each . Since the ​ are pairwise relatively prime, their product ​ is the least common multiple (LCM). Therefore  is divisible by , i.e.,

Example

Compute

Solution. Since , we compute modulo 5 and 13 separately. It is obvious that Then we only need to find modulo 13. We want By Fermat’s Little Theorem, since is prime and , we have So we reduce the exponent modulo . Compute:

Thus, for : So: Therefore: Now compute: Hence:

We have:

Since , write: Then: Find the inverse of 5 modulo 13: Multiply both sides by 8: So: Then: Thus:

Back Substitution

We may also solve systems of linear congruences with pairwise relatively prime moduli by back substitution.

Example

Solution. We first express from the first congruence: Then substitute this into the second congruence: Find the inverse of modulo : So, Substitute back: Substitute this into the third congruence: Since and , we get Substitute back: So the answer is .

Fermat’s Little Theorem and Euler’s Theorem

Theorem: Fermat’s Little Theorem

Let be a prime, and let be an integer s.t. . Then

Example

Find

Solution.

Definition: Euler’s Totient Function

The Euler’s totient function is the number of positive integers coprime to in .

satisfies the following properties:

Theorem: Euler’s Theorem

Let be a positive integer, and let be an integer s.t. . Then

Example

Find .

Solution. Given , , so . Observe that So Since So Then and So

Primitive Roots

Definition: Primitive Root

A primitive root modulo a prime is an integer s.t. every nonzero element of is a power of .

Theorem

There is a primitive root modulo iff or , where is an odd prime.