NUMBER
THEORY
Integer Representations and Algorithms
Representations of Integers
Integer Representations and Algorithms
Representations of Integers
Integer Representations and Algorithms
Representations of Integers
The successive remainders that we have found, 10, 14, 3, 11, 2, give us the digits from the right to the left of 177130 in the hexadecimal (base 16) expansion of (177130). It follows that
(177130) 10 = (2B3EA) 16.
Integer Representations and Algorithms
Representations of Integers
Integer Representations and Algorithms
Representations of Integers
Use Algorithm 5 to find 3644 mod 645.
Solution: Algorithm 5 initially sets x = 1 and power = 3 mod 645 = 3. In the computation of 3644 mod 645, this algorithm determines 32j mod 645 for j = 1, 2, … , 9 by successively squaring and reducing modulo 645. If aj = 1 (where aj is the bit in the jth position in the binary expansion of 644, which is (1010000100)2), it multiplies the current value of x by 32j mod 645 and reduces the result modulo 645. Here are the steps used:
This shows that following the steps of Algorithm 5 produces the result 3644 mod 645 = 36.
Algorithm 5 is quite efficient; it uses O((log m) 2 log n) bit operations to find bn mod m
Thanks
Divisibility and Modular Arithmetic
Division
When one integer is divided by a second nonzero integer, the quotient may or may not be an integer. For example, 12 ∕ 3 = 4 is an integer, whereas 11∕4 = 2.75 is not. This leads to 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 (or equivalently, if b/a is an integer). 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 divide b.
Remark: We can express a ∣ b using quantifiers as ∃c(ac = b), where the universe of discourse is the set of integers. In Figure 1 a number line indicates which integers are divisible by the positive integer d
THEOREM 1
COROLLARY 1
Modular Arithmetic
The set of all integers congruent to an integer a modulo m is called the congruence class of a modulo m. In Chapter 9 we will show that there are m pairwise disjoint equivalence classes modulo m and that the union of these equivalence classes is the set of integers. Theorem 5 shows that additions and multiplications preserve congruences.
The Division Algorithm
When an integer is divided by a positive integer, there is a quotient and a remainder, as the division algorithm shows.
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.
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. This notation is used to express the quotient and remainder: q = a div d, r = a mod d.
Remark: Note that both a div d and a mod d for a fixed d are functions on the set of integers. Furthermore, when a is an integer and d is a positive integer, we have a div d = ⌊a∕d⌋ and a mod d = a − d.
What are the quotient and remainder when −11 is divided by 3?
Modular Arithmetic
Arithmetic Modulo m
Arithmetic Modulo m
Integer Representations and Algorithms
Representations of Integers
Integer Representations and Algorithms
Representations of Integers
Integer Representations and Algorithms
Representations of Integers
The successive remainders that we have found, 10, 14, 3, 11, 2, give us the digits from the right to the left of 177130 in the hexadecimal (base 16) expansion of (177130). It follows that
(177130) 10 = (2B3EA) 16.
Integer Representations and Algorithms
Representations of Integers
Integer Representations and Algorithms
Representations of Integers
Use Algorithm 5 to find 3644 mod 645.
Solution: Algorithm 5 initially sets x = 1 and power = 3 mod 645 = 3. In the computation of 3644 mod 645, this algorithm determines 32j mod 645 for j = 1, 2, … , 9 by successively squaring and reducing modulo 645. If aj = 1 (where aj is the bit in the jth position in the binary expansion of 644, which is (1010000100)2), it multiplies the current value of x by 32j mod 645 and reduces the result modulo 645. Here are the steps used:
This shows that following the steps of Algorithm 5 produces the result 3644 mod 645 = 36.
Algorithm 5 is quite efficient; it uses O((log m) 2 log n) bit operations to find bn mod m
Primes and Greatest Common Divisors
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.
Remark: The integer n is composite if and only if there exists an integer a such that a | n and 1 <a<n.
The integer 7 is prime because its only positive factors are 1 and 7, whereas the integer 9 is composite because it is divisible by 3.
The primes are the building blocks of positive integers, as the fundamental theorem of arithmetic shows.
THE FUNDAMENTAL THEOREM OF 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.
Primes and Greatest Common Divisors
Trial Division
If n is a composite integer, then n has a prime divisor less than or equal to √n.
Show that 101 is prime.
Solution: The only primes not exceeding √101 are 2, 3, 5, and 7. Because 101 is not divisible by 2, 3, 5, or 7 (the quotient of 101 and each of these integers is not an integer), it follows that 101 is prime.
Greatest Common Divisor
Definition: Let a and b be integers, not both zero. The largest integer d such that d | a and also 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).
One can find greatest common divisors of small numbers by inspection.
Example: What is the greatest common divisor of 24 and 36?
Solution: gcd(24,36) = 12
Example: What is the greatest common divisor of 17 and 22?
Solution: gcd(17,22) = 1
Greatest Common Divisor
Definition: The integers a and b are relatively prime if their greatest common divisor is 1.
Example: 17 and 22
Definition: The integers a1, a2, …, an are pairwise relatively prime if gcd(ai, aj)= 1 whenever 1 ≤ i<j ≤n.
Example: Determine whether the integers 10, 17 and 21 are pairwise relatively prime.
Solution: Because gcd(10,17) = 1, gcd(10,21) = 1, and gcd(17,21) = 1, 10, 17, and 21 are pairwise relatively prime.
Example: Determine whether the integers 10, 19, and 24 are pairwise relatively prime.
Solution: Because gcd(10,24) = 2, 10, 19, and 24 are not pairwise relatively prime.
Least Common Multiple
Definition: The least common multiple of the positive integers a and b is the smallest positive integer that is divisible by both a and b. It is denoted by lcm(a,b).
The least common multiple can also be computed from the prime factorizations.
This number is divided by both a and b and no smaller number is divided by a and b.
Example: lcm(233572, 2433) = 2max(3,4) 3max(5,3) 7max(2,0) = 24 35 72
The greatest common divisor and the least common multiple of two integers are related by:
Theorem 5: Let a and b be positive integers. Then
ab = gcd(a,b) ∙lcm(a,b)
Greatest Common Divisor
Suppose the prime factorizations of a and b are:
where each exponent is a nonnegative integer, and where all primes occurring in either prime factorization are included in both. Then:
This formula is valid since the integer on the right (of the equals sign) divides both a and b. No larger integer can divide both a and b.
Example: 120 = 23 ∙3 ∙5 500 = 22 ∙53
gcd(120,500) = 2min(3,2) ∙3min(1,0) ∙5min(1,3) = 22 ∙30 ∙51 = 20
Finding the gcd of two positive integers using their prime factorizations is not efficient because there is no efficient algorithm for finding the prime factorization of a positive integer.
Computing the greatest common divisor of two integers directly from the prime factorizations of these integers is inefficient. The reason is that it is time-consuming to find prime factorizations. We will give a more efficient method of finding the greatest common divisor, called the Euclidean algorithm. This algorithm has been known since ancient times. It is named after the ancient Greek mathematician Euclid, who included a description of this algorithm in his book The Elements.
gcd(91, 287)
Find the greatest common divisor of 414 and 662 using the Euclidean algorithm.
gcds as Linear Combinations
An important result we will use throughout the remainder of this section is that the greatest common divisor of two integers a and b can be expressed in the form
sa + tb,
where s and t are integers. In other words, gcd(a, b) can be expressed as a linear combination with integer coefficients of a and b. For example, gcd(6, 14) = 2, and 2 = (−2) · 6 + 1 · 14.
BÉZOUT’S THEOREM If a and b are positive integers, then there exist integers s and t such that gcd(a, b) = sa + tb.
If a and b are positive integers, then integers s and t such that gcd(a, b) = sa + tb are called Bézout coefficients of a and b (after Étienne Bézout, a French mathematician of the eighteenth century). Also, the equation gcd(a, b) = sa + tb is called Bézout’s identity.
Thanks
THEOREM 1
COROLLARY 1
-...+...
Modular Arithmetic
The set of all integers congruent to an integer a modulo m is called the congruence class of a modulo m. In Chapter 9 we will show that there are m pairwise disjoint equivalence classes modulo m and that the union of these equivalence classes is the set of integers. Theorem 5 shows that additions and multiplications preserve congruences.
The Division Algorithm
When an integer is divided by a positive integer, there is a quotient and a remainder, as the division algorithm shows.
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.
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. This notation is used to express the quotient and remainder: q = a div d, r = a mod d.
Remark: Note that both a div d and a mod d for a fixed d are functions on the set of integers. Furthermore, when a is an integer and d is a positive integer, we have a div d = ⌊a∕d⌋ and a mod d = a − d.
What are the quotient and remainder when −11 is divided by 3?
Modular Arithmetic
Arithmetic Modulo m
Arithmetic Modulo m
Integer Representations and Algorithms
Representations of Integers
Integer Representations and Algorithms
Representations of Integers
Integer Representations and Algorithms
Representations of Integers
The successive remainders that we have found, 10, 14, 3, 11, 2, give us the digits from the right to the left of 177130 in the hexadecimal (base 16) expansion of (177130). It follows that
(177130) 10 = (2B3EA) 16.
Integer Representations and Algorithms
Representations of Integers
Integer Representations and Algorithms
Representations of Integers
Use Algorithm 5 to find 3644 mod 645.
Solution: Algorithm 5 initially sets x = 1 and power = 3 mod 645 = 3. In the computation of 3644 mod 645, this algorithm determines 32j mod 645 for j = 1, 2, … , 9 by successively squaring and reducing modulo 645. If aj = 1 (where aj is the bit in the jth position in the binary expansion of 644, which is (1010000100)2), it multiplies the current value of x by 32j mod 645 and reduces the result modulo 645. Here are the steps used:
This shows that following the steps of Algorithm 5 produces the result 3644 mod 645 = 36.
Algorithm 5 is quite efficient; it uses O((log m) 2 log n) bit operations to find bn mod m
Primes and Greatest Common Divisors
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.
Remark: The integer n is composite if and only if there exists an integer a such that a | n and 1 <a<n.
The integer 7 is prime because its only positive factors are 1 and 7, whereas the integer 9 is composite because it is divisible by 3.
The primes are the building blocks of positive integers, as the fundamental theorem of arithmetic shows.
THE FUNDAMENTAL THEOREM OF 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.
Primes and Greatest Common Divisors
Trial Division
If n is a composite integer, then n has a prime divisor less than or equal to √n.
Show that 101 is prime.
Solution: The only primes not exceeding √101 are 2, 3, 5, and 7. Because 101 is not divisible by 2, 3, 5, or 7 (the quotient of 101 and each of these integers is not an integer), it follows that 101 is prime.
Greatest Common Divisor
Definition: Let a and b be integers, not both zero. The largest integer d such that d | a and also 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).
One can find greatest common divisors of small numbers by inspection.
Example: What is the greatest common divisor of 24 and 36?
Solution: gcd(24,36) = 12
Example: What is the greatest common divisor of 17 and 22?
Solution: gcd(17,22) = 1
Greatest Common Divisor
Definition: The integers a and b are relatively prime if their greatest common divisor is 1.
Example: 17 and 22
Definition: The integers a1, a2, …, an are pairwise relatively prime if gcd(ai, aj)= 1 whenever 1 ≤ i<j ≤n.
Example: Determine whether the integers 10, 17 and 21 are pairwise relatively prime.
Solution: Because gcd(10,17) = 1, gcd(10,21) = 1, and gcd(17,21) = 1, 10, 17, and 21 are pairwise relatively prime.
Example: Determine whether the integers 10, 19, and 24 are pairwise relatively prime.
Solution: Because gcd(10,24) = 2, 10, 19, and 24 are not pairwise relatively prime.
Least Common Multiple
Definition: The least common multiple of the positive integers a and b is the smallest positive integer that is divisible by both a and b. It is denoted by lcm(a,b).
The least common multiple can also be computed from the prime factorizations.
This number is divided by both a and b and no smaller number is divided by a and b.
Example: lcm(233572, 2433) = 2max(3,4) 3max(5,3) 7max(2,0) = 24 35 72
The greatest common divisor and the least common multiple of two integers are related by:
Theorem 5: Let a and b be positive integers. Then
ab = gcd(a,b) ∙lcm(a,b)
Greatest Common Divisor
Suppose the prime factorizations of a and b are:
where each exponent is a nonnegative integer, and where all primes occurring in either prime factorization are included in both. Then:
This formula is valid since the integer on the right (of the equals sign) divides both a and b. No larger integer can divide both a and b.
Example: 120 = 23 ∙3 ∙5 500 = 22 ∙53
gcd(120,500) = 2min(3,2) ∙3min(1,0) ∙5min(1,3) = 22 ∙30 ∙51 = 20
Finding the gcd of two positive integers using their prime factorizations is not efficient because there is no efficient algorithm for finding the prime factorization of a positive integer.
Computing the greatest common divisor of two integers directly from the prime factorizations of these integers is inefficient. The reason is that it is time-consuming to find prime factorizations. We will give a more efficient method of finding the greatest common divisor, called the Euclidean algorithm. This algorithm has been known since ancient times. It is named after the ancient Greek mathematician Euclid, who included a description of this algorithm in his book The Elements.
gcd(91, 287)
Find the greatest common divisor of 414 and 662 using the Euclidean algorithm.
gcds as Linear Combinations
An important result we will use throughout the remainder of this section is that the greatest common divisor of two integers a and b can be expressed in the form
sa + tb,
where s and t are integers. In other words, gcd(a, b) can be expressed as a linear combination with integer coefficients of a and b. For example, gcd(6, 14) = 2, and 2 = (−2) · 6 + 1 · 14.
BÉZOUT’S THEOREM If a and b are positive integers, then there exist integers s and t such that gcd(a, b) = sa + tb.
If a and b are positive integers, then integers s and t such that gcd(a, b) = sa + tb are called Bézout coefficients of a and b (after Étienne Bézout, a French mathematician of the eighteenth century). Also, the equation gcd(a, b) = sa + tb is called Bézout’s identity.
gcds as Linear Combinations
Express gcd(252, 198) = 18 as a linear combination of 252 and 198.
Thanks
Divisibility and Modular Arithmetic
Division
When one integer is divided by a second nonzero integer, the quotient may or may not be an integer. For example, 12 ∕ 3 = 4 is an integer, whereas 11∕4 = 2.75 is not. This leads to 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 (or equivalently, if b/a is an integer). 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 divide b.
Remark: We can express a ∣ b using quantifiers as ∃c(ac = b), where the universe of discourse is the set of integers. In Figure 1 a number line indicates which integers are divisible by the positive integer d
THEOREM 1
COROLLARY 1
Modular Arithmetic
The set of all integers congruent to an integer a modulo m is called the congruence class of a modulo m. In Chapter 9 we will show that there are m pairwise disjoint equivalence classes modulo m and that the union of these equivalence classes is the set of integers. Theorem 5 shows that additions and multiplications preserve congruences.
The Division Algorithm
When an integer is divided by a positive integer, there is a quotient and a remainder, as the division algorithm shows.
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.
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. This notation is used to express the quotient and remainder: q = a div d, r = a mod d.
Remark: Note that both a div d and a mod d for a fixed d are functions on the set of integers. Furthermore, when a is an integer and d is a positive integer, we have a div d = ⌊a∕d⌋ and a mod d = a − d.
What are the quotient and remainder when −11 is divided by 3?
Modular Arithmetic
Arithmetic Modulo m
Arithmetic Modulo m
Integer Representations and Algorithms
Representations of Integers
Integer Representations and Algorithms
Representations of Integers
Integer Representations and Algorithms
Representations of Integers
The successive remainders that we have found, 10, 14, 3, 11, 2, give us the digits from the right to the left of 177130 in the hexadecimal (base 16) expansion of (177130). It follows that
(177130) 10 = (2B3EA) 16.
Integer Representations and Algorithms
Representations of Integers
Integer Representations and Algorithms
Representations of Integers
Use Algorithm 5 to find 3644 mod 645.
Solution: Algorithm 5 initially sets x = 1 and power = 3 mod 645 = 3. In the computation of 3644 mod 645, this algorithm determines 32j mod 645 for j = 1, 2, … , 9 by successively squaring and reducing modulo 645. If aj = 1 (where aj is the bit in the jth position in the binary expansion of 644, which is (1010000100)2), it multiplies the current value of x by 32j mod 645 and reduces the result modulo 645. Here are the steps used:
This shows that following the steps of Algorithm 5 produces the result 3644 mod 645 = 36.
Algorithm 5 is quite efficient; it uses O((log m) 2 log n) bit operations to find bn mod m
Primes and Greatest Common Divisors
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.
Remark: The integer n is composite if and only if there exists an integer a such that a | n and 1 <a<n.
The integer 7 is prime because its only positive factors are 1 and 7, whereas the integer 9 is composite because it is divisible by 3.
The primes are the building blocks of positive integers, as the fundamental theorem of arithmetic shows.
THE FUNDAMENTAL THEOREM OF 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.
Primes and Greatest Common Divisors
Trial Division
If n is a composite integer, then n has a prime divisor less than or equal to √n.
Show that 101 is prime.
Solution: The only primes not exceeding √101 are 2, 3, 5, and 7. Because 101 is not divisible by 2, 3, 5, or 7 (the quotient of 101 and each of these integers is not an integer), it follows that 101 is prime.
Greatest Common Divisor
Definition: Let a and b be integers, not both zero. The largest integer d such that d | a and also 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).
One can find greatest common divisors of small numbers by inspection.
Example: What is the greatest common divisor of 24 and 36?
Solution: gcd(24,36) = 12
Example: What is the greatest common divisor of 17 and 22?
Solution: gcd(17,22) = 1
Greatest Common Divisor
Definition: The integers a and b are relatively prime if their greatest common divisor is 1.
Example: 17 and 22
Definition: The integers a1, a2, …, an are pairwise relatively prime if gcd(ai, aj)= 1 whenever 1 ≤ i<j ≤n.
Example: Determine whether the integers 10, 17 and 21 are pairwise relatively prime.
Solution: Because gcd(10,17) = 1, gcd(10,21) = 1, and gcd(17,21) = 1, 10, 17, and 21 are pairwise relatively prime.
Example: Determine whether the integers 10, 19, and 24 are pairwise relatively prime.
Solution: Because gcd(10,24) = 2, 10, 19, and 24 are not pairwise relatively prime.
Least Common Multiple
Definition: The least common multiple of the positive integers a and b is the smallest positive integer that is divisible by both a and b. It is denoted by lcm(a,b).
The least common multiple can also be computed from the prime factorizations.
This number is divided by both a and b and no smaller number is divided by a and b.
Example: lcm(233572, 2433) = 2max(3,4) 3max(5,3) 7max(2,0) = 24 35 72
The greatest common divisor and the least common multiple of two integers are related by:
Theorem 5: Let a and b be positive integers. Then
ab = gcd(a,b) ∙lcm(a,b)
Greatest Common Divisor
Suppose the prime factorizations of a and b are:
where each exponent is a nonnegative integer, and where all primes occurring in either prime factorization are included in both. Then:
This formula is valid since the integer on the right (of the equals sign) divides both a and b. No larger integer can divide both a and b.
Example: 120 = 23 ∙3 ∙5 500 = 22 ∙53
gcd(120,500) = 2min(3,2) ∙3min(1,0) ∙5min(1,3) = 22 ∙30 ∙51 = 20
Finding the gcd of two positive integers using their prime factorizations is not efficient because there is no efficient algorithm for finding the prime factorization of a positive integer.
Computing the greatest common divisor of two integers directly from the prime factorizations of these integers is inefficient. The reason is that it is time-consuming to find prime factorizations. We will give a more efficient method of finding the greatest common divisor, called the Euclidean algorithm. This algorithm has been known since ancient times. It is named after the ancient Greek mathematician Euclid, who included a description of this algorithm in his book The Elements.
gcd(91, 287)
Find the greatest common divisor of 414 and 662 using the Euclidean algorithm.
gcds as Linear Combinations
An important result we will use throughout the remainder of this section is that the greatest common divisor of two integers a and b can be expressed in the form
sa + tb,
where s and t are integers. In other words, gcd(a, b) can be expressed as a linear combination with integer coefficients of a and b. For example, gcd(6, 14) = 2, and 2 = (−2) · 6 + 1 · 14.
BÉZOUT’S THEOREM If a and b are positive integers, then there exist integers s and t such that gcd(a, b) = sa + tb.
If a and b are positive integers, then integers s and t such that gcd(a, b) = sa + tb are called Bézout coefficients of a and b (after Étienne Bézout, a French mathematician of the eighteenth century). Also, the equation gcd(a, b) = sa + tb is called Bézout’s identity.
gcds as Linear Combinations
Express gcd(252, 198) = 18 as a linear combination of 252 and 198.
Thanks