Chapter 4: Number Theory and Cryptography

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{]}$

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

a) 37

b) 66

c) -17

d) -67

Find$\mathbf{gcd}\mathbf{(}\mathbf{1000}\mathbf{,}\mathbf{625}\mathbf{)}$ and$\mathbf{Icm}\mathbf{(}\mathbf{1000}\mathbf{,}\mathbf{625}\mathbf{)}$ and verify that $\mathbf{gcd}\mathbf{(}\mathbf{1000}\mathbf{,}\mathbf{625}\mathbf{)}\mathbf{·}\mathbf{Icm}\mathbf{(}\mathbf{1000}\mathbf{,}\mathbf{625}\mathbf{)}\mathbf{=}\mathbf{1000}\mathbf{·}\mathbf{625}$.

Use Algorithm 5 to find ${123}^{1001}mod101$

a) Show that if aand bare positive integers with a > b, then

b) Explain how to use (a) to construct an algorithm for computing the greatest common divisor of two positive integers that uses only comparisons, subtractions, and shifts of binary expansions, without using any divisions.

c) Find using this algorithm

Describe the steps that Alice and Bob follow when they use the Diffie-Hellman key exchange protocol to generate a shared key. Assume that they use the prime $p=23$and take $a=5$, which is a primitive root of 23, and that Alice selects $k_1=8$and Bob selects $k_2=5$. (You may want to use some computational aid).

Decide whether each of these integers is congruent to 5 modulo 17.

a) 80

b) 103

c) -29

d) -122

Find$\mathbf{gcd}\mathbf{(}\mathbf{92928}\mathbf{,}\mathbf{123552}\mathbf{)}$ and$\mathbf{Icm}\mathbf{(}\mathbf{92928}\mathbf{,}\mathbf{123552}\mathbf{)}$ and verify that $\mathbf{gcd}\mathbf{(}\mathbf{92928}\mathbf{,}\mathbf{123552}\mathbf{)}\mathbf{\cdot }\mathbf{Icm}\mathbf{(}\mathbf{92928}\mathbf{,}\mathbf{123552}\mathbf{)}\mathbf{=}\mathbf{92928}\mathbf{\cdot }\mathbf{123552}$. [Hint: First, find the prime factorizations of 92928 and 123552.]

Let \({m_1}\) and \({m_2}\) be two relatively prime integers. This implies \({m_1} = \)

Prime decomposition.

Show that every positive integer can be represented uniquely as the sum of distinct powers of 2 . [Hint: Consider binary expansions of integers.]