Cryptography

1. Reformulate Equation (2.1), removing the restriction that a is a nonnegative integer. That is, let a be any integer.

10 points   

QUESTION 2

1. For each of the following equations, find an integer x that satisfies the equation.

a) 5x ≡ 4 (mod 3) 

b) 7x ≡ 6 (mod 5) 

c) 9x ≡ 8 (mod 7) 

30 points   

QUESTION 3

1. Determine the GCD of the following;

a) gcd(24140, 16762) 

b) gcd(4655, 12075) 

20 points   

QUESTION 4

1. Using Fermat's theorem to find a number x between 0 and 28 with x85 congruent to 6 modulo 29. (You should not need to use any brute-force searching.)

10 points   

QUESTION 5

1. Use Euler's theorem to find a number a between 0 and 9 such that a is congruent to 71000 modulo 10. (Note: This is the same as the last digit of the decimal expansion of 71000).

10 points   

QUESTION 6

1. Prove the following:

If p is prime, then φ(p1) = pi - pi-1. Hint: What numbers have a factor in common with pi?

10 points   

QUESTION 7

1. Six professors begin courses on Monday, Tuesday, Wednesday, Thursday, Friday, and Saturday, respectively, and announce their intentions of lecturing at intervals of 2, 3, 4, 1, 6, and 5 days, respectively. The regulations of the university forbid Sunday lectures (so that a Sunday lecture must be omitted). When first will all six professors find themselves compelled to omit a lecture? Hint: Use the CRT.