4.1. Briefly define a group. Get solution
4.2. Briefly define a ring. Get solution
4.3. Briefly define a field. Get solution
4.4. What does it mean to say that b is a divisor of a? Get solution
4.5. What is the difference between modular arithmetic and ordinary arithmetic? Get solution
4.6. List three classes of polynomial arithmetic. Get 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 > 2. Get solution
4.2 Does the set of residue classes modulo 3 form a group
a. with respect to addition?
b. with respect to multiplication? Get solution
4.3 Consider the set S = {a, b} with addition and multiplication defined by the tables:
Is S a ring? Justify your answer. Get solution
4.6 Find integers x such that
a. 5x 4 (mod 3)
b. 7x 6 (mod 5)
c. 9x 8 (mod 7) Get solution
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 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 b (mod 0)? Get solution
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 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 solution
4.10 What is the smallest positive integer that has exactly k divisors, for 1 k 6? Get solution
4.11 Prove the following:
a. a b (mod n) implies b a (mod n)b. a b (mod n) and b c (mod n) imply a c (mod n) Get solution
4.12 Prove the following:
a. [(a mod n) (b mod n)] mod n = (a b) mod nb. [(a mod n) x (b mod n)] mod n = (a x b) mod n Get solution
4.13 Find the multiplicative inverse of each nonzero element in Z5. Get solution
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 9's" whenchecking computations in arithmetic. Get solution
a. Determine gcd(24140, 16762).
b. Determine gcd(4655, 12075). Get 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 At be the value of A in the Euclidean algorithm after the ith iteration. Show thatShow that if m, n, and N are integers with with 1 <=m, n, <=2N, then the Euclidean algorithm takes
at most 2N steps to find gcd(m, n). Get 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 n
1. If An = Bn stop. gcd(A, B) = AnCn
2. If An and Bn are both even, setA n+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 = Cn5. If An and Bn are both odd, setA n+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.
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 solution
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)a. 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)
b. Show that if the algorithm does not stop before step (n 1), then
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 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 solution
4.20 Develop a set of tables similar to Table 4.3 for GF(5). Get solution
4.21 Demonstrate that the set of polynomials whose coefficients form a field is a ring. Get solution
4.22 Demonstrate whether each of these statements is true or false for polynomials over a field:
a. The product of monic polynomials is monic.
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 solution
4.23 For polynomial arithmetic with coefficients in Z10, perform the following calculations:
a. (7x + 2) (x2 + 5)
b. (6x2+ x + 3) x (5x2 + 2) Get 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 solution
4.25 Determine the gcd of the following pairs of polynomials:
a. x3+ x + 1 and x2 + x + 1 over GF(2)
b. x3x + 1 and x. + 1 over GF(3)
c. x5+ x4+ x3x2x + 1 and x3+ x2 + x + 1 over GF(3)
d. x5+ 88x4+ 73x3+ 83x2+ 51x + 67 and x3+ 97x2 Get solution
4.26 Develop a set of tables similar to Table 4.6 for GF(4) with m(x) = x4+ x + 1. Get solution
4.27 Determine the multiplicative inverse of x3+ x + 1 in GF(24), with m(x) = x4+ x + 1. Get solution
4.28 Develop a table similar to Table 4.8 for GF(24) with m(x) = x4+ x + 1. Get solution
