UFUG 2106 : Discrete

Mathematics
Chapter 04: Elementary Number Theory and Methods
of Proof
Recommended readings:
(1) Textbook: Pages 160-171; 183-187; 190-197; 200-208; 211-216; 218-225; 228-232
(2) Reference book (“Discrete Mathematics and Its Applications”, 8th Edition, Kenneth H.
Rosen):Sec. 4.1.4, 4.1.5 (Pages 254-258); Sec. 4.2.4 (Pages 267-268); Sec. 4.4.1-
4.4.5 (Pages 290-298)
ACK: Part of the PPTs are built from the PPT slides from Instructor’s
Companion Website of the textbook.
Outline
1. Direct Proof and Counterexample I: Introduction
2. Direct Proof and Counterexample II: writing Advice
3. Direct Proof and Counterexample III: Rational Numbers
4. Direct Proof and Counterexample IV: Divisibility
5. Direct Proof and Counterexample V: Division into Cases and the Quotient-
Remainder Theorem
6. Direct Proof and Counterexample VI: Floor and Ceiling
7. Indirect argument: Contradiction and Contraposition
8. Indirect Argument: Two Famous Theorems
9. Application: Algorithms
10. Congruence
2
Learning Outcomes
1. Be able to use the following proof techniques
o Direct proof:
▪ Constructive proof of existence
▪ Disproof by counterexample
▪ Method of exhaustion
▪ Division into cases
o Indirect argument
▪ Contradiction
▪ Contraposition

3
Learning Outcomes
● 2. Understand the foundational concepts in number theory
o Even, odd, prime, composite integers
o Rational numbers, real numbers, floor and ceiling
o Divisibility, multiple, factor, divisor, unique factorization of integers
o Modular operation
o Congruence

● 3. Algorithms
o Be able to read and write formal algorithms
o Learn some key algorithms in number theory

4
Outline
1. Direct Proof and Counterexample I: Introduction
2. Direct Proof and Counterexample II: writing Advice
3. Direct Proof and Counterexample III: Rational Numbers
4. Direct Proof and Counterexample IV: Divisibility
5. Direct Proof and Counterexample V: Division into Cases and the Quotient-
Remainder Theorem
6. Direct Proof and Counterexample VI: Floor and Ceiling
7. Indirect argument: Contradiction and Contraposition
8. Indirect Argument: Two Famous Theorems
9. Application: Algorithms
10. Congruence
5
Direct Proof and Counterexample Ⅰ: Introduction

6
Review of Rules of Inference for Quantified Statements

7
Even, Odd, Prime, and Composite Integers

8
Proving Existential Statements
According to the definition, a statement in the form
∃𝑥 ∈ 𝐷 such that 𝑄(𝑥)
is true if, and only if, 𝑄(𝑥) is true for at least one 𝑥 in 𝐷.

One way to prove this is to find an 𝑥 in 𝐷 that makes 𝑄(𝑥) true.

Another way is to give a set of directions for finding such an 𝑥. Both
methods are called constructive proofs of existence. The logical
principle underlying such a proof is existential generalization.

9
Example 4.1.3 – Constructive Proofs of Existence

a. Prove: ∃ an even integer 𝑛 that can be written in two ways as a

sum of two prime numbers.

b. Suppose that 𝑟 and 𝑠 are integers. Prove: ∃ an integer 𝑘 such that

22𝑟 + 18𝑠 = 2𝑘.

10
Disproving Universal Statements by Counterexample

Example 4.1.4 – Disproof by Counterexample

Disprove the following statement by finding a counterexample
∀ real numbers 𝑎 and 𝑏, if 𝑎2 = 𝑏 2 then 𝑎 = 𝑏

11
Example 4.1.5 – The Method of Exhaustion
Use the method of exhaustion to prove the following statement:

∀𝑛 ∈ 𝒁, if 𝑛 is even and 4 ≤ 𝑛 ≤ 26 then 𝑛 can be written as a sum of

two prime numbers.

12
Proving Universal Statements
The most powerful technique for proving a universal statement is one
that works regardless of the size of the domain over which the
statement is quantified.

It is based on a logical principle universal generalization. A more

descriptive name is generalizing from the generic particular.

13
Proving Universal Statements
When the method of generalizing from the generic particular is applied
to a property of the form “If 𝑃(𝑥) then 𝑄(𝑥),” the result is the method
of direct proof.

