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.

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.