Math 124, HW #3, Page 1, December 12, 2001  Student, F.

1. We use PARI to find the partial convergents using the program in class and Mathematica (see attached printout) to plot the stuff:

? \r conv.gp
? convergents([13,1,8,3])
%1 = [13, 14, 125/9, 389/28]
? convergents([1,1,1,1,1,1,1,1])
%2 = [1, 2, 3/2, 5/3, 8/5, 13/8, 21/13, 34/21]
? convergents([1,2,3,4,5,6,7,8])
%3 = [1, 3/2, 10/7, 43/30, 225/157, 1393/972, 9976/6961, 81201/56660]

2. See attached.

3. We use the technique of recognizing rationals from lecture 20.

? x = ellj(.5+.3281996289*I) \\ Find the invariant
%4 = 61.71428564980142595608262719 - 3.26348601 E-25*I
\\ Note: The imaginary part is very very small.
? contfrac(real(x)) \\ Expand into a continued fraction
%5 = [61, 1, 2, 2, 316482, 3, 2, 1, 1, 1, 4, 1, 3, 5, 1, 9, 9, 18, 2]
? contfracpnqn([61,1,2,2])
%6 =
[432 185]
[7 3]
? 432/7.0 \\ Evaluate a bit of the fraction
%8 = 61.71428571428571428571428571

Note how close \frac{432}{7} is to the real part of x. This is most likely the rational we’re looking for.

4. (a) x = [\overline{2, 3}].

x = 2 + \frac{1}{3 + x}
= 2 + \frac{x}{3x + 1}
⟹ 3x^{2} + x = 6x + 2 + x
⟹ 3x^{2} − 6x + 2 = 0
⟹ x = \frac{6 ± \sqrt{36 + 24}}{6}
⟹ x = 1 + \frac{\sqrt{60}}{6}

This checks out with what the computer sez’. Note that we took the positive root so that x would be positive.

(b) After extensive algebraic mistakes, we find that x = [\overline{1, 2, 1}] becomes, using a similar analysis to the previous part, 3x^{2} − 2x − 3 = 0, which implies x = \frac{2+\sqrt{40}}{6}. But [2, \overline{1, 2, 1}] = 2 + \frac{1}{[\overline{1,2,1}]} = \frac{5+\sqrt{10}}{3}.

(c) We use the same method to find that [\overline{1, 2, 3}] can be found by solving 7x^{2}−8x−3 =

0, which implies [\overline{1, 2, 3}] = \frac{4+\sqrt{37}}{7}. [0, \overline{1, 2, 3}] = 1 + \frac{7}{4+\sqrt{37}} = \frac{7\sqrt{37}−28}{21}.

5. We use the algorithm discussed in lecture.

(a)

\sqrt{5} = 2 + t_{0}
\frac{1}{t_{0}} = \frac{1}{\sqrt{5} − 2} = \frac{\sqrt{5} + 2}{1} = 4 + t_{1}
\frac{1}{t_{1}} = \frac{1}{\sqrt{5} − 2} = 4 + t_{2}

So, \sqrt{5} = [2, \overline{4}]. (b)

\frac{1 + \sqrt{13}}{2} = 2 + t_{0}
\frac{1}{t_{0}} = \frac{\sqrt{13} + 3}{2} = 3 + t_{1}
\frac{1}{t_{1}} = \frac{\sqrt{13} + 3}{2} = 3 + t_{2}

So, \frac{1+\sqrt{13}}{2} = [2, \overline{3}]. (c)

\frac{5 + \sqrt{37}}{4} = 2 + t_{0}
\frac{1}{t_{0}} = \frac{4}{sqrt37 − 3} = \frac{\sqrt{37} + 3}{7} = 1 + t_{1}
\frac{1}{t_{1}} = \frac{sqrt37 + 4}{3} = 3 + t_{2}
\frac{1}{t_{2}} = \frac{sqrt37 + 5}{4} = 2 + t_{3}

So, \frac{1+\sqrt{37}}{4} = [\overline{2, 1, 3}].