14
Example 4.1.7 – A Direct Proof of a Theorem
Prove that the sum of any two even integers is even.

Formal Restatement:
∀ integers 𝑚 and 𝑛, if 𝑚 and 𝑛 are even then 𝑚 + 𝑛 is even.

This statement is universally quantified over an infinite domain. Thus to

prove it in general, you need to show that no matter what two integers
you might be given, if both are even then their sum will also be even.

15
Example 4.1.7 – A Direct Proof of a Theorem
Formal Restatement:
∀ integers 𝑚 and 𝑛, if 𝑚 and 𝑛 are even then 𝑚 + 𝑛 is even.

16
Example 4.1.8 – Identifying the “Starting Point” and
the “Conclusion to Be Shown”

Write the first sentence of a proof (the “starting point”) and the last
sentence of a proof (the “conclusion to be shown”) for the following
statement:
Every complete bipartite graph is connected.

17
Outline
1. Direct Proof and Counterexample I: Introduction
2. Direct Proof and Counterexample II: writing Advice
3. Direct Proof and Counterexample III: Rational Numbers
4. Direct Proof and Counterexample IV: Divisibility
5. Direct Proof and Counterexample V: Division into Cases and the Quotient-
Remainder Theorem
6. Direct Proof and Counterexample VI: Floor and Ceiling
7. Indirect argument: Contradiction and Contraposition
8. Indirect Argument: Two Famous Theorems
9. Application: Algorithms
10. Congruence
18
Directions for Writing Proofs of Universal Statements

Over the years, the following rules of style have become fairly standard for
writing the final versions of proofs:
1. Copy the statement of the theorem to be proved on your paper.
2. Clearly mark the beginning of your proof with the word Proof.
3. Make your proof self-contained. This means that you should explain
the meaning of each variable used in your proof in the body of the proof.
Thus you will begin proofs by introducing the initial variables and stating
what kind of objects they are. The first sentence of your proof would be
something like “Suppose 𝑚 and 𝑛 are any even integers” or “Let 𝑥 be a
real number such that 𝑥 is greater than 2.” This is similar to declaring
variables and their data types at the beginning of a computer program.
19
Directions for Writing Proofs of Universal Statements

4. Write your proof in complete, grammatically correct sentences.

5. Keep your reader informed about the status of each statement in
your proof.
6. Give a reason for each assertion in your proof.
7. Include the “little words and phrases” that make the logic of your
arguments clear.
{Because, Since, Then, Thus, So, Hence, Therefore, Consequently, It
follows that}
{Observe that, Note that, Recall that, But, Now}
8. Display equations and inequalities.
20
Common Mistakes
● Arguing from examples.

Example:
Statement: The sum of any two even integers is even.
Proof: This is true because if 𝑚 = 14 and 𝑛 = 6, which are both even,
then 𝑚 + 𝑛 = 20, which is also even.

21
Common Mistakes
● Using the same letter to mean two different things.

Example:
Suppose m and n are any odd integers. Then by definition of odd, 𝑚 =
2𝑘 + 1 and 𝑛 = 2𝑘 + 1 where 𝑘 is an integer.

22
Common Mistakes
● Jumping to a conclusion.

Example:
Suppose 𝑚 and 𝑛 are any even integers. By definition of even, 𝑚 = 2𝑟
and 𝑛 = 2𝑠 for some integers 𝑟 and 𝑠. Then 𝑚 + 𝑛 = 2𝑟 + 2𝑠. So 𝑚 +
𝑛 is even.

23
Common Mistakes
● Assuming what is to be proved.

Example:
Statement: The product of any two odd integers is odd.
Proof: Suppose 𝑚 and 𝑛 are any odd integers. When any odd integers
are multiplied, their product is odd. Hence 𝑚𝑛 is odd.

24
Common Mistakes
● Confusion between what is known and what is still to be shown.
Example:
Statement: The product of any two odd integers is odd.
Proof: Suppose 𝑚 and 𝑛 are any odd integers. We must show that 𝑚𝑛
is odd. This means that there exists an integer 𝑠 such that
𝑚𝑛 = 2𝑠 + 1.
Also by definition of odd, there exist integers 𝑎 and 𝑏 such that 𝑚 =
2𝑎 + 1 and 𝑛 = 2𝑏 + 1. Then
𝑚𝑛 = (2𝑎 + 1)(2𝑏 + 1) = 2𝑠 + 1.
So, since 𝑠 is an integer, 𝑚𝑛 is odd by definition of odd.
25
Common Mistakes
● Use of any when the correct word is some.

