The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Chapter 4. Number Theory and

Cryptography

Lai Văn Phút

Ngày 1 tháng 5 năm 2023

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Contents

1. The Integers and Division

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Contents

1. The Integers and Division

2. Integers and Algorithms

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Contents

1. The Integers and Division

2. Integers and Algorithms
3. Primes and Greatest Common Divisors

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Division

Definition. Let a and b are integers, then b is said to be

divisible by a (or b is a multiple of a, or a is a divisor of b,
or a divides b), if there exists an integer k such that
b = ka. We also write a |b

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Division

Definition. Let a and b are integers, then b is said to be

divisible by a (or b is a multiple of a, or a is a divisor of b,
or a divides b), if there exists an integer k such that
b = ka. We also write a |b
Example.
1. 3 ∤ 13

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Division

Definition. Let a and b are integers, then b is said to be

divisible by a (or b is a multiple of a, or a is a divisor of b,
or a divides b), if there exists an integer k such that
b = ka. We also write a |b
Example.
1. 3 ∤ 13
2. 4 | 12

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Division

Definition. Let a and b are integers, then b is said to be

divisible by a (or b is a multiple of a, or a is a divisor of b,
or a divides b), if there exists an integer k such that
b = ka. We also write a |b
Example.
1. 3 ∤ 13
2. 4 | 12
3. Let n and d be positive integer. How many positive
integers not exceeding (≤) n are divisible by d ?

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Division algorithm

Let a be an integer and d a positive integer. Then there
are unique integers q and r such that

a = dq + r, 0 ≤ r < d

• d is called the divisor (số chia),

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Division algorithm

Let a be an integer and d a positive integer. Then there
are unique integers q and r such that

a = dq + r, 0 ≤ r < d

• d is called the divisor (số chia),

• a the dividend (số bị chia),

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Division algorithm

Let a be an integer and d a positive integer. Then there
are unique integers q and r such that

a = dq + r, 0 ≤ r < d

• d is called the divisor (số chia),

• a the dividend (số bị chia),
• q the quotient (thương) and r the remainder (số dư).

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Division algorithm

Let a be an integer and d a positive integer. Then there
are unique integers q and r such that

a = dq + r, 0 ≤ r < d

• d is called the divisor (số chia),

• a the dividend (số bị chia),
• q the quotient (thương) and r the remainder (số dư).

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Division algorithm

Let a be an integer and d a positive integer. Then there
are unique integers q and r such that

a = dq + r, 0 ≤ r < d

• d is called the divisor (số chia),

• a the dividend (số bị chia),
• q the quotient (thương) and r the remainder (số dư).
Note. We also write q = a div d, r = a mod d.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Division algorithm

Let a be an integer and d a positive integer. Then there
are unique integers q and r such that

a = dq + r, 0 ≤ r < d

• d is called the divisor (số chia),

• a the dividend (số bị chia),
• q the quotient (thương) and r the remainder (số dư).
Note. We also write q = a div d, r = a mod d.
Example.
1. Find the quotient and the remainder in the division of
101 by 11

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Division algorithm

Let a be an integer and d a positive integer. Then there
are unique integers q and r such that

a = dq + r, 0 ≤ r < d

• d is called the divisor (số chia),

• a the dividend (số bị chia),
• q the quotient (thương) and r the remainder (số dư).
Note. We also write q = a div d, r = a mod d.
Example.
1. Find the quotient and the remainder in the division of
101 by 11
2. Find the quotient and the remainder in the division of
–11 by 3
Lai Văn Phút Chapter 4. Number Theory and Cryptography
The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Quizz

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Quizz

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Congruences (đồng dư)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Congruences (đồng dư)

6|(17 − 5)?

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Congruences (đồng dư)

6|(17 − 5)?→ 17 ≡ 5 mod 6

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Congruences (đồng dư)

6|(17 − 5)?→ 17 ≡ 5 mod 6

Example. Are the following congruences true?

• 17 ≡ 5 (mod 6)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Congruences (đồng dư)

6|(17 − 5)?→ 17 ≡ 5 mod 6

Example. Are the following congruences true?

