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.