Example:
Suppose 𝑚 is a particular but arbitrarily chosen odd integer. By
definition of odd, 𝑚 = 2𝑎 + 1 for any integer 𝑎.

26
Common Mistakes
● Misuse of the word if.

Example:
Suppose 𝑝 is a prime number. If 𝑝 is prime, then 𝑝 cannot be written
as a product of two smaller positive integers.

27
Outline
1. Direct Proof and Counterexample I: Introduction
2. Direct Proof and Counterexample II: writing Advice
3. Direct Proof and Counterexample III: Rational Numbers
4. Direct Proof and Counterexample IV: Divisibility
5. Direct Proof and Counterexample V: Division into Cases and the Quotient-
Remainder Theorem
6. Direct Proof and Counterexample VI: Floor and Ceiling
7. Indirect argument: Contradiction and Contraposition
8. Indirect Argument: Two Famous Theorems
9. Application: Algorithms
10. Congruence
28
Direct Proof and Counterexample Ⅲ: Rational Numbers

29
Example 4.3.2 – Any Sum of Rational Numbers Is
Rational

30
Outline
1. Direct Proof and Counterexample I: Introduction
2. Direct Proof and Counterexample II: writing Advice
3. Direct Proof and Counterexample III: Rational Numbers
4. Direct Proof and Counterexample IV: Divisibility
5. Direct Proof and Counterexample V: Division into Cases and the Quotient-
Remainder Theorem
6. Direct Proof and Counterexample VI: Floor and Ceiling
7. Indirect argument: Contradiction and Contraposition
8. Indirect Argument: Two Famous Theorems
9. Application: Algorithms
10. Congruence
31
Direct Proof and Counterexample Ⅳ: Divisibility
The notion of divisibility is the central concept of one of the most
beautiful subjects in number theory, the study of properties of integers.

32
Direct Proof and Counterexample Ⅳ: Divisibility
Two useful properties of divisibility:

33
Direct Proof and Counterexample Ⅳ: Divisibility
When the definition of divides is rewritten formally using the
existential quantifier, the result is

Since the negation of an existential statement is universal, it follows

that 𝑑 does not divide 𝑛 if, and only if, ∀ integer 𝑘, 𝑛 ≠ 𝑑𝑘 or 𝑑 = 0; in
other words, the quotient 𝑛 ∕ 𝑑 is not an integer.

34
Properties of Divisibility

35
The Unique Factorization of Integers Theorem
The most comprehensive statement about divisibility of integers is
contained in the unique factorization of integers theorem.
Because of its importance, this theorem is also called the fundamental
theorem of arithmetic.

36
The Unique Factorization of Integers Theorem

Example:
3300 = 100 ⋅ 33 = 4 ⋅ 25 ⋅ 3 ⋅ 11 = 2 ⋅ 2 ⋅ 5 ⋅ 5 ⋅ 3 ⋅ 11 = 22 ⋅ 31 ⋅ 52 ⋅ 111
37
Outline
1. Direct Proof and Counterexample I: Introduction
2. Direct Proof and Counterexample II: writing Advice
3. Direct Proof and Counterexample III: Rational Numbers
4. Direct Proof and Counterexample IV: Divisibility
5. Direct Proof and Counterexample V: Division into Cases and the Quotient-
Remainder Theorem
6. Direct Proof and Counterexample VI: Floor and Ceiling
7. Indirect argument: Contradiction and Contraposition
8. Indirect Argument: Two Famous Theorems
9. Application: Algorithms
10. Congruence
38
Direct Proof and Counterexample Ⅴ: Division into
Cases and the Quotient-Remainder Theorem

If n is positive, the quotient-remainder theorem can be illustrated on

the number line as follows:

39
Direct Proof and Counterexample Ⅴ: Division into
Cases and the Quotient-Remainder Theorem

If n is negative, the picture changes.

40
div and mod

41
Example 4.5.4 – Solving Problems about mod
a. Prove that if 𝑛 is a positive integer, then 𝑛 𝑚𝑜𝑑 10 is the digit in the
ones place in the decimal representation for 𝑛.

b. Suppose 𝑚 is an integer. If 𝑚 𝑚𝑜𝑑 11 = 6, what is 4𝑚 𝑚𝑜𝑑 11?