• 17 ≡ 5 (mod 6)
• 24 ≡ 14 (mod 6)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Theorem

1. Let a, b be integers and m is a positive integer. Then

a ≡ b (mod m) if and only if a mod m = b mod m.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Theorem

1. Let a, b be integers and m is a positive integer. Then

a ≡ b (mod m) if and only if a mod m = b mod m.
2. Let a, b be integers and m is a positive integer. Then
a ≡ b (mod m) if and only if there is an integer k such
that a = b + km.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Theorem

1. Let a, b be integers and m is a positive integer. Then

a ≡ b (mod m) if and only if a mod m = b mod m.
2. Let a, b be integers and m is a positive integer. Then
a ≡ b (mod m) if and only if there is an integer k such
that a = b + km.
3. let m is a positive integer. If a ≡ b (mod m) and c ≡ d
(mod m), then a + c ≡ b + d (mod m) and ac ≡ bd
(mod m).

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Theorem

1. Let a, b be integers and m is a positive integer. Then

a ≡ b (mod m) if and only if a mod m = b mod m.
2. Let a, b be integers and m is a positive integer. Then
a ≡ b (mod m) if and only if there is an integer k such
that a = b + km.
3. let m is a positive integer. If a ≡ b (mod m) and c ≡ d
(mod m), then a + c ≡ b + d (mod m) and ac ≡ bd
(mod m).

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Theorem

1. Let a, b be integers and m is a positive integer. Then

a ≡ b (mod m) if and only if a mod m = b mod m.
2. Let a, b be integers and m is a positive integer. Then
a ≡ b (mod m) if and only if there is an integer k such
that a = b + km.
3. let m is a positive integer. If a ≡ b (mod m) and c ≡ d
(mod m), then a + c ≡ b + d (mod m) and ac ≡ bd
(mod m).
Corollary. Let a, b are integers and m is a positive integer.
Then
1. (a + b) mod m = (a mod m+b mod m)(mod m)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Theorem

1. Let a, b be integers and m is a positive integer. Then

a ≡ b (mod m) if and only if a mod m = b mod m.
2. Let a, b be integers and m is a positive integer. Then
a ≡ b (mod m) if and only if there is an integer k such
that a = b + km.
3. let m is a positive integer. If a ≡ b (mod m) and c ≡ d
(mod m), then a + c ≡ b + d (mod m) and ac ≡ bd
(mod m).
Corollary. Let a, b are integers and m is a positive integer.
Then
1. (a + b) mod m = (a mod m+b mod m)(mod m)
2. (ab) mod m = ((a mod m)(b mod m))(mod m)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Applications of Congruences: Cryptography (mật

mã)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Applications of Congruences: Cryptography (mật

mã)

f : Z26 → Z26 , f (p) = (p + k ) mod 26: bijection

• Encryption (mã hóa) f (p) = (p + k ) mod 26

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Applications of Congruences: Cryptography (mật

mã)

f : Z26 → Z26 , f (p) = (p + k ) mod 26: bijection

• Encryption (mã hóa) f (p) = (p + k ) mod 26
• Decryption (giải mã) f −1 (p) = (p − k ) mod 26

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Example.

Example.
1. What is the secret message produced from the
message “MEET YOU IN THE PARK” using the Caesar
cipher (k=3)?

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Example.

Example.
1. What is the secret message produced from the
message “MEET YOU IN THE PARK” using the Caesar
cipher (k=3)?
2. Decrypt the ciphertext message “LEWLYPLUJL PZ H
NYLHA ALHJOLY” that was encrypted with the shift
cipher with shift k = 7.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Example.

Example.
1. What is the secret message produced from the
message “MEET YOU IN THE PARK” using the Caesar
cipher (k=3)?
2. Decrypt the ciphertext message “LEWLYPLUJL PZ H
NYLHA ALHJOLY” that was encrypted with the shift
cipher with shift k = 7.
3. What letter replaces the letter K when the function
f (p) = (7p + 3)mod26 is used for encryption?

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Quizz

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Applications of Congruences: Pseudorandom

Numbers (số giả ngẫu nhiên)

