## Transcribed Text

Multiple Choice Question
1. Using fast modular exponentiation, how many operations (squaring and mod count as one
operation) does it take to compute 112580 mod 19?
a. 18
b. 19
C. 500
d. 2500 e. 112580
Free Response Questions
2. True or false? If the statement is true, give an explanation. If it is false, give a
counterexample.
"Iffi(x) is of order g(x), and f2(x) is of order g(x), then f1(x) + f2(x) is of order
g(x) too."
3. Compute 3 1048576 mod 7 using fast modular exponentiation. Hint: 1048576=2
Show all your steps.
4. Find the prime factorization of 216 - 1. (A mere calculator solution based on
evaluation of 216 - 1 is unacceptable. Hint: factor the expression.)
5. Prove: if n is a natural number, then 22n - 1 must be divisible by
3.
6. Given the base-k expansion of a natural number n, how can we tell whether n is
divisible by
k? You must prove your answer, based on the definition of base-k expansion.
7. In the lectures, we discussed an algorithm for primality testing. For testing whether a
natural number n is prime, the number of trial divisions needed for this algorithm is
of order n° for some real number p. Determine pand explain your answer. You do
not need to give an exact inequality- based proof based on the definition of order.
Using reasonable approximations is enough.

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.