Math 620  Problem Set #2  Due Fri., Sept. 21, 2001

1. a) Show that there is a unique integer-valued function μ : ℕ → ℤ on the natural numbers such that μ(1) = 1 and ∑_{d|n} μ(d) = 0 for all n > 1. Find μ explicitly. Is μ

multiplicative (i.e. does it satisfy μ(ab) = μ(a)μ(b) for (a, b) = 1)?

b) Suppose that f, g are two integer-valued functions on ℕ, and that they are related by g(n) = ∑_{d|n} f(d). Show that f(n) = ∑_{d|n} μ(d)g(n/d).

c) What happens if f = ϕ (Euler phi function)? if f = identity function? if f = δ_{n,1} (Kronecker delta, which is 1 at 1 and is 0 elsewhere).

2. Let p ∈ ℕ be a prime number.

a) Show that p factors non-trivially in ℤ[i] if and only if p is a sum of two squares in ℤ. (Hint: Take norms.)

b) Suppose p = αβ in part (a). Show that (α) = (β) as ideals if and only if p = 2. (If (α) ≠ (β) we say that p splits; and if (α) = (β) we say that p ramifies.)

3. a) Show that if the Euclidean algorithm, applied to m and n, yields m = na_{1} + r_{1}, n = r_{1}a_{2} + r_{2}, r_{1} = r_{2}a_{3} + r_{3}, ..., r_{s−1} = r_{s}a_{s} + 0, then m/n = [a_{1}, …, a_{s}]. (See PS1, #1(b).)

b) Show this explicitly for m = 29, n = 11. In this example, how good an approximation to 29/11 is each convergent p_{1}/q_{i} := [a_{1}, …, a_{i}], relative to the denominator of the convergent? Conjecture? (Also see your calculations for PS1, #1(d).)

c) In part (b), consider the table

a_{1} a_{2} … a_{s}
p_{−1} p_{0} p_{1} p_{2} … p_{s}
q_{−1} q_{0} q_{1} q_{2} … q_{s}

where p_{−1} = q_{0} = 0 and p_{0} = q_{−1} = 1. What is the determinant of ( \begin{matrix}p_{i} & p_{i−1} \\ q_{i} & q_{i−1} \end{matrix} )?

What happens if you divide p_{i} by p_{i−1}, or q_{i} by q_{i−1}? (I.e. what are the quotient and remainder?) Conjecture? (Compare with your calculations in PS1, #1(c).) Show how this gives an efficient algorithm for determining the convergents to 29/11, and a solution to 29x + 11y = 1.

4. Find all solutions to the following systems:

a) 3x ≡ 4 (mod 7) and 5x ≡ 2 (mod 6)

b) x ≡ 3 (mod 10) and x ≡ 4 (mod 12)

c) x^{2} ≡ −1 (mod 125)

d) x^{3} ≡ 5 (mod 16) and x^{2} ≡ −1 (mod 125)