SOAR Homework Three

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

1. 1. Show that the continued fraction x=[1,2,1,2,1,2,1,2,...] satisfies the quadratic equation 2x² - 2x -1 = 0. Find the value of x.

   2. Show that the other root of this equation is -1/[2,1,2,1,2,1,...].

   3. Find the quadratic equation that the continued fraction x=[a,b,a,b,a,b,...] satisfies. Show that the other root of this equation is -1/[b,a,b,a,b,a,b,a,...].

   4. Find the quadratic equation that the continued fraction x=[a,b,c,a,b,c,a,b,c,....] satisfies.

   5. The other root of this equation is probably either -1/[c,b,a,c,b,a,...], -1/[a,c,b,a,c,b,...], or -1/[b,a,c,b,a,c,...]. Can you tell which without solving the equation?

2. One of the skipped parts of a proof from today's class was the following claim: that x can be written as
   

   x =  xn pn-1 + pn-2 xn qn-1 + qn-2

   (1)

   where x = [a₁,a₂,a₃,...], x_n is defined by x=[a₁,a₂,...,a_n-1,x_n], and the nth convergent is C_n = p_n/q_n = [a₁,a₂,...,a_n].
   1. Prove that p_n+1 = a_n+1p_n + p_n-1 and a_n+1 = a_n+1q_n + q_n-1 for n=1, n=2, and n=3. By convention, (that is, so the formulas work) we assume p₀ = 1 and q₀ = 0.

   2. Prove equation (1) for n=1, n=2, and n=3.

3. Another of the skipped parts is that equation (1) gives us a nice inequality for x:
   

   pn-1 qn-1 < x <  pn-2 qn-2

   (2)

   (provided n is even). We prove this by showing that A/B < C/D implies that
   

   A B <  xA+C xB+D <  C D

   (3)

   and
   

   A B <  A+xC B+xD <  C D .

   (4)

   (Here A, B, C, D, and x are any positive real numbers.)
   1. For the first equation, prove that A(xB+D) = AD + xAB < BC + xAB=B(xA+C).

   2. Use the inequality from part (a) to prove that A/B < (xA+C)/(xB+D).

   3. Use a similar technique to prove the other inequalities involved in equations (3) and (4).

   4. Use equations  and  to prove equation .

Note: In the following problems, I use for the three-line ``equivalent to'' sign, for ease of browsing.

4. Solve the following equations for x. That is, find a value (not all values) satisfying the equations. Fair warning: at least one has no solution!
   1. 203x + 73 = 0 mod 8

   2. x² + 42x + 64 = 0 mod 3

   3. (x+2)³ = 1 mod 3

   4. (x+2)³ = 2 mod 3

   5. (x+2)⁴ = 2 mod 3

5. In class we discussed a simple version of the Chinese Remainder Theorem, which says that if gcd(m,n) = 1, then given two integers a and b there is a unique value of x with 0 =< x < mn such that

   x = a	mod	m
   x = b	mod	n

   1. Solve for x if m=5, n=6, a=3, and b=1. That is, solve

      x = 3	mod	5
      x = 1	mod	6.

   2. Solve for x if m=13, n=11, a=1, and b=2. That is, solve

      x = 1	mod	13
      x = 2	mod	11.

   3. Can you write x (up to multiples of mn) in terms of a, b, m, and n?

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.