# Discrete Mathematics Problem

## 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.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

\$60.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

### Find A Tutor

View available Discrete Math Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.