Chapter 4: Number Theory and Cryptography

By inspection (as discussed prior to Example1), find an inverse of 2 modulo 17 .

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

$$\begin{gathered} \mathbf{a}\mathbf{)}\mathbf{}{\mathbf{\left(}\mathbf{1101}\mathbf{\right)}}_{\mathbf{2}} \\ \mathbf{b}\mathbf{)}\mathbf{}{\mathbf{\left(}\mathbf{1010110101}\mathbf{\right)}}_{\mathbf{2}}\mathbf{} \\ \mathbf{c}\mathbf{)}\mathbf{}{\mathbf{\left(}\mathbf{1110111110}\mathbf{\right)}}_{\mathbf{2}}\mathbf{} \\ \mathbf{d}\mathbf{)}\mathbf{}{\mathbf{\left(}\mathbf{111110000011111}\mathbf{\right)}}_{\mathbf{2}} \end{gathered}$$

Find the prime factorization of each of these integers.

Decrypt these messages that were encrypted using the Caesar cipher.

a) EOXH MHDQV

b) WHVW WRGDB

c) HDW GLP VXP

Describe a procedure for converting decimal (base 10) expansions of integers into hexadecimal expansions.

Show that if aand d are positive integers, then there are integers and rsuch that a = dq + r where -d/2 < r < d/2 .

Fine the nonnegative integer a less than 28 represented by each of these pairs, where each pair represents (a mod 4, a mod 7).

a) (0,0)

b) (1,0)

c) (1,1)

d) (2,1)

e) (2,2)

f) (0,3)

g) (2,0)

h) (3,5)

i) (3,6)

Show that if a, b and m are integers such that$m\ge 2$ and $a\equiv b\left(\mathrm{mod}m\right)$, then $\gcd \left(a,m\right)=\gcd \left(b,m\right)$

Describe an algorithm to add two integers from their Cantor expansions.

Prove or disprove that$n^2-79n+1601$ is prime whenever n is a positive integer.