xn+1 = (axn + c ) mod m

Notes.
• a: Multiplier (nhân tử) (2 ≤ a < m)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Applications of Congruences: Pseudorandom

Numbers (số giả ngẫu nhiên)

xn+1 = (axn + c ) mod m

Notes.
• a: Multiplier (nhân tử) (2 ≤ a < m)
• c: Increment (số gia) (0 ≤< m)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Applications of Congruences: Pseudorandom

Numbers (số giả ngẫu nhiên)

xn+1 = (axn + c ) mod m

Notes.
• a: Multiplier (nhân tử) (2 ≤ a < m)
• c: Increment (số gia) (0 ≤< m)
• x0 : seed (hạt giống) (0 ≤ x0 < m)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Applications of Congruences: Pseudorandom

Numbers (số giả ngẫu nhiên)

xn+1 = (axn + c ) mod m

Notes.
• a: Multiplier (nhân tử) (2 ≤ a < m)
• c: Increment (số gia) (0 ≤< m)
• x0 : seed (hạt giống) (0 ≤ x0 < m)
• m: modulus (mođun)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Applications of Congruences: Pseudorandom

Numbers (số giả ngẫu nhiên)

xn+1 = (axn + c ) mod m

Notes.
• a: Multiplier (nhân tử) (2 ≤ a < m)
• c: Increment (số gia) (0 ≤< m)
• x0 : seed (hạt giống) (0 ≤ x0 < m)
• m: modulus (mođun)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Applications of Congruences: Pseudorandom

Numbers (số giả ngẫu nhiên)

xn+1 = (axn + c ) mod m

Notes.
• a: Multiplier (nhân tử) (2 ≤ a < m)
• c: Increment (số gia) (0 ≤< m)
• x0 : seed (hạt giống) (0 ≤ x0 < m)
• m: modulus (mođun)
Example.(Random numbers from 0 to 8) Find the
sequence of pseudorandom numbers generated by the
linear congruential method with modulus m = 9, multiplier
a = 7, increment c = 4, and seed x0 = 3.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Applications of Congruences: Pseudorandom

Numbers (số giả ngẫu nhiên)

xn+1 = (axn + c ) mod m

Notes.
• a: Multiplier (nhân tử) (2 ≤ a < m)
• c: Increment (số gia) (0 ≤< m)
• x0 : seed (hạt giống) (0 ≤ x0 < m)
• m: modulus (mođun)
Example.(Random numbers from 0 to 8) Find the
sequence of pseudorandom numbers generated by the
linear congruential method with modulus m = 9, multiplier
a = 7, increment c = 4, and seed x0 = 3.m = 9, a = 7, c =
4, x0 = 3 =⇒ xn+1 = 7xn + 4
Lai Văn Phút Chapter 4. Number Theory and Cryptography
The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Applications of Congruences: Pseudorandom

Numbers (số giả ngẫu nhiên)

xn+1 = (axn + c ) mod m

Notes.
• a: Multiplier (nhân tử) (2 ≤ a < m)
• c: Increment (số gia) (0 ≤< m)
• x0 : seed (hạt giống) (0 ≤ x0 < m)
• m: modulus (mođun)
Example.(Random numbers from 0 to 8) Find the
sequence of pseudorandom numbers generated by the
linear congruential method with modulus m = 9, multiplier
a = 7, increment c = 4, and seed x0 = 3.m = 9, a = 7, c =
4, x0 = 3 =⇒ xn+1 = 7xn + 4 =⇒ x1 , x2 , ...
Lai Văn Phút Chapter 4. Number Theory and Cryptography
The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Example.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Applications of Congruences: Hashing Function

H (k ) = k mod m
Using in searching data in memory
• k: data searched,

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Applications of Congruences: Hashing Function

H (k ) = k mod m
Using in searching data in memory
• k: data searched,
• m: memory block.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Applications of Congruences: Hashing Function

H (k ) = k mod m
Using in searching data in memory
• k: data searched,
• m: memory block.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Applications of Congruences: Hashing Function

