[PDF] CONTINUED FRACTIONS AND PELLS EQUATION Contents 1

View - Download CONTINUED FRACTIONS AND PELLS EQUATION Contents 1

Previous PDF

Next PDF

CONTINUED FRACTIONS AND PELL'S EQUATION

SEUNG HYUN YANG

Abstract.

In this REU paper, I will use some important characteristics of continued fractions to give the complete set of solutions to Pell's equation. I would like to thank my mentor Avan for introducing and guiding me through this extremely interesting material. I would like to cite Steuding's detailed but slightly °awed book as the main source of learning and Andreescu and Andrica's book as an inspiration for numerous fun experiments I have made this summer.

Contents

1. Continued Fractions 1

2. Solution to Pell's Equation 9

References 12

1.Continued Fractions

This rather long section gives several crucial tools for solving Pell's equation.

De¯nition 1.1.

Leta0,a1,a2,:::,ambe real numbers. Then,

a 0+1 a 1+1 a 2+1 a 3+1 a 4+1

¢¢¢+1

a m¡1+1 a m is called a¯nite continued fractionand is denoted by [a0,a1,a2,...,am]. If the chain of fractions does not stop, then it is called anin¯nite continued fraction.

Remark1.2.

From now on, we will useanas it is de¯ned here.

De¯nitions 1.3.

(a) For n·m, [a0,a1,...,an] is callednth convergentto [a0,a1,a2, ...,am]. (b) De¯ne two sequences of real numbers, (pn) and (qn), re- cursively as follows: (1)p¡1= 1,p0=a0, andpn=anpn¡1+pn¡2; and (2)q¡1=

0,q0= 1, andqn=anqn¡1+qn¡2.

Remark1.4.

From now on, we will usepnandqnas they are de¯ned here.

Date: AUGUST 22, 2008.

1

2 SEUNG HYUN YANG

Theorem 1.5.

Let [a0,a1,a2,...,am] be a continued fraction. Then, for 0·n· m, pn q n= [a0,a1,a2,...,an].

Proof.

We proceed by induction. For n = 1,

[a0;a1] =a0+1 a 1 a1a0+ 1 a 1 =a1p0+p¡1 a

1q0+q¡1

=p1 q 1 as desired. Now, suppose the theorem holds for n. [a0;:::;an+1] = [a0;:::;an¡1;an+1 a n+1] (an+1 a n+1)pn¡1+pn¡2 (an+1 a n+1)qn¡1+qn¡2 (an+1an+ 1)pn¡1+an+1pn¡2 (an+1an+ 1)qn¡1+an+1qn¡2 an+1anpn¡1+an+1pn¡2+pn¡1 a n+1anqn¡1+an+1qn¡2+qn¡1 an+1(anpn¡1+pn¡2) +pn¡1 a n+1(anqn¡1+qn¡2) +qn¡1 an+1pn+pn¡1 a n+1qn+qn¡1 =pn+1 q n+1

Remark1.6.

As a result of this theorem, we will refer to

pn q nas the nth convergent.

Theorem 1.7.

Suppose thata0is an integer, thatanis a positive integer for each

1·n·m¡1, and that 1·am. Then,pnandqnare (a) integers and (b) coprime

for each 1·n·m¡1.

Proof.

(a)p¡1,q¡1,p0, andq0are integers by de¯nition.an's are also integers for

0·n·m¡1 by the given. Sincepnandqn(1·n·m¡1) are de¯ned as com-

binations of multiplication and subtraction of said variables (which are integers), they must be integers as well. (b) We use the following useful lemma:

Lemma 1.8.

For 1·n·m, following two relations hold:

(1)pnqn¡1¡pn¡1qn=(¡1)n¡1; and (2)pnqn¡2¡pn¡2qn=(¡1)nan.

CONTINUED FRACTIONS AND PELL'S EQUATION 3

Proof.

(1) p nqn¡1¡pn¡1qn= (anpn¡1+pn¡2)qn¡1¡pn¡1(anqn¡1+qn¡2) = (¡1)(pn¡1qn¡2¡pn¡2qn¡1) = (¡1)n(p0q¡1¡p¡1q0) = (¡1)n(¡1) = (¡1)n¡1 as desired. (2) p nqn¡2¡pn¡2qn= (anpn¡1+pn¡2)qn¡2¡(anqn¡1+qn¡2)pn¡2 =an(pn¡1qn¡2¡pn¡2qn¡1) = (1) n¡2an = (¡1)nan To complete the proof of Theorem 1.7, consider (1) of Lemma 1.8. Since there is a linear combination ofpnandqnthat is equal to§1, by elementary proposition from number theory, we conclude they are coprime as greatest common divisor We now move on to use continued fractions to approximate real numbers.

