Chapter 4: Number Theory and Cryptography

Showthat\({{\rm{Z}}_m}\)with multiplication modulo m, where\({\rm{m}} \ge {\rm{2}}\)is an integer, satisfies the closure, associative, and commutativity properties, and\({\rm{1}}\)is a multiplicative identity.

Answer Exercise 37 for two's complement expansion.

How is the one's complement representation of the sum of two integers obtained from the one's complement representations of these integers?

Use Exercise 41 to determine whether\({M_{11}} = {2^{11}} - 1 = 2047\) and \({M_{17}} = {2^{17}} - 1 = 131,071\) are prime.

Use the extended Euclidean algorithm to express gcd(144,89) as a linear combination of 144 and 89.

Show that the check digit of an can always detect

a single error.

Answer Exercise 38 for two's complement expansion.

How is the one's complement representation of the difference of two integers obtained from the one's complement representations of these integers?

Use the extended Euclidean algorithm to express $\gcd (1001,100001)$ as a linear combination of 1001 and 100001.

Show that the distributive property of multiplication over addition holds for \({{\rm{Z}}_m}\), where \({\rm{m}} \ge {\rm{2}}\)is an integer.

Show that if n is prime and b is a positive integer with $n\times b$, then n passes Miller’s test to the base b.

Show that there are transpositions of two digits that are not detected by an ISBN-13.