6. (a) Claim: For any positive integer n, \sqrt{n^{2} + 1} = [n, \overline{2n}]. Proof: First, we note that ⌊\sqrt{n^{2} + 1}⌋ = n. It is clear that n < \sqrt{n^{2} + 1} and it is also clear (by squaring both sides) that \sqrt{n^{2} + 1} < n + 1. Now we can use the continued fraction algorithm:

\sqrt{n^{2} + 1} = n + t_{0}
\frac{1}{t_{0}} = \frac{1}{\sqrt{n^{2} + 1} − n} = \frac{\sqrt{n^{2} + 1} + n}{1} = 2n + t_{1}
\frac{1}{t_{1}} = \frac{1}{\sqrt{n^{2} + 1} − n} = 2n + t_{2}

We’re done—\sqrt{n^{2} + 1} = [n, \overline{2n}].

(b) Let n = 2. Then \sqrt{5} = [2, \overline{4}]. We use a computer to check approximations:

? sqrt(5)     \\ What we want!
%4 = 2.236067977499789696409173668
? contfracpnqn([2,4])
%2 =
[9 2]
[4 1]
? 9/4.0
%3 = 2.250000000000000000000000000  \\ a bit off
? contfracpnqn([2,4,4])
%5 =
[38 9]
[17 4]
? 38/17.0
%6 = 2.235294117647058823529411764  \\ closer
? contfracpnqn([2,4,4,4])
%7 =
[161 38]
[72 17]
? 161/72.0
%8 = 2.236111111111111111111111111  \\ very close
? contfracpnqn([2,4,4,4,4])
%9 =
[682 161]
[305 72]
? 682/305.0
%10 = 2.236065573770491803278688524 \\ hey cool!

So \frac{682}{304} ≈ \sqrt{5}!

7. We are only asked to find some rational numbers that satisfy the inequality, so we use a computer to test some values. Clearly we are interested in \frac{a}{b} ≈ π, so we use continued fractions to find rational approximations for π. Then we write a little function that tests whether a certain rational number satisfies the inequality.

? \rmath124/conv.gp                \\ We borrowed this function
? convergents(contfrac(Pi))        \\ from lecture notes
%13 = [3, 22/7, 333/106, 355/113, 103993/33102, 104348/33215, ...]
\\ This is the function that will test:
? test(a,b)=1.0*abs(Pi-a/b)<1/(sqrt(5)*b^2)
? test(3,1)    \\ The simplest approximation works
%19 = 1
? test(22,7)            \\ So does the second simplest
%14 = 1
? test(333,106)         \\ Nope
%15 = 0
? test(355,113)         \\ Yep
%16 = 1
? test(103993,33102)    \\ Nope
%17 = 0
? test(104348,33215)    \\ Yep, a third.
%18 = 1

So, \frac{3}{1}, \frac{22}{7}, \frac{355}{113}, \frac{104348}{33214} all work!

8. We are only asked to postulate on whether or not there is a pattern. Let’s see what the continued fraction expansion of e^{2} is:

? \p500
   realprecision = 500 significant digits
? contfrac(exp(2))
%4 = [7, 2, 1, 1, 3, 18, 5, 1, 1, 6, 30, 8, 1, 1, 9, 42, 11, 1, 1,
12, 54, 14, 1, 1, 15, 66, 17, 1, 1, 18, 78, 20, 1, 1, 21, 90, 23,
1, 1, 24, 102, 26, 1, 1, 27, 114, 29, 1, 1, 30, 126, 32, 1, 1, 33,
138, 35, 1, 1, 36, 150, 38, 1, 1, 39, 162, 41, 1, 1, 42, 174, 44,
1, 1, 45, 186, 47, 1, 1, 48, 198, 50, 1, 1, 51, 210, 53, 1, 1,
54, 222, 56, 1, 1, 57, 234, 59, 1, 1, 60, 246, 62, 1, 1, 63, 258,
65, 1, 1, 66, 270, 68, 1, 1, 69, 282, 71, 1, 1, 72, 294, 74, 1, 1,
75, 306, 77, 1, 1, 78, 318, 80, 1, 1, 81, 330, 83, 1, 1, 84, 342,
86, 1, 1, 87, 354, 89, 1, 1, 90, 366, 92, 1, 1, 93, 378, 95, 1, 1,
96, 390, 98, 1, 1, 99, 402, 101, 1, 1, 102, 414, 104, 1, 1, 105,
426, 107, 1, 1, 108, 438, 110, 1, 1, 111, 450, 113, 1, 1, 114, 462,
116, 1, 1, 117, 474, 119, 1, 1, 120, 486, 122, 1, 1, 123, 498, 125,
1, 1, 126]

