**Homework for Mathematics of Information Security **

M360: Fall 2004

** HW 3: due Friday 9/10**

READ: Sections 3.3, 2.4, 2.5.

BOOK PROBLEMS: Section 2.14 # 3,4. Section 3.12, #2,3.

OTHER PROBLEMS:

A. Find all solutions to the following congruences by hand:

i) 7x=3 mod 15

ii) 6x=5 mod 15

iii) 8x=6 mod 14

iv) x^2=1 mod 8

v) x^2=2 mod 7

vi) x^2=3 mod 7.

B. Show that {3,5,7} is the only prime triplet.

(A set {n, n+2, n+4} is a prime triplet if all three numbers are prime).

C. Find all primes of the form p=n^2-1 and explain why you've got them all.

D. Compute (p-1)! mod p for several primes p and state a prediction for what it always is.

For example, when p=5, then (4)!=(4)(3)(2)(1)= 4 mod 5.

E. Pick m and a and calculate powers a, a^2, a^3, ... mod m (with maple or by hand).

Try varying m and a and generate some tables of data.

Write down 3 patterns that you notice.

Bonus Problems:

F. Show there are infinitely many primes which are 3 mod 4.

G. Explain why your answer to D is true.