Chapter 4: Number Theory and Cryptography

Adapt the proof that there are infinitely many primes (Theorem

3 in Section 4.3) to show that there are infinitely many primes in the arithmetic progression 6k + 5 , k = 1 , 2 ,......

Convert the decimal expansion of each of these integers to a binaryexpansion.

1. \(321\)
2. \(1023\)
3. \(100632\)

Find the prime factorization of each of these integers.

d.) 1001 e.) 1111 f.) 909,090

Show that937is an inverse of 13modulo 2436 .

Encrypt the message STOP POLLUTION by translating the letters into numbers, applying the given encryption function, and then translating the numbers back into letters.

a) f(p)=(p+4) mod 26

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

c) f(p)=(17 p+22) mod 26

2. Which memory locations are assigned by the hashing

function $\mathbf{h}\mathbf{\left(}\mathbf{k}\mathbf{\right)}\mathbf{=}\mathbf{k}\mathbf{mod}\mathbf{101}$to the records of insurance

company customers with these Social Security numbers?

$$\begin{gathered} \mathbf{a}\mathbf{)}\mathbf{}\mathbf{104578690}\mathbf{}\mathbf{}\mathbf{b}\mathbf{)}\mathbf{}\mathbf{432222187} \\ \mathbf{c}\mathbf{)}\mathbf{}\mathbf{372201919}\mathbf{}\mathbf{}\mathbf{d}\mathbf{)}\mathbf{}\mathbf{501338753} \end{gathered}$$

Prove that if a is an integer other than\(0\), then

a) \(1\)divides a.

b) a divides\({\rm{0}}\).

a) Define what it means for a and b to be congruent m odulo 7.

b) Which pairs of the integers-11,-8,-7,-1,0,3 and 17are congruent ?

c) Show that ifa and bare congruent m odulo 7, then 10a+13 and -4b+20 are also congruent m odulo 7.

a) Explain why ndiv 7 equals the number of complete weeks in days.

b) Explain why n div 24 equals the number of complete days inn hours.

.Which integers leave a remainder of 1 when divided by 2

and also leave a remainder of 1 when divided by 3?