Chapter 4: Number Theory and Cryptography

Add (10111)2and (11010)2by working through each

step of the algorithm for addition given in the text.

Express each nonnegative integer a less than 15 as a pair (a mod 3, a mod 5).

Explain how to use the pairs found in Exercise 51 to add 4 and 7.

Prove or disprove that${\mathit{p}}_{\mathbf{1}}{\mathit{p}}_{\mathbf{2}}\mathbf{\dots }{\mathit{p}}_{\mathbf{n}}\mathbf{+}\mathbf{1}$is prime for every positive integer n, where role="math" localid="1668525741485" ${\mathit{p}}_{\mathbf{1}}\mathbf{,}{\mathit{p}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{.}\mathbf{.}\mathbf{,}{\mathit{p}}_{\mathbf{n}}$are the n smallest prime numbers.

Multiply (1110)2 and (1010)2 by working through each step of the algorithm for multiplication given in the text.

Show that there is a composite integer in every arithmetic progression$ak+b,k=1,2,....$ where a and b are positive integers.

Solve the system of congruence’s that arises in Example 8.

Describe an algorithm for finding the difference of two binary expansions.

Show that 2 is a primitive root of 19.

Adapt the proof in the text that there are infinitely many primes to prove that there are infinitely many primes of the form \(3k + 2\], where k is a non-negative integer. (Hint: Suppose that there are only finitely many such primes \({q_1),{q_2),...{q_n)\], and consider the number \(3{q_1){q_2)...{q_n) - 1\]].