H (k ) = k mod m
Using in searching data in memory
• k: data searched,
• m: memory block.
Example. Find the memory locations assigned by the
hashing function h(k ) = k mod 111 to the records of
customers with Social Security numbers 064212848 and
037149212.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Representations of Integers

n = ak bk + ak −1 bk −1 + ... + a1 b + a0 . Denote (ak ak −1 ...a1 a0 )b

Notes.
• n: positive integer.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Representations of Integers

n = ak bk + ak −1 bk −1 + ... + a1 b + a0 . Denote (ak ak −1 ...a1 a0 )b

Notes.
• n: positive integer.
• b > 1: integer.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Representations of Integers

n = ak bk + ak −1 bk −1 + ... + a1 b + a0 . Denote (ak ak −1 ...a1 a0 )b

Notes.
• n: positive integer.
• b > 1: integer.
• a0 , a1 , ..., ak < b, ak ̸= 0: nonnegative integer.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Representations of Integers

n = ak bk + ak −1 bk −1 + ... + a1 b + a0 . Denote (ak ak −1 ...a1 a0 )b

Notes.
• n: positive integer.
• b > 1: integer.
• a0 , a1 , ..., ak < b, ak ̸= 0: nonnegative integer.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Representations of Integers

n = ak bk + ak −1 bk −1 + ... + a1 b + a0 . Denote (ak ak −1 ...a1 a0 )b

Notes.
• n: positive integer.
• b > 1: integer.
• a0 , a1 , ..., ak < b, ak ̸= 0: nonnegative integer.
This is the base b expansion of the integer n.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Representations of Integers

n = ak bk + ak −1 bk −1 + ... + a1 b + a0 . Denote (ak ak −1 ...a1 a0 )b

Notes.
• n: positive integer.
• b > 1: integer.
• a0 , a1 , ..., ak < b, ak ̸= 0: nonnegative integer.
This is the base b expansion of the integer n.
Examples.
1. (241)10 = ?

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Representations of Integers

n = ak bk + ak −1 bk −1 + ... + a1 b + a0 . Denote (ak ak −1 ...a1 a0 )b

Notes.
• n: positive integer.
• b > 1: integer.
• a0 , a1 , ..., ak < b, ak ̸= 0: nonnegative integer.
This is the base b expansion of the integer n.
Examples.
1. (241)10 = ?

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Representations of Integers

n = ak bk + ak −1 bk −1 + ... + a1 b + a0 . Denote (ak ak −1 ...a1 a0 )b

Notes.
• n: positive integer.
• b > 1: integer.
• a0 , a1 , ..., ak < b, ak ̸= 0: nonnegative integer.
This is the base b expansion of the integer n.
Examples.
1. (241)10 = ? → (241)10 = 2.102 + 4.101 + 1.100 = 241
2. (7016)8 = ?

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Representations of Integers

n = ak bk + ak −1 bk −1 + ... + a1 b + a0 . Denote (ak ak −1 ...a1 a0 )b

Notes.
• n: positive integer.
• b > 1: integer.
• a0 , a1 , ..., ak < b, ak ̸= 0: nonnegative integer.
This is the base b expansion of the integer n.
Examples.
1. (241)10 = ? → (241)10 = 2.102 + 4.101 + 1.100 = 241
2. (7016)8 = ?

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Representations of Integers

n = ak bk + ak −1 bk −1 + ... + a1 b + a0 . Denote (ak ak −1 ...a1 a0 )b

Notes.
• n: positive integer.
• b > 1: integer.
• a0 , a1 , ..., ak < b, ak ̸= 0: nonnegative integer.
This is the base b expansion of the integer n.
Examples.
1. (241)10 = ? → (241)10 = 2.102 + 4.101 + 1.100 = 241
2. (7016)8 = ? →
(7016)8 = 7.83 + 0.82 + 1.81 + 6.80 = 3598 = (3598)10
3. Suppose that the letters A through F represent the
digits corresponding to the numbers 10 through 15 (in
decimal notation). Find (2AE0B )16
Lai Văn Phút Chapter 4. Number Theory and Cryptography
The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Representations of Integers

n = ak bk + ak −1 bk −1 + ... + a1 b + a0 . Denote (ak ak −1 ...a1 a0 )b

