Number Theory (Part B)
CSI 2101: Discrete Structures
School of Electrical Engineering and Computer Science, University of Ottawa
February 03, 2022
Copyright By PowCoder代写 加微信 powcoder
Md. Hasan (uOttawa) Discrete Structures 4b MdH W22 February 03, 2022 1 / 16
1 Properties of Primes
2 Greatest Common Divisors
3 Linear Congruences
Md. Hasan (uOttawa) Discrete Structures 4b MdH W22 February 03, 2022 2 / 16
Trial Division and The Sieve of Eratosthenes
If n is a composite integer, then n has a prime divisor less than or equal √
An integer is prime if it is not divisible by any prime less than or equal to its square root. This leads to the brute-force algorithm known as trial division.
The sieve of Erastosthenes is used to find all primes not exceeding a specified positive integer. It starts with a list of integers. The sieving process continues for all primes ≤ √n where n is a given positive integer.
Md. Hasan (uOttawa) Discrete Structures 4b MdH W22 February 03, 2022 3 / 16
The Infinitude of Primes There are infinitely many primes.
The Prime Number Theorem
The ratio of π(x), the number of primes not exceeding x, and x/ln(x)
approaches 1 as x grows without bound. Mersene Primes
Prime numbers of the form 2p − 1, where p is prime, are called Mersene primes.
Md. Hasan (uOttawa) Discrete Structures 4b MdH W22 February 03, 2022 4 / 16
Conjectures About Primes
Goldbach’s Conjecture
Every even integer n, n > 2, is the sum of two primes.
Primes of the form n2 + 1
There are infinitely many primes of the form n2 + 1, where n is a positive integer. It has been shown that there are infinitely many primes of the form n2 + 1, where n is a positive integer or the product of at most two primes.
The Twin Prime Conjecture
The twin prime conjecture asserts that there are infinitely many pairs of
twin primes. Twin primes are pairs of primes that differ by 2.
Md. Hasan (uOttawa) Discrete Structures 4b MdH W22 February 03, 2022 5 / 16
Greatest Common Divisors
Definition
Let a and b be integers, not both zero. The largest integer d such that d | a and d | b is called the greatest common divisor of a and b. the greatest common divisor of a and b is denoted by gcd(a, b).
• gcd(27, 45) = 9 • gcd(11, 17) = 1
Relatively Prime
The integers a and b are relatively prime if their greatest common divisor
Md. Hasan (uOttawa) Discrete Structures 4b MdH W22 February 03, 2022 6 / 16
Greatest Common Divisors (cont.)
Pairwise Relatively Prime
The integers a,a,…,an are pairwise relatively prime if gcd(ai,aj) = 1
whenever 1 ≤ i < j ≤ n.
– The integers 10, 17, and 21 are pairwise relatively prime.
– The integers 10, 19, and 24 are not pairwise relatively prime.
Prime Factorization and GCD a = pa pa ...pan
b = pb pb ...pbn n
gcd(a,b) = pmin(a,b)pmin(a,b)...pmin(an,bn) n
Md. Hasan (uOttawa) Discrete Structures 4b MdH W22 February 03, 2022 7 / 16
Greatest Common Divisors (cont.)
Least Common Multiple
The least common multiple of the positive integers a and b is the smallest positive integer that is divisible by both a and b. The least common multiple of a and b is denoted by lcm(a, b).
lcm(a, b) = pmax(a,b)pmax(a,b)...pmax(an,bn) n
Let a and b be positive integers. Then ab =gcd(a, b)·lcm(a, b).
Md. Hasan (uOttawa) Discrete Structures 4b MdH W22 February 03, 2022 8 / 16
The Euclidean Algorithm
The prime factorization can be a computationally inefficient method of finding the GCDs. It takes time to factorize primes.
The Euclidean algorithm is a more efficient method of finding the GCDs. =bq+r,wherea,b,q,andr areintegers. Then gcd(a, b)=gcd(b, r ).
If an integer d divides both a and b, then it also divides a − bq = r . Thus,
any common divisor of a and b is also a common divisor of b and r.
Likewise, if an integer d divides both b and r, then it also divides bq + r = a. Thus, any common divisor of b and r is also a common divisor of a and b.
Consequently, gcd(a,b)=gcd(b,r).
Md. Hasan (uOttawa) Discrete Structures 4b MdH W22 February 03, 2022 9 / 16
The Euclidean Algorithm (cont.)
The Euclidean Algorithm (a ≥ b)
procedure gcd (a, b : positive integers) x := a
while y ̸= 0
r := x mod y x := y
return x{gcd(a,b) is x}
Md. Hasan (uOttawa)
Discrete Structures 4b MdH W22
February 03, 2022
GCDs as Linear Combinations
Bezout’s Theorem/Identity
If a and b are positive integers, then there exist integers s and t such that
gcd(a, b) = sa + tb.
Here, s and t are called Bezout’s coefficients of a and b.
Express gcd(252, 198) = 18 as a linear combination of 252 and 198.
Md. Hasan (uOttawa) Discrete Structures 4b MdH W22 February 03, 2022 11 / 16
GCDs as Linear Combinations (cont.)
Method 1: Backward Euclidean
Suppose that a and b are positive integers with a ≥ b. Let r0 = a and
r0 = r1q1 + r2 0 ≤ r2 < r1, r1 = r2q2 + r3 0 ≤ r3 < r2, .
rn−2 =rn−1qn−1 +rn rn−1 = rnqn.
0≤rn