De¯nition 1.9.

Let®be a real number. Forn= 0,1,2,..., de¯ne a recursive algorithm as follows:®0=®,an=b®nc, and®n=an+1 n+1.

Remark1.10.

Here,b cis used as a °oor function. That means, by the last equation, nis positive for all positiven. Observe that1 n+1=®n-b®nc. Thus, the left side of the equation must be less than 1, and therefore®n+1>1. Then, by de¯nition, a n+1is a positive integer. Thus, we may conclude that®n,an¸1 forn¸1. Observe also that, given positivem,®= [a0,a1,...,am¡1,®m]. It is called the mth continued fraction of®.

Remark1.11.

Observe that, if®is rational, then the algorithm above is equivalent to Euclidean algorithm, with®n, when reduced to a fraction of coprimes, consist- ing ofnth remainder as numerator andn+ 1th remainder as denominator. That means, the continued fraction of a rational number is ¯nite. On the other hand, if®is irrational, then the continued fraction must be in¯nite simply because any ¯nite continued fraction is rational (and therefore cannot be equal to an irrational number).

Theorem 1.12.

Let®be irrational andpn

q nbe a convergent to its continued fraction. Then, (1.13)®¡pn q n=1 q n(®n+1qn+qn¡1):

4 SEUNG HYUN YANG

Proof.

Let n be a positive number. Then,®= [a0,a1,...,an,®n+1]. Then,

®¡pn

q n=®n+1pn+pn¡1 n+1qn+qn¡1¡pn q n q n(®n+1qn+qn¡1) pn¡1qn¡pnqn¡1 q n(®n+1qn+qn¡1) (¡1)(pnqn¡1¡qnpn¡1) q n(®n+1qn+qn¡1) (¡1)n q n(®n+1qn+qn¡1)

Remark1.14.

Observe, for each positiven,an·®nby a property of °oor function. Also, sinceq¡1,q0, andan(n >0) are positive integers, the same must be true for q n(n >0) by de¯nition. Then,

¯¯¯®¡pn

q n¯

¯¯¯=1

q n(®n+1qn+qn¡1) 1 q n(an+1qn+qn¡1) 1 q nqn+1: By de¯nition,qn=anqn¡1+qn¡2. Since 1·anandqn¡2>0, we conclude that q nis strictly increasing asnincreases. Then, we may conclude that the continued fraction of a number converges to that number by the inequality just given here.

In other words,

®= limn!1pn

q n= [a0,a1,a2,...].

Corollary 1.15.

Let®be a real number with convergentpn

q n. Then, jqn®¡pnjProof.

By Theorem 1.12,

¯¯¯¯®¡pn

q n¯

¯¯¯=1

q n(®n+1qn+qn¡1) ) jqn®¡pnj=1 q n®n+1+qn¡1

Similarly,

jqn¡1®¡pn¡1j=1 q n¡1®n+qn¡2

CONTINUED FRACTIONS AND PELL'S EQUATION 5

It now su±ces to prove the following inequality: 1 q n®n+1+qn¡1<1 q n¡1®n+qn¡2 1 q n¡1(an+1 n+1) +qn¡2 1 q n¡1an+qn¡1 n+1+qn¡2

®n+1

q n¡1an®n+1+qn¡1+qn¡2®n+1 ,qn¡1an®n+1+qn¡1+®n+1qn¡2< qn®2n+1+qn¡1®n+1 ,®n+1(qn¡1an+qn¡2) +qn¡1< qn®2n+1+qn¡1®n+1 ,qn®n+1+qn¡1< ®n+1(qn®n+1+qn¡1) ,1< ®n+1 We are now ready to move onto two extremely beautiful and important approx- imation theorems involving convergents.

Theorem 1.16.

(The Law of Best Approximations)Let®be a real number with convergent pn q nandn¸2. Ifp,qare integers such that 0< q·qnandp q 6= p n q n, then jqn®¡pnjMoreover, a reduced fraction p0 q

0withq0¸q2that satis¯es the latter inequality is a

convergent.

Proof.

By Corollary 1.15, we have already proven the case in which p q is a conver- gent. Supposeq=qn. Then,p6=pn.¯¯¯¯p q

¡pn

q n¯

¯¯¯=jp¡pnj

q n 1 q n:

¯¯¯¯®¡pn

q n¯

¯¯¯<1

q nqn+1 1 2qn becauseqn+1¸3 ifn¸2 (qnis strictly increasing forn¸1 andq1¸q0= 1). By the Triangle Inequality, we have¯¯¯¯®¡p q

¯¯¯¸¯¯¯¯p

