CS代写 CSI 2101: Discrete Structures

Number Theory (Part A)
CSI 2101: Discrete Structures
School of Electrical Engineering and Computer Science, University of Ottawa
February 02, 2022

Md. Hasan (uOttawa) Discrete Structures 4a MdH W22 February 02, 2022 1 / 14

1 Divisibility
2 Modular Arithmetic
Md. Hasan (uOttawa) Discrete Structures 4a MdH W22 February 02, 2022 2 / 14

Introduction
􏰀 Number theory is the part of mathematics devoted to the study of the integers and their properties.
􏰀 The scope of number theory includes a wide range of applications in computing and cryptography.
􏰀 The study of number theory is necessary to understand the cryptographic mechanisms used in electronic security.
􏰀 In particular, we are emphasizing on divisibility, modular arithmetic, and the properties of prime numbers.
Md. Hasan (uOttawa) Discrete Structures 4a MdH W22 February 02, 2022 3 / 14

􏰀 Definition
If a and b are integers with a ̸= 0, we say that a divides b if there is an integer c such that b = ac. When a divides b we say that a is a factor or divisor of b, and that b is a multiple of a. The notation a | b denotes that a divides b. We write a 􏰅 b when a does not divides b.
􏰀 Example 7 | 56
Md. Hasan (uOttawa) Discrete Structures 4a MdH W22 February 02, 2022 4 / 14

Division Algorithm
􏰀 Theorem: The Division Algorithm
Let a be an integer and d a positive integer. Then there are unique
integers q and r, with 0 ≤ r < d, such that a = dq + r. 􏰀 Definition In the equality given in the division algorithm, d is called the divisor, a is called the dividend, q is called the quotient, and r is called the remainder. q = a div d and r = a mod d. Md. Hasan (uOttawa) Discrete Structures 4a MdH W22 February 02, 2022 6 / 14 Modular Arithmetic 􏰀 Definition If a and b are integers and m is a positive integer, then a is congruent to b modulo m if m divides a − b. The notation a ≡ b(mod m) is used to indicate that a is congruent to b modulo m. We say that a ≡ b (mod m) is a congruence and that m is its modulus (plural moduli). If a and b are not congruent modulo m, we write a ̸≡ b (mod m). Let a and b be integers, and let m be a positive integer. Then a ≡ b (mod m) if and only if a mod m = b mod m. Md. Hasan (uOttawa) Discrete Structures 4a MdH W22 February 02, 2022 7 / 14 Modular Arithmetic (cont.) Let m be a positive integer. The integers a and b are congruent modulo m ifandonlyifthereisanintegerk suchthata=b+km. Let m be 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 m be a positive integer and let a and b be integers. Then (a + b) mod m = ((a mod m) + (b mod m)) mod m (ab) mod m = ((a mod m)(b mod m)) mod m Md. Hasan (uOttawa) Discrete Structures 4a MdH W22 February 02, 2022 8 / 14 Arithmetic Modulo m 􏰀 We can define arithmetic operations on Zm, the set of nonnegative integers less than m. that is, the set 0, 1, ..., m − 1. In particular, we define addition of these integers, denoted by +m by a +m b = (a + b) mod m, where the addition on the right-hand side of this equation is the ordinary addition of integers, and we define multiplication of these integers, denoted by ·m by a ·m b = (a · b) mod m, where the multiplication on the right-hand side of this equation is the ordinary multiplication of integers. Md. Hasan (uOttawa) Discrete Structures 4a MdH W22 February 02, 2022 9 / 14 Arithmetic Modulo m Properties If a and b belong to Zm, then a +m b and a ·m b belong to Zm. 􏰀 Associativity If a, b, and c belong to Zm, then (a +m b) +m c = a +m (b +m c) and (a·m b)·m c =a·m (b·m c). 􏰀 Commutativity If a, b, and c belong to Zm, then a +m b = b +m a and a ·m b = b ·m a. 􏰀 Identity Elements The elements 0 and 1 are identity elements for addition and multiplication modulo m, respectively. That is, if a belongs to Zm, then a +m 0 = 0 +m a = a and a ·m 1 = 1 ·m a = a. Md. Hasan (uOttawa) Discrete Structures 4a MdH W22 February 02, 2022 10 / 14 Arithmetic Modulo m Properties (cont.) 􏰀 Additive Inverses If a ̸= 0 belongs to Zm, then m − a is an additive inverse of a modulo m and 0 is its own additive inverse. That is, a +m (m − a) = 0 and 0 +m 0. 􏰀 Distributivity If a, b, and c belong to Zm, then a ·m (b +m c) = (a ·m b) +m (a ·m c) and (a+m b)·m c =(a·m c)+m (b·m c). Md. Hasan (uOttawa) Discrete Structures 4a MdH W22 February 02, 2022 11 / 14 􏰀 Definition An integer p greater than 1 is called prime if the only positive factors of p are 1 and p. A positive integer that is greater than 1 and is not prime is called composite. 13 is a prime since its only positive factors are 1 and 13 􏰀 Theorem: Fundamental Arithmetic Every 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. 􏰀 Example 21 = 3 · 7 100 = 2·2·5·5 = 22 ·52 Md. Hasan (uOttawa) Discrete Structures 4a MdH W22 February 02, 2022 12 / 14 Primes (cont.) 􏰀 Theorem: Trial Division If n is a composite integer, then n has a prime divisor less than or equal to By the definition of a composite integer, n has a factor a with 1 < a < n. By the definition of a factor of a positive integer, we have n = ab, where b>1. Firstly,wewillshowthata≤√norb≤√n. √√
Ifa> nandb> n,thenab>n,whichisacontradiction. Consequently, a ≤ √n or b ≤ √n. Thus, n has a positive divisor not
n. That divisor can be a prime or it can have a prime divisor
less than itself (based on the fundamental theorem of arithmetic). In
either case, n has a prime divisor less than or equal to
Md. Hasan (uOttawa) Discrete Structures 4a MdH W22
February 02, 2022 13 / 14

Thank You!
Questions and Comments?
Md. Hasan (uOttawa) Discrete Structures 4a MdH W22 February 02, 2022 14 / 14

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts