A. Student

Math 124 Problem Set 5

2. We establish both identities by induction. Claim: [a_{n}, a_{n−1}, …, a_{1}, a_{0}] = \frac{p_{n}}{p_{n−1}} . Since p_{−1} = 1 and p_{0} = a_{0}, [a_{0}] = \frac{p_{0}}{p_{−1}} . This establishes the base case. Now suppose that [a_{n−1}, …, a_{0}] = \frac{p_{n−1}}{p_{n−2}} . Then [a_{n}, a_{n−1}, …, a_{0}] = a_{n} + 1/[a_{n−1}, …, a_{0}] = a_{n} + _{\frac{1}{\frac{p_{n−1}}{p_{n−2}}}} = a_{n} + \frac{p_{n−2}}{p_{n−1}} = \frac{a_{n}p_{n−1}+p_{n−2}}{p_{n−1}} . The numerator is just the definition of p_{n}; this proves the claim. Claim: [a_{n}, a_{n−1}, …, a_{1}] = \frac{q_{n}}{q_{n−1}} . Since q_{0} = 1 and q_{1} = a_{1}, [a_{1}] = \frac{q_{1}}{q_{0}} . This establishes the base case. Now suppose that [a_{n−1}, …, a_{1}] = \frac{q_{n−1}}{q_{n−2}} . Then [a_{n}, a_{n−1}, …, a_{1}] = a_{n} + 1/[a_{n−1}, …, a_{1}] = a_{n} + _{\frac{1}{\frac{q_{n−1}}{q_{n−2}}}} = a_{n} + \frac{q_{n−2}}{q_{n−1}} = \frac{a_{n}q_{n−1}+q_{n−2}}{q_{n−1}} . The numerator is just the definition of q_{n}; this proves the claim.

3. If we compute ellj(t) in PARI, where t = −0.5+0.3281996289i the result is 61.7142856 …−6.2 E−26I. The imaginary part is effectively 0, so we wish to guess the rational number that gives the real part. The command contfrac(61.7142856) gives [61, 1, 2, 2, 178571], suggesting that a good guess for our rational number is given by the continued fraction [61, 1, 2, 2]. This value is \frac{432}{7}. 4i. Let α = [\overline{2, 3}]. Then α = 2 + \frac{1}{3+ \frac{1}{α}}, so 3α^{2} − 6α − 2 = 0. Solving for α yields 1 + \frac{\sqrt{15}}{3}. 4ii. First we compute α = [\overline{1, 2, 1}]. This gives α = 1+(2+ \frac{1}{(1+α^{−1})})^{−1}. Solving for α yields 3α^{2}−2α−3 = 0, so α = \frac{1+\sqrt{10}}{3}. Now [2, \overline{1, 2, 1}] = 2 + \frac{1}{[\overline{1,2,1}]}, so our final answer is \frac{5+\sqrt{10}}{3}. 4iii. This is [\overline{1, 2, 3}]^{−1}. As above, if α = [\overline{1, 2, 3}] then α = 1 + (2 + \frac{1}{3+ \frac{1}{α}})^{−1}. This simplifies to α = 7α^{2} + 8α − 3 = 0, so α = \frac{4+\sqrt{37}}{7}. Therefore our desired answer is \frac{−4+\sqrt{37}}{3}.

5. For all three parts we use contfrac in PARI to find the continued fraction and prove that the answer is correct. 5i. We claim that \sqrt{5} = [2, \overline{4}]. Let α = [\overline{4}]; then α = 4 + \frac{1}{α}, so α = 2 + \sqrt{5}. Now [2, \overline{4}] = 2 + \frac{1}{2+\sqrt{5}} = \sqrt{5}, as desired. 5ii. We claim that \frac{1+\sqrt{13}}{2} = [2, \overline{3}]. Let α = [\overline{3}]; then α = 3+ \frac{1}{α}, so α^{2} −3α−1 = 0. This gives α = \frac{3+\sqrt{13}}{2}. Then [2, \overline{3}] = 2 + \frac{2}{3+\sqrt{13}} = \frac{1+\sqrt{13}}{2}. 5iii. We claim that \frac{5+\sqrt{37}}{4} = [\overline{2, 1, 3}]. Let α = [\overline{2, 1, 3}]; then α = 2+(1+(3+ \frac{1}{α})^{−1})^{−1}, so 4α^{2}−10α−3 = 0. Solving for α gives \frac{5+\sqrt{37}}{4}, as desired. 6i. First we compute [\overline{2n}]. Let α = \overline{[2n]}; then α = 2n+ \frac{1}{α}. This gives α^{2}−2nα−1 = 0, so α = n+\sqrt{n^{2} + 1}. Now [n, \overline{2n}] = n + \frac{1}{α} = n − (n − \sqrt{n^{2} + 1}) = \sqrt{n^{2} + 1}, as desired. 6ii. Using the previous part, we know that \sqrt{5} = [2, \overline{4}]. We can try successive convergents until two agree up to four decimal places; once such convergent is 682/305.

7. In PARI, use convergents(contfrac(Pi)) to obtain the convergents of the continued fraction of π. We can now test convergents for property described in the problem, noting that smaller denominators are more likely to work. One convergent that satisfies the property is 3/1, since π − 3 < .15 and \frac{1}{\sqrt{5}} > .44. The next is 22/7, since 22/7−π < .002 and \frac{1}{49\sqrt{5}} > .009. A third is 355/113, since 355/113−π < .0000003 while \frac{1}{113^{2}\sqrt{5}} > .00003.

8. In PARI, the command contfrac(exp(2)) gives

[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, 77, 17, 1, 1, 18, 78, 20, 1, 1, 21, 90, …]

This suggests that after the initial 7, the ith group of 5 numbers is of the form

3(i − 1) + 2, 1, 1, 3i, 18 + 12(i − 1).

9i. We are looking for natural number solutions to n + 1 = x^{2}, \frac{n}{2} + 1 = y^{2}. Isolating n yields n = x^{2} − 1 = 2(y^{2} − 1), implying that x^{2} − 2y^{2} = −1. There are infinitely many solutions (x, y) to this equation if the period of the continued fraction of \sqrt{2} has odd order. Indeed, \sqrt{2} = [1, \overline{2}]. For each (x, y) we can take 2(y^{2} − 1) to find a unique (even) n; thus there are infinitely many n satisfying the desired property. 9ii. We can use the convergents program introduced in class to produce a list of convergents for the continued fraction of sqrt2. The odd terms are of interest, and since we want to find n > 389, we want the denominator of the convergent to be at least 14. The first two such convergents are \frac{41}{29} and \frac{239}{169}. They yield n = 2(29^{2} − 1) = 1680 and n = 2(169^{2} − 1) = 57120.

10. If x and y are consecutive integers, then we have z^{2} = x^{2} + (x + 1)^{2} = 2x^{2} + 2x + 1. Multiplying by 2, we have 2z^{2} = 4x^{2} + 4x + 2 = (2x + 1)^{2} + 1. Put u = 2x + 1; then u^{2} − 2z^{2} = −1. From the previous problem we know there are infinitely many solutions to this equation for u and z. Clearly each solution (u, z) gives a unique (x, z). Lastly we verify that each of these solutions (x, z) leads to a primitive Pythagorean triple. But this is trivial: clearly x and x + 1 are coprime, and if either shares a nontrivial divisor with z then the third must also share this divisor, implying that (x, x + 1) > 1, which is impossible.