Chapter 4: Number Theory and Cryptography

Does\(17\)divide each of these numbers?

a) \(68\)

b) \(84\)

c) \(357\)

d) \(1001\)

Determine whether each of these integers is prime.

a) 21 b) 29

c) 71 d) 97

e) 111 f) 143

Which memory locations are assigned by the hashing

function $h\left(k\right)=kmod97$to the records of insurance

company customers with these Social Security numbers?

$$\begin{gathered} \mathbf{a}\mathbf{)}\mathbf{}\mathbf{034567981}\mathbf{}\mathbf{b}\mathbf{)}\mathbf{}\mathbf{183211232} \\ \mathbf{c}\mathbf{)}\mathbf{}\mathbf{220195744}\mathbf{}\mathbf{d}\mathbf{)}\mathbf{}\mathbf{}\mathbf{987255335} \end{gathered}$$

Encrypt the message DO NOT PASS GO by translating the letters into numbers, applying the given encryption function, and then translating the numbers back into letters.

a) f(p)=(p+3) mod 26(the Caesar cipher)

b) f(p)=(p+13) mod 26

c) f(p)=(3 p+7) mod 26

Find$210\mathrm{div}17\mathrm{and}210\mathrm{mod}17$

The odometer on a car goes to up miles. The present owner of a car bought it when the odometer read miles. He now wants to sell it; when you examine the car for possible purchase, you notice that the odometer reads miles. What can you conclude about how many miles he drove the car, assuming that the odometer always worked correctly?

One digit in each of these identification numbers of a postal money order is smudged. Can you recover the smudged digit, indicated by a Q, in each of these numbers?

a) Q 1223139784

b) 6702120 Q 988

c) 27 Q 41007734

d) 213279032 Q 1

Explain how to convert from binary to base 64 expansions and from base 64 expansions to binary expansions and from octal to base 64 expansions and from base 64 expansions to octal expansions.

Evaluate these quantities.

a)−17 mod 2

b) 144 mod 7

c)−101 mod 13

d) 199 mod 19

Use the construction in the proof of the Chinese Remainder Theorem to find the solution of the system of congruences$\mathit{x}\mathbf{\equiv }\mathbf{2}\mathbf{(}\mathbf{mod}\mathbf{3}\mathbf{)}\mathbf{,}\mathbf{x}\mathbf{\equiv }\mathbf{1}\mathbf{(}\mathbf{mod}\mathbf{4}\mathbf{)}\mathbf{,}\mathbf{}\mathbf{and}\mathbf{}\mathbf{x}\mathbf{\equiv }\mathbf{3}\mathbf{(}\mathbf{mod}\mathbf{5}\mathbf{)}$