| 4.1 | For the group Sn of all permutations of n distinct symbols, What is the number of elements in Sn? Show that Sn is not abelian for n > 2.
|
| 4.2 | Does the set of residue classes modulo 3 form a group with respect to addition? with respect to multiplication?
|
| 4.3 | Consider the set S = {a, b} with addition and multiplication defined by the tables:
Is S a ring? Justify your answer. |
| 4.4 | Reformulate Equation (4.1), removing the restriction that a is a nonnegative integer. That is, let a be any integer. |
| 4.5 | Draw a figure similar to Figure 4.2 for a < 0. |
| 4.6 | Find integers x such that 5x  4 (mod 3) 6 (mod 5) 8 (mod 7)
|
| 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: 5 mod 3 5 mod 3 5 mod 3 5 mod 3
|
| 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 | 4.9 | In Section 4.2, 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 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). |
| 4.10 | What is the smallest positive integer that has exactly k divisors, for 1  6? |
| 4.11 | Prove the following: a n) implies b n) a n) and b n) imply a n)
|
| 4.12 | Prove the following: [(a mod n) (b mod n)] mod n = (a b) mod n [(a mod n) x (b mod n)] mod n = (a x b) mod n
|
|
[Page 132] |
| 4.13 | Find the multiplicative inverse of each nonzero element in Z5. |
| 4.14 | Show that an integer N is congruent modulo 9 to the sum of its decimal digits. For example, 475 4 + 7 + 5  16 1 + 6 7 (mod 9). This is the basis for the familiar procedure of "casting out 9s" when checking computations in arithmetic. |
| 4.15 | Determine gcd(24140, 16762). Determine gcd(4655, 12075).
|
| 4.16 | The purpose of this problem is to set an upper bound on the number of iterations of the Euclidean algorithm. Suppose that m = qn + r with q > 0 and 0 n. Show that m/2 > r. Let At be the value of A in the Euclidean algorithm after the ith iteration. Show that 
Show that if m, n, and N are integers with 1 n, 2N steps to find gcd(m, n).
|
| 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 n | If An = Bn stop. gcd(A, B) = AnCn If An and Bn are both even, set An+1 = An/2, Bn+1 = Bn/2, Cn+1 = 2Cn If An is even and Bn is odd, set An+1 = An/2, Bn+1 = Bn, Cn+1 = Cn If An is odd and Bn is even, set An+1 = An, Bn+1 = Bn/2, Cn+1 = Cn 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. To get a feel for the two algorithms, compute gcd(2152, 764) using both the Euclidean and Stein's algorithm. What is the apparent advantage of Stein's algorithm over the Euclidean algorithm?
|
| 4.18 | Show that if Stein's algorithm does not stop before the nth step, then Cn+1 x gcd(An+1, Bn+1) = Cn x gcd(An, Bn) Show that if the algorithm does not stop before step (n 1), then 
Show that if 1 2N steps to find gcd(m, n). Thus, Stein's algorithm works in roughly the same number of steps as the Euclidean algorithm. Demonstrate that Stein's algorithm does indeed return gcd(A, B).
|
| 4.19 | Using the extended Euclidean algorithm, find the multiplicative inverse of 1234 mod 4321 24140 mod 40902 550 mod 1769
|
| 4.20 | Develop a set of tables similar to Table 4.3 for GF(5). |
| 4.21 | Demonstrate that the set of polynomials whose coefficients form a field is a ring. |
| 4.22 | Demonstrate whether each of these statements is true or false for polynomials over a field: The product of monic polynomials is monic. The product of polynomials of degrees m and n has degree m + n The sum of polynomials of degrees m and n has degree max[m, n].
|
|
[Page 133] |
| 4.23 | For polynomial arithmetic with coefficients in Z10, perform the following calculations: (7x + 2) (x2 + 5) (6x2 + x + 3) x (5x2 + 2)
|
| 4.24 | Determine which of the following are reducible over GF(2): x3 + 1 x3 + x2 + 1 x4 + 1 (be careful)
|
| 4.25 | Determine the gcd of the following pairs of polynomials: x3 + x + 1 and x2 + x + 1 over GF(2) x3 x + 1 and x2 + 1 over GF(3) x5 + x4 + x3 x2 x + 1 and x3 + x2 + x + 1 over GF(3) x5 + 88x4 + 73x3 + 83x2 + 51x + 67 and x3 + 97x2 + 40x + 38 over GF(101)
|
| 4.26 | Develop a set of tables similar to Table 4.6 for GF(4) with m(x) = x4 + x + 1. |
| 4.27 | Determine the multiplicative inverse of x3 + x + 1 in GF(24), with m(x) = x4 + x + 1. |
| 4.28 | Develop a table similar to Table 4.8 for GF(24) with m(x) = x4 + x + 1. |
