4.1 Briefly define a group. Get 4.1 exercise solution
4.2 Briefly define a ring. Get 4.2 exercise solution
4.3 Briefly define a field. Get 4.3 exercise solution
4.4 What does it mean to say that b is a divisor of a? Get 4.4 exercise solution
4.5 What is the difference between modular arithmetic and ordinary arithmetic? Get 4.5 exercise solution
4.6 List three classes of polynomial arithmetic. Get 4.6 exercise solution
Problems
4.1 For the group Sn of all permutations of n distinct symbols, a. what is the number of elements in Sn? b. show that Sn is not abelian for n 7 2. Get 4.1 exercise solution
4.2 Does the set of residue classes (mod3) form a group a. with respect to modular addition? b. with respect to modular multiplication? Get 4.2 exercise solution
4.3 Consider the set S = {a, b} with addition and multiplication defined by the following tables.
Is S a ring? Justify your answer. Get 4.3 exercise solution
4.4 Reformulate Equation (4.1), removing the restriction that a is a nonnegative integer. That is, let a be any integer. Get 4.4 exercise solution
4.5 Draw a figure similar to Figure 4.1 for a 6 0. Get 4.5 exercise solution
4.6 For each of the following equations, find an integer x that satisfies the equation. a. 5x K 4 (mod 3) b. 7x K 6 (mod 5) c. 9x K 8 (mod 7) Get 4.6 exercise solution
4.7 In this text, we assume that the modulus is a positive integer. But the definition of the expression a mod n also makes perfect sense if n is negative. Determine the following: a. 5 mod 3 b. 5 mod -3 c. -5 mod 3 d. -5 mod -3 Get 4.7 exercise solution
4.8 A modulus of 0 does not fit the definition but is defined by convention as follows: a mod 0 = a. With this definition in mind, what does the following expression mean: a K b (mod 0)? Get 4.8 exercise solution
4.9 In Section 4.3, we define the congruence relationship as follows: Two integers a and b are said to be congruent modulo n if (a mod n) = (b mod n). We then proved that a K b (mod n) if n | (a - b). Some texts on number theory use this latter relationship as the definition of congruence: Two integers a and b are said to be congruent modulo n if n | (a - b). Using this latter definition as the starting point, prove that, if (a mod n) = (b mod n), then n divides (a - b). Get 4.9 exercise solution
4.10 What is the smallest positive integer that has exactly k divisors, for 1 <= k <= 6? Get 4.10 exercise solution
4.11 Prove the following: a. a K b (mod n) implies b K a (mod n) b. a K b (mod n) and b K c (mod n) imply a K c (mod n) Get 4.11 exercise solution
4.12 Prove the following: a. [(a mod n) - (b mod n)] mod n = (a - b) mod n b. [(a mod n) * (b mod n)] mod n = (a * b) mod n Get 4.12 exercise solution
4.13 Find the multiplicative inverse of each nonzero element in Z5. Get 4.13 exercise solution
4.14 Show that an integer N is congruent modulo 9 to the sum of its decimal digits. For example, 475 K 4 + 7 + 5 K 16 K 1 + 6 K 7 (mod 9). This is the basis for the familiar procedure of “casting out 9’s” when checking computations in arithmetic. Get 4.14 exercise solution
4.15 a. Determine gcd(24140, 16762). b. Determine gcd(4655, 12075). Get 4.15 exercise solution
4.16 The purpose of this problem is to set an upper bound on the number of iterations of the Euclidean algorithm. a. Suppose that m = qn + r with q > 0 and 0<=r <= n. Show that m/2 > r. b. Let Ai be the value of A in the Euclidean algorithm after the ith iteration. Show that
c. Show that if m, n, and N are integers with (1 … m, n, … 2N), then the Euclidean algorithm takes at most 2N steps to find gcd(m, n). Get 4.16 exercise solution
4.17 The Euclidean algorithm has been known for over 2000 years and has always been a favorite among number theorists. After these many years, there is now a potential competitor, invented by J. Stein in 1961. Stein’s algorithms is as follows. Determine gcd(A, B) with A, B Ú 1. STEP 1 Set A1 = A, B1 = B, C1 = 1
STEP 2 n
(1) If An = Bn stop. gcd(A, B) = AnCn
(2) If An and Bn are both even, set An+1 = An/2, Bn+1 = Bn/2, Cn+1 = 2Cn
(3) If An is even and Bn is odd, set An+1 = An/2, Bn+1 = Bn, Cn+1 = Cn
(4) If An is odd and Bn is even, set An+1 = An, Bn+1 = Bn/2, Cn+1 = Cn
(5) If An and Bn are both odd, set An+1 = | An - Bn |, Bn+1 = min (Bn, An), Cn+1 = Cn
Continue to step n + 1.
a. To get a feel for the two algorithms, compute gcd(2152, 764) using both the Euclidean and Stein’s algorithm. b. What is the apparent advantage of Stein’s algorithm over the Euclidean algorithm?
Get 4.17 exercise solution
4 .18 a. Show that if Stein’s algorithm does not stop before the nth step, then Cn+1 * gcd(An+1, Bn+1) = Cn * gcd(An, Bn) b. Show that if the algorithm does not stop before step (n - 1), then
c. Show that if 1 … A, B … 2N, then Stein’s algorithm takes at most 4N steps to find gcd(m, n). Thus, Stein’s algorithm works in roughly the same number of steps as the Euclidean algorithm. d. Demonstrate that Stein’s algorithm does indeed return gcd(A, B).
Get 4.18 exercise solution
4.19 Using the extended Euclidean algorithm, find the multiplicative inverse of
a.1234 mod 4321
b.24140 mod 40902
c.550 mod 1769 Get 4.19 exercise solution
4.20 Develop a set of tables similar to Table 4.5 for GF(5). Get 4.20 exercise solution
4.21 Demonstrate that the set of polynomials whose coefficients form a field is a ring. Get 4.21 exercise solution
4.22 Demonstrate whether each of these statements is true or false for polynomials over a fiel
d.
a.The product of monic polynomials is moni
c.
b.The product of polynomials of degrees m and n has degree m + n.
c.The sum of polynomials of degrees m and n has degree max [m, n]. Get 4.22 exercise solution
4.23 For polynomial arithmetic with coefficients in Z10, perform the following calculations.
a.(7x + 2) - (x2 + 5)
b.(6x2 + x + 3) * (5x2 + 2) Get 4.23 exercise solution
4.24 Determine which of the following are reducible over GF(2).
a.x3 + 1
b.x3 + x2 + 1
c.x4 + 1 (be careful) Get 4.24 exercise solution
4.25 Determine the gcd of the following pairs of polynomials.
a.x3 + x + 1 and x2 + x + 1 over GF(2)
b.x3 - x + 1 and x2 + 1 over GF(3)
c.x5 + x4 + x3 - x2 - x + 1 and x3 + x2 + x + 1 over GF(3)
d.x5 + 88x4 + 73x3 + 83x2 + 51x + 67 and x3 + 97x2 + 40x + 38 over GF(101) Get 4.25 exercise solution
4.26 Develop a set of tables similar to Table 4.7 for GF(4) with m(x) = x2 + x + 1. Get 4.26 exercise solution
4.27 Determine the multiplicative inverse of x3 + x + 1 in GF(24) with m(x) = x4 + x + 1. Get 4.27 exercise solution
4.28 Develop a table similar to Table 4.9 for GF(24) with m(x) = x4 + x + 1. Get 4.28 exercise solution