42
Representations of Integers
We defined an even integer to have the form twice some integer. At
that time we could have defined an odd integer to be one that was not
even.

The fact that any integer is either even or odd is called the parity
property.

Prove that given any two consecutive integers, one is even and the
other is odd.

43
Representations of Integers

44
Example 4.5.7 – The Square of an Odd Integer
Prove: The square of any odd integer has the form 8𝑚 + 1 for some
integer 𝑚.

45
Absolute Value and the Triangle Inequality
The triangle inequality is one of the most important results involving
absolute value. It has applications in many areas of mathematics.

46
Absolute Value and the Triangle Inequality

47
Outline
1. Direct Proof and Counterexample I: Introduction
2. Direct Proof and Counterexample II: writing Advice
3. Direct Proof and Counterexample III: Rational Numbers
4. Direct Proof and Counterexample IV: Divisibility
5. Direct Proof and Counterexample V: Division into Cases and the Quotient-
Remainder Theorem
6. Direct Proof and Counterexample VI: Floor and Ceiling
7. Indirect argument: Contradiction and Contraposition
8. Indirect Argument: Two Famous Theorems
9. Application: Algorithms
10. Congruence
48
Direct Proof and Counterexample Ⅵ: Floor and Ceiling

49
Direct Proof and Counterexample Ⅵ: Floor and Ceiling

50
Example 4.6.4 – Disproving an Alleged Property of
Floor

Are the following statements true or false?

(1) For all real numbers 𝑥 and 𝑦, ⌊𝑥 + 𝑦⌋ = ⌊𝑥⌋ + ⌊𝑦⌋.

(2) For every real number 𝑥 and for every integer 𝑚, ⌊𝑥 + 𝑚⌋ = ⌊𝑥⌋ + 𝑚

51
Direct Proof and Counterexample Ⅵ: Floor and Ceiling

52
Direct Proof and Counterexample Ⅵ: Floor and Ceiling

Given any integer 𝑛 and any positive integer 𝑑, the quotient-remainder

theorem guarantees the existence of unique integers 𝑞 and 𝑟 such that
𝑛 = 𝑑𝑞 + 𝑟 and 0 ≤ 𝑟 < 𝑑.

The following theorem states that the floor notation can be used to describe
q and r as follows:

𝑛 𝑛
𝑞= and 𝑟 = 𝑛 − 𝑑 ⋅ .
𝑑 𝑑

53
Direct Proof and Counterexample Ⅵ: Floor and Ceiling

Thus if, on a calculator or in a computer language, floor is built in but

div and mod are not, div and mod can be defined as follows:
For a nonnegative integer 𝑛 and a positive integer 𝑑,

Note that 𝑑 divides 𝑛 if, and only if, 𝑛 𝑚𝑜𝑑 𝑑 = 0. In floor notation this
means that 𝑑 divides 𝑛 if, and only if, 𝑛 = 𝑑 · 𝑛Τ𝑑 .

54
Outline
1. Direct Proof and Counterexample I: Introduction
2. Direct Proof and Counterexample II: writing Advice
3. Direct Proof and Counterexample III: Rational Numbers
4. Direct Proof and Counterexample IV: Divisibility
5. Direct Proof and Counterexample V: Division into Cases and the Quotient-
Remainder Theorem
6. Direct Proof and Counterexample VI: Floor and Ceiling
7. Indirect argument: Contradiction and Contraposition
8. Indirect Argument: Two Famous Theorems
9. Application: Algorithms
10. Congruence
55
Indirect Argument: Contradiction and Contraposition

56
Example 4.7.1 – There Is No Greatest Integer
Use proof by contradiction to show that there is no greatest integer.

57
Argument by Contraposition

58
Example 4.7.4 – If the Square of an Integer Is Even,
Then the Integer Is Even

Prove that for every integer 𝑛, if 𝑛2 is even then 𝑛 is even.

59
Outline
1. Direct Proof and Counterexample I: Introduction
2. Direct Proof and Counterexample II: writing Advice
3. Direct Proof and Counterexample III: Rational Numbers
4. Direct Proof and Counterexample IV: Divisibility
5. Direct Proof and Counterexample V: Division into Cases and the Quotient-
Remainder Theorem
6. Direct Proof and Counterexample VI: Floor and Ceiling
7. Indirect argument: Contradiction and Contraposition
8. Indirect Argument: Two Famous Theorems
9. Application: Algorithms
10. Congruence
60
(1) The Irrationality of 𝟐