q

¡pn

q n¯ q n¯ 1 q n¡1 2qn 1 2qn >¯¯¯¯®¡pn q n¯

6 SEUNG HYUN YANG

Multiplying both sides byq=qn, we obtain the desired inequality. Now suppose 0< q < qn. We may set up following system of two equations with two variables X and Y: p nX+pn¡1Y=p(1.17) q nX+qn¡1Y=q(1.18) A series of basic manipulations from high school mathematics yields the following unique solution (x,y): x=pqn¡1¡qpn¡1 p nqn¡1¡pn¡1qn y=pqn¡qpn p nqn¡1¡pn¡1qn

By Lemma 1.8, the denominators reduce to§1:

x=§(pqn¡1¡qpn¡1) y=§(pqn¡qpn)

Therefore, x and y are nonzero (otherwise

p q is a convergent) integers. By the equation 1.18, sinceqn> q, we conclude that x and y have opposite signs. By

Lemma 1.8,®¡pn

q nalternates signs. That is,®¡pn q nand®¡pn¡1 q n¡1have opposite signs. This implies thatqn®¡pnandqn¡1®¡pn¡1have opposite signs as well. Therefore,x(qn®¡pn) andy(qn¡1®¡pn¡1) have the same sign. Thus, q®¡p= (qnx+qn¡1y)®¡(pnx+pn¡1y) =x(qn®¡pn) +y(qn¡1®¡pn¡1) ) jq®¡pj=jx(qn®¡pnj+jy(qn¡1®¡pn¡1)j ) jq®¡pj>jqn¡1®¡pn¡1j >jqn®¡pnj as desired. In particular, this inequality holds forqn¡1< q < qn, which, by Induc-

Theorem 1.19.

(a) Given any two consecutive convergents to a real number®, there is at least one satisfying

¯¯®¡p

q

¯¯¯<1

2q2 (b) Any reduced fraction that satis¯es the above inequality is a convergent.

Proof.

(a) By Lemma 1.8, given any two consecutive convergents, exactly one is greater than or equal to®, and the other is less than or equal to®. Thus, (1.20)

¯¯¯¯p

n+1 q n+1¡pn q n¯ q n+1¯

¯¯¯+¯¯¯¯p

n q n¡®¯¯¯¯

CONTINUED FRACTIONS AND PELL'S EQUATION 7

Now, suppose the said inequality is not true for some consecutive convergents pn q nandpn+1 q n+1. By Lemma 1.8, 1 q nqn+1=¯¯¯¯p n+1qn¡pnqn+1 q nqn+1¯

¯¯¯=¯¯¯¯p

n+1 q n+1¡pn q n¯ =¯¯¯¯®¡pn+1 q n+1¯

¯¯¯+¯¯¯¯p

n q n¡®¯¯¯¯ 1

2q2n+1+1

2q2n 1 q nqn+1¸1

2q2n+1+1

2q2n=q2n+q2n+1

2q2nq2n+1

)2qnqn+1¸q2n+q2n+1 )0¸(qn¡qn+1)2 Becauseqnis strictly increasing for positive n, this may be true only ifn= 0 and q

1=q0=a1= 1. Thus, by contradiction, (a) is true for all positiven, and we

only need to check for the casen= 0 (the two consecutive convergents beingp0 q

0andp1

q 1): 01¡®=a1a0+ 1¡®=a0+ 1¡®=a0+ 1¡[a0;1;a2;a3;:::] <1¡1 1 + 1 a

2= 1¡a2

a

2+ 1·1

2 which satis¯es the statement of the theorem. (b) Suppose p q satis¯es the said inequality. By the law of best approximations, it su±ces to show p q is a best approximation to®. Let P Q be such thatP Q 6=p q andjQ®¡Pj · jq®¡pj=q¯¯¯®¡p q

¯¯¯<1

2q. Then,

1 qQ

·jpQ¡Pqj

qQ =¯¯¯¯p q ¡P Q

·¯¯¯¯®¡p

q

¯¯¯+¯¯¯¯P

Q 1 2q2+1 2qQ q+Q 2q2Q )1

[PDF] maths fractions

[PDF] Maths Fractions 3 ème

[PDF] maths fractions college

[PDF] maths fractions priorité operatoires

[PDF] Maths Fréquence valeurs

[PDF] maths full form

[PDF] Maths Géographie

[PDF] Maths géometrie

[PDF] maths geometrie 4 eme

[PDF] Maths géométrie dur

[PDF] Maths geometrie pyramides

[PDF] maths graphique fonction

[PDF] MATHS IMPORTAANT !!

[PDF] Maths in english

[PDF] maths informatique metier