Math 620  Problem Set #3  Due Fri., Sept. 28, 2001

1. Let R be a commutative ring. If f(x) = ∑_{i=0}^{n} a_{i}x^{i} ∈ R[x], define its derivative f′(x) := ∑_{i=1}^{n} ia_{i}x^{i−1}.

a) Show that if f + g = h then f′ + g′ = h′; and that if fg = k then f′g + fg′ = k′.

b) Find all f such that f′ = 0 if R = ℤ. What if R = ℤ/p, where p is a prime number?

c) Show that f^{(j)} = 0 for j > n if n = deg f. (Here f^{(1)} = f′ and f^{(j+1)} = (f^{(j)})′ by definition.)

d) If R = ℤ, show that j! divides f^{(j)}(x) in ℤ[x] for all j.

e) Show that if f(x) ∈ ℤ[x] and x_{0} ∈ ℤ then

f(x_{0} + h) = f(x_{0}) + f′(x_{0})h + \frac{f′′}{2} (x_{0})h^{2} + ⋯ + \frac{f^{(n)}}{n!} (x_{0})h^{n}.

(Here n = deg f, and \frac{f^{(j)}}{j!} is the polynomial guaranteed by part (d).)

2. In the notation of PS 2 #3(c), verify for α = 29/11 and for α = 6188/4709 that

i) the determinant of ( \begin{matrix}p_{n} & p_{n+1} \\ q_{n} & q_{n+1} \end{matrix} ) is (−1)^{n}.

ii) the absolute value of the difference \frac{p_{n}}{q_{n}} − \frac{p_{n+1}}{q_{n+1}} is \frac{1}{q_{n}q_{n+1}} < \frac{1}{q_{n}^{2}} .

iii) |\frac{p_{n}}{q_{n}} − α| < \frac{1}{q_{n}^{2}} .

iv) p_{n} = a_{n}p_{n−1} + p_{n−2} and q_{n} = a_{n}q_{n−1} + q_{n−2}. Can you prove any of these facts in general?

3. a) Assuming that items (i)-(iv) in problem 2 hold in general, explain an efficient algorithm for finding solutions to ax + by = 1, when a and b are relatively prime integers.

b) Work this out for a = 620 and b = 101.

c) See if you can now do problem 2(b) on Problem Set 1 more efficiently.

d) Find all solutions to (7 + 11i)x + (3 + 5i)y = 1 + i in ℤ[i].

4. a) Show that if p is a prime number, then

x^{p} − x = x(x − 1) ⋯ (x − (p − 1)) ∈ ℤ/p[x].

Use this to evaluate (p − 1)! mod p.

b) By regarding 1, …, p − 1 ∈ U_{p}, and by pairing up each a ∈ U_{p} with its inverse, find (p − 1)! mod p in another way.

c) What if p isn’t prime?

5. a) Which of the following elements exist in the ring ℤ_{2} of 2-adic integers? \frac{1}{2}, \frac{1}{3}, \sqrt{−1}, \sqrt{2} b) What if ℤ_{2} is replaced by ℤ_{p}, where p = 3? 5? 7? 17? In both (a) and (b), when these elements exist, find the first few terms explicitly.