Proof by contradiction

61
(2) Are There Infinitely Many Prime Numbers?

Proof by contradiction

62
Outline
1. Direct Proof and Counterexample I: Introduction
2. Direct Proof and Counterexample II: writing Advice
3. Direct Proof and Counterexample III: Rational Numbers
4. Direct Proof and Counterexample IV: Divisibility
5. Direct Proof and Counterexample V: Division into Cases and the Quotient-
Remainder Theorem
6. Direct Proof and Counterexample VI: Floor and Ceiling
7. Indirect argument: Contradiction and Contraposition
8. Indirect Argument: Two Famous Theorems
9. Application: Algorithms
10. Congruence
63
Application: Algorithms
The word algorithm refers to a step-by-step method for performing
some action.

Examples in daily life

● food preparation recipes
● directions for assembling equipment or hobby kits

Examples in elementary school math

● multidigit addition and subtraction
● multidigit (long) multiplication
64
An Algorithmic Language
The data type of a variable indicates the set in which the variable
takes its values, whether the set of integers, or real numbers, or
character strings, or the set {0, 1} (for a Boolean variable), and so
forth.

An assignment statement gives a value to a variable. It has the form

𝑥≔𝑒
where 𝑥 is a variable and 𝑒 is an expression. This is read “𝑥 is assigned
the value 𝑒” or “let 𝑥 be 𝑒.”

65
An Algorithmic Language
Conditional statements are denoted either

where
● condition is a predicate involving algorithm variables
● 𝑠1 and 𝑠2 are algorithm statements or groups of algorithm
statements.

66
An Algorithmic Language
When ambiguity is possible, however, we may explicitly bind a group
of statements together into a unit by preceding the group with the
word do and following it with the words end do.

67
An Algorithmic Language
A while loop has the form

where condition is a predicate involving algorithm variables. The word

while marks the beginning of the loop, and the words end while
mark its end.

68
An Algorithmic Language

69
An Algorithmic Language
The second form of iteration we will use is a for-next loop. A for-
next loop has the following form:

70
An Algorithmic Language

71
The Division Algorithm
For an integer a and a positive integer d, the quotient-remainder
theorem guarantees the existence of integers q and r such that
𝑎 = 𝑑𝑞 + 𝑟 and 0 ≤ 𝑟 < 𝑑.

72
The Division Algorithm

73
Greatest Common Divisor
The greatest common divisor of two integers 𝑎 and 𝑏 is the largest
integer that divides both 𝑎 and 𝑏.
o Example: the greatest common divisor of 12 and 30 is 6.

74
Example 4.10.5 – Calculating Some gcd’s
a. Find gcd(72, 63).

b. b. Find gcd(1020 , 630 ).

75
The Euclidean Algorithm

76
The Euclidean Algorithm

77
Example 4.10.7 – A Trace Table for the Euclidean
Algorithm

Construct a trace table for Euclidean Algorithm using A = 330 and B =

156.
𝐴 330
/
𝐵 156
𝑎
𝑏
𝑟
gcd
78
Outline
1. Direct Proof and Counterexample I: Introduction
2. Direct Proof and Counterexample II: writing Advice
3. Direct Proof and Counterexample III: Rational Numbers
4. Direct Proof and Counterexample IV: Divisibility
5. Direct Proof and Counterexample V: Division into Cases and the Quotient-
Remainder Theorem
6. Direct Proof and Counterexample VI: Floor and Ceiling
7. Indirect argument: Contradiction and Contraposition
8. Indirect Argument: Two Famous Theorems
9. Application: Algorithms
10. Congruence
79
Congruence Relation
Definition:
If 𝑎 and 𝑏 are integers and 𝑚 is a positive integer, then 𝑎 is congruent
to 𝑏 modulo 𝑚 iff 𝑚|(𝑎 − 𝑏).
Notation:
Notation 𝑎 ≡ 𝑏 (mod 𝑚) indicates that a is congruent to b modulo m.
𝑚 is called the modulus of the congruence. If a is not congruent to b
modulo m, we write 𝑎 ≢ 𝑏 (mod 𝑚).
Property:
Two integers are congruent mod 𝑚 iff they have the same remainder
when divided by 𝑚.
80
Example of Congruence
Is 19 congruent to 4 modulo 6?

Are 16 and 21 congruent modulo 5?

