Georgetown University Modular Arithmetic Questions

1. Consider the equation

197x≡367 mod 419

Suppose that I claimed that x≡155 is the solution. Write a few lines (line?) of Python code which verify that I am correct.

2. Do the same with the claim that x≡25 is a solution of the equation

x² −4x+ 19 ≡125 mod 419

3. Solve the following modular equations.

(a) 7x≡6 mod 25

(b) 3x+ 2 ≡1 −xmod 21

(c) 10001x≡4 mod 101

Hint: What is 100 mod 101? What is 10000 mod 101?

(d) 50x≡x−2 mod 155

4. Find an integer n>2 where 3 does not divide n and 3ⁿ⁻¹ ≡ 1 mod n

5. Compute the following number without the use of a computer:

11371495005541085992897640328743727364597182772002 mod 101

Your answer should be among 0,1,2,…,100. Note that 101 is a prime number.

6. Find a prime number p for which the equation

x² ≡−1 mod p

has no solution.

7. Find a prime number p for which the equation

x² ≡−1 mod p

has a solution.

8. Compute the following numbers, where φis Euler’s totient function.

(a) φ(2)

(b) φ(15)

(c) φ(27)

(d) φ(21000)

9. Compute

5^{2^999} mod 21000

10. Find a generator mod 191 (which is a prime number).