Expert Answers

Expert Answers

1.   For each of the following pairs of numbers, say whether or not the two numbers are relatively prime. 

      (a) 18, 4 

      (b) 7, 27

      (c) 24, 33 

      (d) 22, 51

      (e) 0, 17

2.   For each of the following numbers n, list the nonnegative numbers less than n that are relatively prime to n, and use this list to find φ(n).
      (a) 18

      (b) 23

      (c) 77

      (d) 16

      (e) 15

3.   Use the rules of exponentiation to simplify each of the following formulae.

In the following problems you will use Euler’s Theorem and your knowledge of modular arithmetic to simplify a modular exponential expression bt rem m to a similar expression where the exponent is a small nonnegative integer. You should assume that the base b is relatively prime to m so that Euler’s Theorem is applicable. Show your work.

Question: modulus m = 4001 (a prime). Simplify b12006 rem m.

4.   In this problem we use the modulus m = 17. 

      (a) Simplify b19 rem 17. 

      (b) Simplify b33 rem 17.

(c) Simplify b52 rem 17.

      (d) Simplify b213 rem 17.

5.   In this problem we use the modulus m = 61. 

      (a) Simplify b61 rem 61.

      (b) Simplify b185 rem 61.

      (c) Simplify b2410 rem 61.

6.   In this problem we use the modulus m = 143. 

      (a) Simplify b225 rem 143.

      (b) Simplify b481 rem 143.

      (c) Simplify b12037 rem 143.

7.   Which of the following equations are true? Which are false? 

      (a) Is ?

      (b) Is ?

      (c) Is ?

      (d) Is ?

      (e) Is ?

8.   Solve for s or explain why no solution exists.
Powered by