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^n?1 ? 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).