SOAR Homework Two

These homework problems are meant to expand your understanding of what goes on during class. Any you turn in will be graded and returned to you. Answers may or may not be posted on the web, depending on demand.

Problems

Note: I have used the notation Sqrt(2) to denote the square root of 2, as we are on the border of my HTML knowledge. I hope that this is clear.

  1. In class we proved that Sqrt(2) is not rational. This problem provides another proof via a method called Fermat's infinite descent.
    1. Suppose that a and b are positive integers with a/b = Sqrt(2). Show that
       2b-a
      a-b
      		 = Sqrt(2)
      as well.

    2. Show that b > a-b > 0 and that 2b-a and a-b are integers.

    3. Deduce that if we can write Sqrt(2) as a ratio of integers, we can always make the denominator a smaller integer. Conclude that we may repeat this process (the descent) until the denominator is 1, so c/1 = Sqrt(2) for some integer c. This is a contradiction (Sqrt(2) is not an integer), so our original assumption (that Sqrt(2) is a fraction) must be false.

Recall that in class we defined a simple continued fraction as
[a1,a2,a3,a4,...] = a1 +  1
a2 +  1
a3 +  1
a4 + ...
where the ai are integers and ai > 0 for i > 2. (That is, all the ai are integers and only a1 may be negative or zero.) This fraction may continue forever, but if it terminates then we say it is a finite simple continued fraction.

  1. Let a=119 and b=37.
    1. Find the greatest common divisor gcd(a,b).

    2. Find the continued fraction representation of a/b.

    3. Repeat (a) and (b) with numbers of your own choosing. Make them as interesting as possible.

  2. Find the ordinary fraction representations of
    1. [1,2]

    2. [1,2,3]

    3. [1,2,3,4]

    4. [1,2,3,4,5]

    5. a finite simple continued fraction [a1,a2,a3,a4,a5] of your choosing.

  3. We saw in class that Sqrt(2) = [1,2,2,2,2,...] and Sqrt(3) = [1,1,2,1,2,1,2,...].
    1. Find the simple continued fraction for Sqrt(5).

    2. Find the simple continued fraction for Sqrt(6).

    3. Formulate a conjecture about Sqrt(k), where k is not a perfect square (so Sqrt(k) is not an integer).

  4. Let phi = [1,1,1,1,1,...]. Find an expression for phi that doesn't involve continued fractions.

  5. In class we saw that, while any integer can be factored uniquely into prime factors, this is not the case in every possible situation. This problem presents another situation where unique factorization fails. (You may skip part (b) if you like and just assume that it is true.)
    1. Let us write Z[Sqrt(-5)] for the set of numbers a+b Sqrt(-5), where a and b are integers. We can multiply these numbers together: show that
      (a + b Sqrt(-5)) · (c + d Sqrt(-5)) = (ac-5bd) + (bc+ad) Sqrt(-5).
      (Use the fact that (Sqrt(-5}))2 = -5.)

      We remark that Z is the usual notation for the integers, and Sqrt(-5) is just shorthand for ``a number about which all we know is that its square is -5.'' Thus Z[Sqrt(-5)] is notation that means the integers together with this Sqrt(-5).

    2. [Hard] Show that 1+Sqrt(-5) is ``prime'' in the sense that if (a+b Sqrt(-5)) ·(c + d Sqrt(-5)) = 1+Sqrt(-5), then either a+b Sqrt(-5)=±1 or c+d Sqrt(-5)=±1.

      You have just shown that multiplying two elements of Z[Sqrt(-5)] produces another element of Z[Sqrt(-5)]. We say that Z[Sqrt(-5)] is closed under multiplication.

    3. Finally, show that (1+Sqrt(-5))·(1-Sqrt(-5)) = 2 · 3, so 6 may be factored into ``primes'' in two different ways. (You may assume that 2, 3, and 1-Sqrt(-5) are ``primes'' here.)

These problems are also available as a pdf file.

Solutions

Please email Peter if you are interested in answers or solutions for the web. Thanks.

SOAR Spring 2003 Course Homepage