81
Modulus vs mod
● In the context of congruence, 𝑎 ≡ 𝑏 (mod 𝑚) describes a binary
relation on the set of integers.
● In the expression 𝑎 mod 𝑚 = 𝑏, the notation mod denotes a
function (from integers to integers).

Let 𝑎 and 𝑏 be integers and let 𝑚 be a positive integer, then

● Theorem 1: 𝑎 ≡ 𝑏 (mod 𝑚) if and only if 𝑎 mod 𝑚 = 𝑏 mod 𝑚.
● Theorem 2: 𝑎 ≡ 𝑏 (mod 𝑚) if and only if there is an integer 𝑘 such
that 𝑎 = 𝑏 + 𝑘𝑚.

82
Congruences of Sums and Products
Theorem: Let 𝑚 be a positive integer. If 𝑎 ≡ 𝑏 (mod 𝑚) and 𝑐 ≡ 𝑑 (mod 𝑚),
then 𝑎 + 𝑐 ≡ 𝑏 + 𝑑 (mod 𝑚) and 𝑎𝑐 ≡ 𝑏𝑑 (mod 𝑚).
Proof:

Corollary: Let 𝑚 be a positive integer and let 𝑎 and 𝑏 be integers. Then:

● (𝑎 + 𝑏) mod 𝑚 = ((𝑎 mod 𝑚) + (𝑏 mod 𝑚)) mod 𝑚
● 𝑎𝑏 mod 𝑚 = ((𝑎 mod 𝑚)(𝑏 mod 𝑚)) mod 𝑚

83
Example
Find the value of 193 mod 31 4 mod 23.

84
Arithmetic Modulo
Let 𝒁𝑚 denote the set of nonnegative integers less than 𝑚, i.e.,
𝒁𝑚 = {0, 1, … , 𝑚 − 1}
We define two types of arithmetic modulo operations on set 𝒁𝑚 .
● Addition modulo 𝑚: The operation +𝑚 is defined as
𝑎 +𝑚 𝑏 = (𝑎 + 𝑏) mod 𝑚
● Multiplication modulo 𝑚: The operation ⋅𝑚 is defined as
𝑎 ⋅𝑚 𝑏 = (𝑎 ⋅ 𝑏) mod 𝑚
Examples:
o 7 +11 9 = (7 + 9) mod 11 = 5
o 7 ⋅11 9 = (7 ⋅ 9) mod 11 = 8
85
Properties of Arithmetic Modulo
● Closure: If 𝑎, 𝑏 ∈ 𝒁𝑚 , then 𝑎 +𝑚 𝑏 and 𝑎 ⋅𝑚 𝑏 also belong to 𝒁𝑚 .
● Associativity: If 𝑎, 𝑏, 𝑐 ∈ 𝒁𝑚 , then
o 𝑎 +𝑚 𝑏 +𝑚 𝑐 = 𝑎 +𝑚 𝑏 + 𝑚 𝑐
o 𝑎 ⋅𝑚 𝑏 ⋅𝑚 𝑐 = 𝑎 ⋅𝑚 𝑏 ⋅𝑚 𝑐
● Commutativity: If 𝑎, 𝑏 ∈ 𝒁𝑚 , then 𝑎 +𝑚 𝑏 = 𝑏 +𝑚 𝑎 and 𝑎 ⋅𝑚 𝑏 = 𝑏 ⋅𝑚 𝑎
● Identity elements: 0 and 1 are identity elements for addition and
multiplication modulo 𝑚, respectively: 𝑎 +𝑚 0 = 𝑎 and 𝑎 ⋅𝑚 1 = 𝑎
● Additive inverses: For non-zero a ∈ 𝑍𝑚 , 𝑚 − 𝑎 is the additive inverse of a
modulo m. 0 is its own additive inverse.
● Distributivity: If 𝑎, 𝑏, 𝑐 ∈ 𝒁𝑚 , then 𝑎 ⋅𝑚 𝑏 +𝑚 𝑐 = 𝑎 ⋅𝑚 𝑏 +𝑚 (𝑎 ⋅𝑚 𝑐)

86
Linear Congruence and Multiplicative Inverse
Definition: A congruence of the form 𝑎𝑥 ≡ 𝑏 (mod 𝑚), where 𝑚 is a
positive integer, 𝑎, 𝑏 are integers, and 𝑥 is an integer variable, is called
a linear congruence. The solution of the linear congruence are all the
integers 𝑥 that satisfy it.

Definition: An integer 𝑎ത such that 𝑎𝑎

