Answers to HW #5

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.

A. For every p, b_p should be less than or equal to c_p. (I'm only writing out the English because I don't know how to produce the symbol in HTML.)

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

A. gcd(b,c)_p = min(b_p, c_p), the minimum of the two.

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

A. Either way, the exponent on p is min(a_p, b_p, c_p).

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

A. Looking at just the p-exponents, we know d_p is less than or equal to b_p, c_p. Then the statement is that for all p,
min(b_p - d_p, c_p - d_p) is less-or-equal min(b_p, c_p).
This is true; indeed, the difference is d_p.
So the better statement was
gcd(b/d, c/d) * 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.
OOPS possibly n₁=0, but the others are definitely positive.
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.)

First we address existence. Let r = n/d, for "numerator" and "denominator".

Proof by induction on d (which is at least 1).
If d=1, then r = n, so take n₁ = n and that's the complete expansion.
If d > 1, let n₁ be the greatest integer < r.
So r = n₁ + (n - d*n₁)/r, where the new numerator is in (0,r).
By induction, the fraction r/(n - d*n₁) has a finite continued fractions expansion.
(Here we crucially used n - d*n₁ < r to justify the invocation of induction.)
Sticking it into r = n₁ + 1 / r/(n - d*n₁), we get a c.f.exp. of r.

Now uniqueness, also done by induction on d.
If d=1, then r = n is the only c.f.exp., because having another term will spoil integrality.
Now assume d>1.
If r = n₁ + 1/(n₂ + 1/(n₃ + 1/... = m₁ + 1/(m₂ + 1/(m₃ + 1/...,
then the greatest integers less-or-equal to these three equal numbers must be the same.
For the second and third, said greatest integers are n₁, m₁.
Subtract those off, invert both sides, and you have an equality between two c.f.expansions of a rational with smaller denominator than you started (as in the previous proof).
So by the same induction, these two expansions must be equal.

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

A. Playing around with a calculator, it is easy to see that the first few n_i are 2,4,4,4,4... which suggests that one is stuck in a loop. Proving that involves a little bit of algebra with sqrt(5).

c. Compute it for 140/49.

140/49 = 2 + 1/(42/49)

49/42 = 1 + 1/(42/7)

42/7 = 6

so 140/49 = 2 + 1/(1 + 1/6).

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

A. They're really "the same".
At each step of the Euclidean algorithm, one must compute the remainder after division of m by n. If one instead wrote down the multiple of n being subtracted,the sequence of such multiples is exactly the sequence of n_i.
The sneaky thing is that to compute the continued fractions expansion of m/n, it is not important that m,n are in lowest terms. If one never simplifies them during the computationg of the c.f.exp., the last denominator one meets is gcd(m,n). For example, gcd(140,49)=7 in the one above.