After the initial two digits, the pattern seems to be: 1, 1, 3+3k, 18+12k, 5+3k, where k starts at 0. So, [7, 2, 1, 1, 3+3∗0, 18+12∗0, 5+3∗0, 1, 1, 3+3∗1, 18+12∗1, 5+3∗1, …].

9. Claim: There are infinitely many even integers n such that both n + 1 and \frac{n}{2} + 1 are perfect squares. Proof: Let us write x^{2} = n+1 and y^{2} = \frac{n}{2} +1. We can substitute the first equation into the second to yield, y^{2} = \frac{x^{2}−1}{2}+1 ⇒ 2y^{2} = x^{2}+1 ⇒ 1 = 2y^{2}−x^{2} ⇒ −1 = x^{2}−2y^{2}. Now consider ℚ(\sqrt{2}). Define (as in lecture), N(a + \sqrt{2}b) = (a + \sqrt{2}b)(a − \sqrt{2}b) = a^{2} − 2b^{2}. Let z = 7 + 5\sqrt{2}. Note that N(z) = 49 − 25 ∗ 2 = −1. Since N(xy) = N(x)N(y), we have N(z^{k}) = −1 when k ≥ 1 is odd. Let’s compute some z^{k}, then take the a portion and call that x, plug it into our first formulas and find n:

k  z^{k}  x  n  \sqrt{\frac{n}{2} + 1}
1  7 + 5\sqrt{2}  7  48  5
2  99 + 70\sqrt{2}  k odd
3  1393 + 985\sqrt{2}  1393  1940448  985
5 275807 + 195025\sqrt{2} 275807 76069501248 195025

We can continue calculating z^{k} = x + y\sqrt{2}. Since N(z^{k}) = x^{2} − 2y^{2} = −1, we can find any number of x and y that satisfy the first two equations we wrote, which yield n = x^{2} − 1. It is trivial to see that the values of z^{k} will continue to increase and will never repeat. For part (b), we’ve found two such n in the calculations in the table.

10. We need to show that there exist infinitely many primitive Pythagorean triples x, y, z such that y = x + 1. Let’s start with x^{2} + (x + 1)^{2} = z^{2} ⟹ 2x^{2} + 2x + 1 − z^{2} = 0 ⟹ 4x^{2} + 4x + 2 − 2z^{2} = 0. Let’s complete the square: (2x + 1)^{2} + 1 − 2z^{2} = 0 ⟹ −1 = (2x + 1)^{2} + 2z^{2}, but this is just the same problem as problem 9, where we needed −1 = x^{2} − 2y^{2}. Sure enough, if 7 = 2x + 1, x = 3 implies 3^{2} + 4^{2} = 5^{2}, which is true. If 1393 = 2x + 1, then 696^{2} + 697^{2} = 985^{2}. Just like in problem 9, we can find an infinite number of these (2x + 1, z) pairs that satisfy x^{2} + y^{2} = z^{2} by just calculating (7 + 5\sqrt{2})^{k} for odd k.

It should be noted that this is not an exhaustive list. In both problems 9 and 10, we simply took an existing easy-to-see root, and then took it to powers to find other roots. I wrote a little program to find Pythagorean triples of this type on my HP48 and found the first several such triples:

\begin{matrix}n & x & y & z \\ 0 & 0 & 0 & 0 \\ 1 & 3 & 4 & 5 \\ 2 & 20 & 21 & 29 \\ 3 & 119 & 120 & 169 \\ 4 & 696 & 697 & 985 \\ 5 & 4059 & 4060 & 5741 \\ 6 & 23660 & 23661 & 33461 \\ 7 & 137903 & 137904 & 195025 \end{matrix}

It is curious to note that x_{n+1} = 4z_{n} + x_{n−1}. I can’t seem to prove that this is the case, but the pattern is very prevalent.