Classical Algebra

Written Assignment No. 2

due Friday, October 10, 2003

Directions: Written assignments must be typeset. While it is neither necessary nor desirable to show small details of computation, you must indicate what you are doing and explain any reasoning used. Accuracy is important in completing this assignment.

If you are in the writing intensive division of the course, you must complete each written assignment in a satisfactory way. This may require re-submission, possibly more than once, after the initial evaluation.

1. Find the least non-negative residue of 2^{129} (mod 1025).

2. List all solutions that are distinct mod 40 for each of the following congruences:

(a) 3x ≡ 1 (mod 40).

(b) 3x ≡ 25 (mod 40).

(c) 28x ≡ 43 (mod 40).

(d) 59x ≡ 74 (mod 40).

(e) 25x ≡ 55 (mod 40).

3. List the number of distinct solutions mod 121461 for each of the following congruences:

(a) 48x ≡ 771 (mod 121461)

(b) 48x ≡ 6 (mod 121461)

(c) 48x ≡ 256 (mod 121461)

4. Prove that a and d have no common factor if there exist integers b and c such that

ac + bd = 1 .

5. Let a, b, and c be integers with a, b > 0. Prove that if there is an integer point (r, s) on the

line

ax + by = c ,

then there is one and only one integer point (x, y) on the line for which

0 ≤ x < \frac{b}{gcd(a, b)} .