Notes.
• n: positive integer.
• b > 1: integer.
• a0 , a1 , ..., ak < b, ak ̸= 0: nonnegative integer.
This is the base b expansion of the integer n.
Examples.
1. (241)10 = ? → (241)10 = 2.102 + 4.101 + 1.100 = 241
2. (7016)8 = ? →
(7016)8 = 7.83 + 0.82 + 1.81 + 6.80 = 3598 = (3598)10
3. Suppose that the letters A through F represent the
digits corresponding to the numbers 10 through 15 (in
decimal notation). Find (2AE0B )16
Lai Văn Phút Chapter 4. Number Theory and Cryptography
The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Representations of Integers

n = ak bk + ak −1 bk −1 + ... + a1 b + a0 . Denote (ak ak −1 ...a1 a0 )b

Notes.
• n: positive integer.
• b > 1: integer.
• a0 , a1 , ..., ak < b, ak ̸= 0: nonnegative integer.
This is the base b expansion of the integer n.
Examples.
1. (241)10 = ? → (241)10 = 2.102 + 4.101 + 1.100 = 241
2. (7016)8 = ? →
(7016)8 = 7.83 + 0.82 + 1.81 + 6.80 = 3598 = (3598)10
3. Suppose that the letters A through F represent the
digits corresponding to the numbers 10 through 15 (in
decimal notation). Find (2AE0B )16 →= 175627
Lai Văn Phút Chapter 4. Number Theory and Cryptography
The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Common Bases Expansions

• Decimal Expansions (b = 10) (thập phân)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Common Bases Expansions

• Decimal Expansions (b = 10) (thập phân)

• Binary Expansions (b = 2) (nhị phân)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Common Bases Expansions

• Decimal Expansions (b = 10) (thập phân)

• Binary Expansions (b = 2) (nhị phân)
• Octal Expansions (b = 8) (bát phân)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Common Bases Expansions

• Decimal Expansions (b = 10) (thập phân)

• Binary Expansions (b = 2) (nhị phân)
• Octal Expansions (b = 8) (bát phân)
• Hexadecimal Expansions (b = 16) (thập lục phân)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Examples.

a. Find 2 expansion of (241)10

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Examples.

a. Find 2 expansion of (241)10

b. Find 8 expansion of (12345)10

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Examples.

a. Find 2 expansion of (241)10

b. Find 8 expansion of (12345)10
c. Find 16 expansion of (177130)10

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Constructing Base b Expansions

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Constructing Base b Expansions

Example. Find base 2 expansion of 241.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Quizz

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Quizz

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Addition

Rules.
0 + 0 = 0, 1 + 0 = 1, 1 + 1 = 0( remind 1)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Addition

Rules.
0 + 0 = 0, 1 + 0 = 1, 1 + 1 = 0( remind 1)
Add a = (1110)2 and b = (1011)2

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Addition

Rules.
0 + 0 = 0, 1 + 0 = 1, 1 + 1 = 0( remind 1)
Add a = (1110)2 and b = (1011)2

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Addition

Rules.
0 + 0 = 0, 1 + 0 = 1, 1 + 1 = 0( remind 1)
Add a = (1110)2 and b = (1011)2

1 = 0.2 + 1

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Addition

Rules.
0 + 0 = 0, 1 + 0 = 1, 1 + 1 = 0( remind 1)
Add a = (1110)2 and b = (1011)2

1 = 0.2 + 1
2 = 1.2 + 0

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Addition

Rules.
0 + 0 = 0, 1 + 0 = 1, 1 + 1 = 0( remind 1)
Add a = (1110)2 and b = (1011)2

1 = 0.2 + 1
2 = 1.2 + 0
2 = 1.2 + 0

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Addition

Rules.
0 + 0 = 0, 1 + 0 = 1, 1 + 1 = 0( remind 1)
Add a = (1110)2 and b = (1011)2

1 = 0.2 + 1
2 = 1.2 + 0
2 = 1.2 + 0
3 = 1.2 + 1

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Addition