ത ≡ 1 (mod 𝑚) is called a
multiplicative inverse of a modulo 𝑚.
Multiplicative inverses can be used to solve congruences.
o if 𝑎𝑥 ≡ 𝑏 (mod 𝑚) then 𝑎𝑎𝑥 ത (mod 𝑚), and thus 𝑥 ≡ 𝑎𝑏
ത ≡ 𝑎𝑏 ത (mod 𝑚).

87
Example of Multiplicative Inverses
Let 𝑚 = 15.

Find a multiplicative inverse of 8 modulo 15

Find a multiplicative inverse of 7 modulo 15

Find a multiplicative inverse of 5 modulo 15

88
Existence of Multiplicative Inverse
Theorem: If 𝑎 and 𝑚 are relatively prime integers and 𝑚 > 1, then a
multiplicative inverse of a modulo 𝑚 exists. Furthermore, this inverse is
unique modulo 𝑚.
Proof: Since gcd(𝑎, 𝑚) = 1, by Bézout’s Theorem there are integers 𝑠
and 𝑡 such that 𝑠𝑎 + 𝑡𝑚 = 1.
Hence, 𝑠𝑎 + 𝑡𝑚 ≡ 1 (mod 𝑚).
Since 𝑡𝑚 ≡ 0 (mod 𝑚), it follows that 𝑠𝑎 ≡ 1 (mod 𝑚).
Consequently, 𝑠 is a multiplicative inverse of 𝑎 modulo 𝑚.
Uniqueness: Leave as an exercise

89
Bézout’s Theorem
Bézout’s Theorem: If 𝑎 and 𝑏 are positive integers, then there exists integers
𝑠 and 𝑡 such that gcd(𝑎, 𝑏) = 𝑠𝑎 + 𝑡𝑏.
If 𝑎 and 𝑏 are positive integers, then integers 𝑠 and 𝑡 such that gcd(𝑎, 𝑏) =
𝑠𝑎 + 𝑡𝑏 are called Bézout’s coefficients of 𝑎 and 𝑏.
The equation gcd(𝑎, 𝑏) = 𝑠𝑎 + 𝑡𝑏 is called Bézout’s identity.

Extended Euclidean Algorithm to find Bézout’s coefficients:

o Initialization step: Set 𝑠0 = 1, 𝑠1 = 0, 𝑡0 = 0, and 𝑡1 = 1.
o Iterations: for 𝑗 = 2, 3, … , 𝑛:
Let 𝑠𝑗 = 𝑠𝑗−2 – 𝑞𝑗−1 𝑠𝑗−1 and 𝑡𝑗 = 𝑡𝑗−2 – 𝑞𝑗−1 𝑡𝑗−1 , where 𝑞𝑗 are the quotients in
the divisions used when the Euclidean algorithm finds gcd(𝑎, 𝑏).
o Output: 𝑠 = 𝑠𝑛 and 𝑡 = 𝑡𝑛 .
90
Example of Extended Euclidean Algorithm
Problem: Express gcd(252, 198) = 18 as a linear combination of 252 and
198 using the extended Euclidean algorithm.
Solution:
First, the Euclidean algorithm uses the divisions:
We have 𝑞1 = 1, 𝑞2 = 3, 𝑞3 = 1, 𝑞4 = 2.
Set 𝑆0 = 1, 𝑆1 = 0, 𝑡0 = 0, and 𝑡1 = 1, and follow the rule to calculate for
𝑗 = 2, 3, 4, We have:

Finally, we have 18 = 4 × 252 − 5 × 298

91
The Chinese Remainder Theorem
An ancient Chinese puzzle: There are certain things whose number is
unknown. When divided by 3, the remainder is 2; when divided by 5,
the remainder is 3; and when divided by 7, the remainder is 2. What
will be the number of things?
Problem formulation: Suppose the number of things is x. We have:
o 𝑥 ≡ 2 (mod 3)
o 𝑥 ≡ 3 (mod 5)
o 𝑥 ≡ 2 (mod 7)
The Chinese remainder theorem, named after the Chinese heritage of
problems involving systems of linear congruences, states that when the
moduli of a system of linear congruences are pairwise relatively prime,
there is a unique solution of the system modulo the product of the
moduli.
92
The Chinese Remainder Theorem

93
The Chinese Remainder Theorem
Proof

94
Fermat’s Little Theorem

Application Example

95
Applications of Number Theory

96