Chapter 4: Number Theory and Cryptography

What is the least common multiple of each pairs in Exercise 24?

a)${\mathbf{2}}^{\mathbf{2}}\mathbf{\cdot }{\mathbf{3}}^{\mathbf{3}}\mathbf{\cdot }{\mathbf{5}}^{\mathbf{5}}\mathbf{,}{\mathbf{2}}^{\mathbf{5}}\mathbf{\cdot }{\mathbf{3}}^{\mathbf{3}}\mathbf{\cdot }{\mathbf{5}}^{\mathbf{2}}$

b)$\mathbf{2}\mathbf{\cdot }\mathbf{3}\mathbf{\cdot }\mathbf{5}\mathbf{\cdot }\mathbf{7}\mathbf{\cdot }\mathbf{11}\mathbf{\cdot }\mathbf{13}\mathbf{,}{\mathbf{2}}^{\mathbf{11}}\mathbf{\cdot }{\mathbf{3}}^{\mathbf{9}}\mathbf{\cdot }\mathbf{11}\mathbf{\cdot }{\mathbf{17}}^{\mathbf{14}}$

c) 17,$\mathbf{17}\mathbf{,}{\mathbf{17}}^{\mathbf{17}}$

d)${\mathbf{2}}^{\mathbf{2}}\mathbf{\cdot }\mathbf{7}\mathbf{,}{\mathbf{5}}^{\mathbf{3}}\mathbf{\cdot }\mathbf{13}$

e) 0, 5

f)$\mathbf{2}\mathbf{\cdot }\mathbf{3}\mathbf{\cdot }\mathbf{5}\mathbf{\cdot }\mathbf{7}\mathbf{,}\mathbf{2}\mathbf{\cdot }\mathbf{3}\mathbf{\cdot }\mathbf{5}\mathbf{\cdot }\mathbf{7}$

How many divisions are required to find gcd(144, 233) using the Euclidean algorithm?

List all integers between -100 and 100 that are congruent to -1 modulo 25 .

What is the original message encrypted using the RSA system with $n=43\cdot 59and\mathrm{e}=13$if the encrypted message is $066719470671$? (To decrypt, first find the decryption exponent d which is the inverse of $\mathrm{e}=13modulo42\cdot 58$).

Use Algorithm 5 to find $3^{2003}mod99$

What is the least common multiple of each pair in Exercise 25?

a)${\mathbf{3}}^{\mathbf{7}}\mathbf{\cdot }{\mathbf{5}}^{\mathbf{3}}\mathbf{\cdot }{\mathbf{7}}^{\mathbf{3}}\mathbf{,}{\mathbf{2}}^{\mathbf{11}}\mathbf{\cdot }{\mathbf{3}}^{\mathbf{5}}\mathbf{\cdot }{\mathbf{5}}^{\mathbf{9}}$

b)$\mathbf{11}\mathbf{\cdot }\mathbf{13}\mathbf{\cdot }\mathbf{17}\mathbf{,}{\mathbf{2}}^{\mathbf{9}}\mathbf{\cdot }{\mathbf{3}}^{\mathbf{7}}\mathbf{\cdot }{\mathbf{5}}^{\mathbf{5}}\mathbf{\cdot }{\mathbf{7}}^{\mathbf{3}}$

c)${\mathbf{23}}^{\mathbf{31}}\mathbf{,}{\mathbf{23}}^{\mathbf{17}}$

d)$\mathbf{41}\mathbf{\cdot }\mathbf{43}\mathbf{\cdot }\mathbf{53}\mathbf{,}\mathbf{41}\mathbf{\cdot }\mathbf{43}\mathbf{\cdot }\mathbf{53}$

e)${\mathbf{3}}^{\mathbf{13}}\mathbf{\cdot }{\mathbf{5}}^{\mathbf{17}}\mathbf{,}{\mathbf{2}}^{\mathbf{12}}\mathbf{\cdot }{\mathbf{7}}^{\mathbf{21}}$

f) 1111, 0

Find all solutions, if any, to the system of congruences $\mathbf{x}\mathbf{\equiv }\mathbf{7}\left(\mathrm{mod}9\right)\mathbf{,}\mathbf{}\mathbf{x}\mathbf{\equiv }\mathbf{4}\left(\mathrm{mod}12\right)$, and$\mathbf{x}\mathbf{\equiv }\mathbf{16}\mathbf{(}\mathbf{mod}\mathbf{}\mathbf{21}\mathbf{)}$

Find gcd(2n + 1.3 + 2), where n is a positive integer.[Hint: use the Euclidean algorithm]

Decide whether each of these integers is congruent to 3 modulo 7.

a) 37

b) 66

c) -17

d) -67

Complete the proof of the Chinese remainder theoremby showing that the simultaneous solution of a systemof linear congruences modulo pairwise relatively primemoduli Is unique modulo the product of these moduli.[Hint: Assume that x and y are two simultaneous solutions. Show that $\mathbf{mi}\mathbf{\mid }\mathbf{x}\mathbf{-}\mathbf{y}$for all i. Using Exercise 29,

conclude that$\mathbf{m}\mathbf{=}\mathbf{m}\mathbf{1}\mathbf{m}\mathbf{2}\mathbf{\cdots }\mathbf{mn}\mathbf{\mid }\mathbf{x}\mathbf{-}\mathbf{y}\mathbf{.}\mathbf{]}$