Rules.
0 + 0 = 0, 1 + 0 = 1, 1 + 1 = 0( remind 1)
Add a = (1110)2 and b = (1011)2

1 = 0.2 + 1
2 = 1.2 + 0
2 = 1.2 + 0
3 = 1.2 + 1
1 = 0.2 + 1

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Addition

Rules.
0 + 0 = 0, 1 + 0 = 1, 1 + 1 = 0( remind 1)
Add a = (1110)2 and b = (1011)2

1 = 0.2 + 1
2 = 1.2 + 0
2 = 1.2 + 0
3 = 1.2 + 1
1 = 0.2 + 1

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Addition

Rules.
0 + 0 = 0, 1 + 0 = 1, 1 + 1 = 0( remind 1)
Add a = (1110)2 and b = (1011)2

1 = 0.2 + 1
2 = 1.2 + 0
2 = 1.2 + 0
3 = 1.2 + 1
1 = 0.2 + 1
Thus, (1110)2 + (1011)2 = (11001)2
Lai Văn Phút Chapter 4. Number Theory and Cryptography
The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Difference

Rules.
• 0−0 = 0

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Difference

Rules.
• 0−0 = 0
• 1−0 = 1

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Difference

Rules.
• 0−0 = 0
• 1−0 = 1
• 1−1 = 0

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Difference

Rules.
• 0−0 = 0
• 1−0 = 1
• 1−1 = 0
• 0 − 1 = 1( remind − 1)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Difference

Rules.
• 0−0 = 0
• 1−0 = 1
• 1−1 = 0
• 0 − 1 = 1( remind − 1)
• −1 − 1 = 0( remind − 1)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Difference

Rules.
• 0−0 = 0
• 1−0 = 1
• 1−1 = 0
• 0 − 1 = 1( remind − 1)
• −1 − 1 = 0( remind − 1)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Difference

Rules.
• 0−0 = 0
• 1−0 = 1
• 1−1 = 0
• 0 − 1 = 1( remind − 1)
• −1 − 1 = 0( remind − 1)
Let a = (1110)2 and b = (1011)2 . Find a − b

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Difference

Rules.
• 0−0 = 0
• 1−0 = 1
• 1−1 = 0
• 0 − 1 = 1( remind − 1)
• −1 − 1 = 0( remind − 1)
Let a = (1110)2 and b = (1011)2 . Find a − b
(1110)2 − (1011)2 = (11)2

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Multiplication

Find the product of a = (110)2 and b = (101)2

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Multiplication

Find the product of a = (110)2 and b = (101)2

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Multiplication

Find the product of a = (110)2 and b = (101)2

Thus, (110)2 .(101)2 = (11110)2

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Division

Find quotient and remainder (if exists) in the division of

(100010)2 by (110)2

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Division

Find quotient and remainder (if exists) in the division of

(100010)2 by (110)2

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Binary Operations: Division

Find quotient and remainder (if exists) in the division of

(100010)2 by (110)2

Thus, the quotient q = 101 and remainder r = 100

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Addition Algorithm

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Addition Algorithm

Example. Find (1110)2 + (1011)2

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Multiplication Algorithm

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Multiplication Algorithm

Example. Find the product of (110)2 and (101)2

Lai Văn Phút Chapter 4. Number Theory and Cryptography
The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Division Algorithm

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Division Algorithm

Example. Find the quotient and the remainder in the

division of 101 by 11

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Modular Exponentiation

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Modular Exponentiation

Example. Find 3644 mod 645

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Primes

Definition.
• A positive integer p greater than 1 is called prime (số
nguyên tố) if the only positive factors (ước số) are 1
and p.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Primes

Definition.
• A positive integer p greater than 1 is called prime (số
nguyên tố) if the only positive factors (ước số) are 1
and p.
• A positive integer that is greater than 1 and is not
prime is called composite (hợp số).

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Example.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The fundamental theorem of arithmetic (ĐL cơ

bản của số học)

Every positive integer greater than 1 can be written

uniquely as a prime or as the product of two or more
primes where the prime factors are written in order of
nondecreasing size.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The fundamental theorem of arithmetic (ĐL cơ

bản của số học)

