Chapter 4: Number Theory and Cryptography

Use Euclidean algorithm to find

1. \(\gcd \left( {12,\,18} \right)\)
2. \(\gcd \left( {111,\,201} \right)\)
3. \(\gcd \left( {1001,\,1331} \right)\)
4. \(\gcd \left( {12345,\,54321} \right)\)
5. \(\gcd \left( {1000,\,5040} \right)\)
6. \(\gcd \left( {9888,\,6060} \right)\)

33. Show that a positive integer is divisible by 3 if and only if the difference of the sum of its binary digits in even numbered positions and the sum of its binary digits in odd-numbered positions is divisible by 3.

Use Fermat’s little theorem to find $7^{121}mod13$

Determine whether the integers in each of these sets are

mutually relatively prime.

a) 8, 10, 12

b) 12, 15, 25

c) 15, 21, 28

d) 21, 24, 28, 32

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

Use Fermat’s little theorem to find${23}^{1002}mod41$

34. Find the one’s complement representations, using bit strings of length six, of the following integers.

(a) 22 b) 31 c) −7 d) −19

Does the check digit of an ISSN detect every single error in an ISSN? Justify your answer with either a proof or a counterexample.

Find a set of four mutually relatively prime integers such that no two of them are relatively prime.

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