MATH 319 Midterm Exam

Answer all the following questions. Include all computations that are necessary for your answers.

1. State Fermat’s Theorem.

2. {1,2,3,…,34} is a complete residue system modulo 34. Is {4,8,12,…,136} a complete residue system mod 34? Explain your answer.

3. 3 is a primitive root mod 17. Briefly explain your answers to the following questions.

a) Find all the other primitive roots mod 17.

b) Show that 2 is not a primitive root mod 17.

c) Find all elements of order 4 mod 17.

d) How many solutions are there to ?

4. Find the smallest positive solution to the simultaneous congruences:

5. Prove that if p is a prime and , then

6. Let m = 91. Some of the terms below apply to m and some do not. Using only the numerical data below determine which terms apply to m and which do not. Specify the base a when necessary. Justify your answers.

Terms – 1. Prime

2. Composite

3. Probable Prime to base a

4. Strong Probable Prime to base a

5. Pseudoprime to base a

6. Strong Pseudoprime to base a.

Numerical Facts.

The smallest positive integer that is a strong pseudoprime to bases 2 and 3 is 1,373,653.