Every positive integer greater than 1 can be written

uniquely as a prime or as the product of two or more
primes where the prime factors are written in order of
nondecreasing size.
Examples. Find the prime factorizations of 100, 999, and
1024.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Theorem

If n is a composite integer, then n has a

√prime divisor
(ước nguyên tố) less than or equal to n.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Theorem

If n is a composite integer, then n has a

√prime divisor
(ước nguyên tố) less than or equal to n.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Theorem

If n is a composite integer, then n has a

√prime divisor
(ước nguyên tố) less than or equal to n.
Examples.
1. Show that 101 is prime.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Theorem

If n is a composite integer, then n has a

√prime divisor
(ước nguyên tố) less than or equal to n.
Examples.
1. Show that 101 is prime.
2. Find the prime factorization of 7007.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Theorem

1. There are infinite many primes.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Theorem

1. There are infinite many primes.

2. (The prime number theorem)The ratio of π (x ), the
number of primes not exceeding x and x/lnx
approaches 1 and grows with bound ( lnx: natural
logarithm of x).

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Greatest Common Divisors

Definition. Let a, b be integers, not both zero. The largest
integer d such that d|a and d|b is called the greatest
common divisor (ước chung lớn nhất) of a and b.
Notation. gcd (a, b)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Greatest Common Divisors

Definition. Let a, b be integers, not both zero. The largest
integer d such that d|a and d|b is called the greatest
common divisor (ước chung lớn nhất) of a and b.
Notation. gcd (a, b)
To find gcd (a, b):

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Greatest Common Divisors

Definition. Let a, b be integers, not both zero. The largest
integer d such that d|a and d|b is called the greatest
common divisor (ước chung lớn nhất) of a and b.
Notation. gcd (a, b)
To find gcd (a, b):

Examples.
1. gcd (24, 36)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Greatest Common Divisors

Definition. Let a, b be integers, not both zero. The largest
integer d such that d|a and d|b is called the greatest
common divisor (ước chung lớn nhất) of a and b.
Notation. gcd (a, b)
To find gcd (a, b):

Examples.
1. gcd (24, 36)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Greatest Common Divisors

Definition. Let a, b be integers, not both zero. The largest
integer d such that d|a and d|b is called the greatest
common divisor (ước chung lớn nhất) of a and b.
Notation. gcd (a, b)
To find gcd (a, b):

Examples.
1. gcd (24, 36)→ gcd (24, 36) = 12
2. gcd (17, 22)
Lai Văn Phút Chapter 4. Number Theory and Cryptography
The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Greatest Common Divisors

Definition. Let a, b be integers, not both zero. The largest
integer d such that d|a and d|b is called the greatest
common divisor (ước chung lớn nhất) of a and b.
Notation. gcd (a, b)
To find gcd (a, b):

Examples.
1. gcd (24, 36)→ gcd (24, 36) = 12
2. gcd (17, 22)
Lai Văn Phút Chapter 4. Number Theory and Cryptography
The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Greatest Common Divisors

Definition. Let a, b be integers, not both zero. The largest
integer d such that d|a and d|b is called the greatest
common divisor (ước chung lớn nhất) of a and b.
Notation. gcd (a, b)
To find gcd (a, b):

Examples.
1. gcd (24, 36)→ gcd (24, 36) = 12
2. gcd (17, 22)→ gcd (17, 22) = 1
Lai Văn Phút Chapter 4. Number Theory and Cryptography
The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Definition.

• The integers a, b are relatively prime (nguyên tố cùng

nhau) if their greatest common divisor is 1

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Definition.

• The integers a, b are relatively prime (nguyên tố cùng

nhau) if their greatest common divisor is 1
• The integers a1 , a2 , a3 , . . . , an are pairwise relatively
prime (đôi 1 nguyên tố cùng nhau) if gcd (ai , aj ) = 1
whenever 1 ≤ i < j ≤ n

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Definition.

• The integers a, b are relatively prime (nguyên tố cùng

nhau) if their greatest common divisor is 1
• The integers a1 , a2 , a3 , . . . , an are pairwise relatively
prime (đôi 1 nguyên tố cùng nhau) if gcd (ai , aj ) = 1
whenever 1 ≤ i < j ≤ n

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Definition.

