Math 620  Problem Set #1  Due Fri., Sept. 14, 2001

1. a) Use the Euclidean algorithm to find the g.c.d. of 110 and 39, and to find all the solutions of the Diophantine equation 110x + 39y = 1.

b) Let a_{1}, a_{2}, … be the quotients appearing in your calculation in (a). That is,

\begin{matrix}110 = 39 · a_{1} + r_{1}, \\ 39 = r_{1} · a_{2} + r_{2}, \end{matrix}

etc. Calculate [a_{1}, a_{2}, …, a_{n}] := a_{1} + _{\frac{1}{a_{2}+_{\frac{1}{a_{3}+ \frac{1}{···+ \frac{1}{an}}}}}} . Make a conjecture and try to prove

it in general.

c) Let α_{i} = [a_{1}, a_{2}, …, a_{i}], for 1 ≤ i ≤ n. Say α_{i} = \frac{p_{1}}{q_{i}} in lowest terms. Write out the numbers \frac{p_{1}}{q_{1}} , \frac{p_{2}}{q_{2}} , …, \frac{p_{n}}{q_{n}}. Compare with your answer in (a). Conjecture? Look for other patterns in the 2 × n matrix whose entries are the p_{i}’s and the q_{i}’s. Conjectures? Proofs?

d) Calculate α_{1}, …, α_{n} to several decimal places and display them on the number line. Any observations? Conjectures or proofs?

2. a) Use the Euclidean algorithm in ℚ[x] to find the g.c.d. of 2x^{2} +3x+5 and x^{2} −x+5. b) Use this calculation to find polynomials F (x), G(x) such that

(2x^{2} + 3x + 5)F (x) + (x^{2} − x + 5)G(x) = 1.

3. Find the following elements in ℤ/5: −1, \frac{1}{2}, \frac{2}{3}, \sqrt{−1}. How many of these can you find in ℤ/6? ℤ/10? ℤ/11? ℤ/13?

4. Let U_{m} = (ℤ/m)^{∗}, the multiplicative group of units in ℤ/m. Determine the structure of U_{m} for m = 17, 18, 21, 22, 25. Which are cyclic? Conjectures?

5. Define the sequence F_{n} of Farey fractions of order n to consist of the rational numbers in the interval [0, 1] that have denominator ≤ n, listed in increasing order and each expressed in lowest terms. Say \frac{a}{b}, \frac{c}{d} are consecutive in F_{n} (and of course, in lowest terms). What can you say about the determinant of the 2 × 2 matrix they form? (Try some examples.) Say \frac{a}{b}, \frac{c}{d}, \frac{e}{f} are consecutive. How do c, d seem to depend on a, b, e, f? Proof?

6. Define a norm N on ℤ[\sqrt{−2}], taking on non-negative integer values, and which is multiplicative. Show that there is a division algorithm with respect to N. (Hint: A picture might help.)