QUESTION 1 1. Reformulate Equation (2.1), removing the restriction that a is a nonnegative integer. That is, let a be any integer. Path: p Words:0 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 bruteforce 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 – pi1. Hint: What numbers have a factor in common with pi? Path: p Words:0 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.. QUESTION 1
 Reformulate Equation (2.1), removing the restriction that ais a nonnegative integer. That is, let a be any integer.

10 points
QUESTION 2
 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
 Determine the GCD of the following;
 a) gcd(24140, 16762)
 b) gcd(4655, 12075)
20 points
QUESTION 4
 Using Fermat’s theorem to find a number xbetween 0 and 28 with x^{85} congruent to 6 modulo 29. (You should not need to use any bruteforce searching.)
10 points
QUESTION 5
 Use Euler’s theorem to find a number abetween 0 and 9 such that a is congruent to 7^{1000} modulo 10. (Note: This is the same as the last digit of the decimal expansion of 7^{1000}).
10 points
QUESTION 6
 Prove the following:
If p is prime, then φ(p^{1}) = p^{i} – p^{i1}. Hint: What numbers have a factor in common with p^{i}?

10 points
QUESTION 7
 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.