• The integers a, b are relatively prime (nguyên tố cùng

nhau) if their greatest common divisor is 1
• The integers a1 , a2 , a3 , . . . , an are pairwise relatively
prime (đôi 1 nguyên tố cùng nhau) if gcd (ai , aj ) = 1
whenever 1 ≤ i < j ≤ n
Examples. Show that
7, 10, 11, 17, 23 are pairwise relatively prime.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Definition.

• The integers a, b are relatively prime (nguyên tố cùng

nhau) if their greatest common divisor is 1
• The integers a1 , a2 , a3 , . . . , an are pairwise relatively
prime (đôi 1 nguyên tố cùng nhau) if gcd (ai , aj ) = 1
whenever 1 ≤ i < j ≤ n
Examples. Show that
7, 10, 11, 17, 23 are pairwise relatively prime.
17, 22 are relative prime.

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Least common multiple

Definition. The Least common multiple (bội chung nhỏ
nhất) of the positive integer a and b is the smallest integer
that is divisible by both a and b.
Notation. lcm(a, b)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Least common multiple

Definition. The Least common multiple (bội chung nhỏ
nhất) of the positive integer a and b is the smallest integer
that is divisible by both a and b.
Notation. lcm(a, b)
To find lcm(a, b):

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Least common multiple

Definition. The Least common multiple (bội chung nhỏ
nhất) of the positive integer a and b is the smallest integer
that is divisible by both a and b.
Notation. lcm(a, b)
To find lcm(a, b):

Examples.
1. lcm(12, 36)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Least common multiple

Definition. The Least common multiple (bội chung nhỏ
nhất) of the positive integer a and b is the smallest integer
that is divisible by both a and b.
Notation. lcm(a, b)
To find lcm(a, b):

Examples.
1. lcm(12, 36)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Least common multiple

Definition. The Least common multiple (bội chung nhỏ
nhất) of the positive integer a and b is the smallest integer
that is divisible by both a and b.
Notation. lcm(a, b)
To find lcm(a, b):

Examples.
1. lcm(12, 36)→ lcm(12, 36) = 36
2. lcm(7, 17)
Lai Văn Phút Chapter 4. Number Theory and Cryptography
The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Least common multiple

Definition. The Least common multiple (bội chung nhỏ
nhất) of the positive integer a and b is the smallest integer
that is divisible by both a and b.
Notation. lcm(a, b)
To find lcm(a, b):

Examples.
1. lcm(12, 36)→ lcm(12, 36) = 36
2. lcm(7, 17)
Lai Văn Phút Chapter 4. Number Theory and Cryptography
The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Least common multiple

Definition. The Least common multiple (bội chung nhỏ
nhất) of the positive integer a and b is the smallest integer
that is divisible by both a and b.
Notation. lcm(a, b)
To find lcm(a, b):

Examples.
1. lcm(12, 36)→ lcm(12, 36) = 36
2. lcm(7, 17)→ lcm(7, 17) = 119
Lai Văn Phút Chapter 4. Number Theory and Cryptography
The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Theorem

Let a, b be positive integers then

ab = gcd (a, b).lcm(a, b)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Theorem

Let a, b be positive integers then

ab = gcd (a, b).lcm(a, b)
Example. gcd(8, 12) = 4, lcm(8,12)=24 → 8.12 = 4.24

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Euclidean Algorithm

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Euclidean Algorithm

Example. Find gcd (24, 36)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Euler φ-function

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Euler φ-function

Example. Find φ(10) and φ(100)

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Quizz

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Quizz

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Integers and Division

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Integers and Division

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Integers and Division

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

The Integers and Division

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Primes and Greatest Common Divisors

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Primes and Greatest Common Divisors

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Integers and Algorithms

Lai Văn Phút Chapter 4. Number Theory and Cryptography

The Integers and Division Integers and Algorithms Primes and Greatest Common Divisors Problems

Integers and Algorithms

Lai Văn Phút Chapter 4. Number Theory and Cryptography