HW #5 due Friday May 16 (problem 5 edited)

Given a natural number n and a prime p, let n_p denote the power to which p appears in the unique factorization of n. So n = product of {p^n_p : p prime}, where most of the factors are p⁰ = 1.

1. Write down necessary and sufficient conditions on the exponents {b_p, c_p} for b|c to be true.

2. Give a formula for gcd(b,c)_p in terms of b_p, c_p.

3. Prove that gcd is associative, in that gcd(a,gcd(b,c)) = gcd(gcd(a,b),c).

4. Let d be a common divisor of b,c. Show that gcd(b/d, c/d) | gcd(b,c).

5. The continued fractions expansion of a positive irrational real number r is
r = n₁ + 1/(n₂ + 1/(n₃ + 1/...
where each n_i is a positive natural number.
If r is rational, one can do the same thing, but the expansion terminates.

a. Show that "the" continued fractions expansion exists uniquely for any rational r.
(Actually this holds for real r too, but one needs to study convergence properly to make sense of that statement, and we haven't and won't.)

b. Optional: Compute it for the square root of 5.

c. Compute it for 140/49.

d. Explain the relation to the Euclidean algorithm (computing gcd(m,n) vs. expansion of m/n).