Chapter 4: Number Theory and Cryptography

^{Find each of these values.}

^{a) \(\left( {{\bf{177}}{\rm{ }}{\bf{mod}}{\rm{ }}{\bf{31}} + {\bf{270}}{\rm{ }}{\bf{mod}}{\rm{ }}{\bf{31}}} \right){\rm{ }}{\bf{mod}}{\rm{ }}{\bf{31}}\)}

^{b) \(\left( {{\bf{177}}{\rm{ }}{\bf{mod}}{\rm{ }}{\bf{31}} \cdot {\bf{270}}{\rm{ }}{\bf{mod}}{\rm{ }}{\bf{31}}} \right){\rm{ }}{\bf{mod}}{\rm{ }}{\bf{31}}\)}

If the product of two integers is 273852711 and their greatestcommon divisor is 23345, what is their least common multiple?

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 $k_2=5$and take $a=2$, which is a primitive root of $101$, and that Alice selects $k_1=7$and Bob selects $k_2=9$. (You may want to use some computational aid).

It can be shown that every integer can be uniquely represented in the form

$3^k+e_{k-1}{3}^{k-1}+\mathrm{L}+e_{1}3+e^j$

where$e_j=-1,0$, or 1 for j=0,1,2, …., k. Expansions of this type are called balanced ternary expansions. Find the balanced ternary expansions of

a) 5 .

b) 13 .

c) 37 .

d) 79 .

Which errors in a single digit of a 15 -digit airline ticket identification number can be detected?

Explain why you cannot directly adapt the proof that there

are infinitely many primes (Theorem 3 in Section 4.3) to show that are

infinitely many primes in the arithmetic progression 3 k + 1 , k = 1 , 2 , ...........

Find each of these values.

a)\(\left( {{\rm{ - 133 }}{\bf{mod}}{\rm{ 23}} + {\bf{2}}61{\rm{ }}{\bf{mod}}{\rm{ 23}}} \right){\rm{ }}{\bf{mod}}{\rm{ 23}}\)

b)\(\left( {45{\bf{7}}{\rm{ }}{\bf{mod}}{\rm{ 23}} \cdot 182{\rm{ }}{\bf{mod}}\;23} \right){\rm{ }}{\bf{mod}}{\rm{ 23}}\)

Show that \(a\)and\(b\)are positive integers, then\(ab = \gcd \left( {a,\,b} \right) \cdot lcm\left( {a,\,b} \right)\). (Hint: Use the prime factorizations of\(a\)and\(b\)also the formula for\(\gcd \left( {a,\,b} \right)\)and\(lcm\left( {a,\,b} \right)\)in terms of this factorization.)

Can the accidental transposition of two consecutive digits in an airline ticket identification number be detected using the check digit?

Which integers are divisible by 5 but leave a remainderof 1 when divided by 3?