CONTINUED FRACTION
Submitted
by
SEEMALI BEHERA
Roll No.- 11818V234055
Under the Supervision
of
Dr. Anasuya Nath
P.G. Department of Mathematics
Utkal University,Vani Vihar
Bhubaneswar-751004,Odisha,India
(Utkal University) Continued Fraction 1 / 25
Overview of Talk
1 Basic Definition of Number Theory
2 Continued Fraction
3 Periodic Continued Fraction
4 pell’s Equation
5 Reference
(Utkal University) Continued Fraction 2 / 25
Basic Definition of Number Theory
Definition of GCD
let pandq be two integers where at least one of them is not zero. The
greatest common divisor(gcd) of p and q, denoted by gcdpp, qq,is the
positive integer d satisying:
(1) d divides both p and q
(2) If c divides both p and q,then c divides d.
Theorem
Let p , q and s be integers. If p divides both q and s , then p divides
qx ` sy, @x,y P Z
The Division Algorithm
Given integers p and q, with q ą 0, there exists unique integers m and r
such that p “ q.m ` r , with 0 ď r ă q. p is called as dividend, q the
divisor, m the quotient and r is the reminder.
(Utkal University) Continued Fraction 3 / 25
Basic Definition of Number Theory
Lemma
Let p and q be two integers. If p “ q.m ` r ,then gcdpp, qq=gcdpq, rq
Theorem
Given two integers p and q not both zero. Then the greatest common
divisor of p and q is a linear combination of them, i.e. there exists two
integers m and n such that gcdpp,qq=mp ` nq.
The Euclid Algorithm
Euclidean algorithm is a method of finding the greatest common divisor of
two given integers. It consists of repeated divisions. In this algorithm we
apply the Division Algorithm repeatedly until we obtain a zero reminder.
(Utkal University) Continued Fraction 4 / 25
Continued Fraction
A continued fraction is an expression of a number as the sum of an integer
and a quotient, the denominator of which is the sum of an integer and a
quotient,and so on.
Definition
A continued fraction is an expression of the form
b0
a0 `
b1
a1 `
b2
a2 `
b3
a3 `
.
a4 ` . .
where a0, a1, a2, ¨¨¨, b0, b1, b2, ¨¨¨ can be real or complex numbers.
(Utkal University) Continued Fraction 5 / 25
Continued Fraction
Definition
A simple(regular) continued fraction is a continued fraction of the form
1
a0 `
1
a1 `
1
a2 `
1
a3 `
.
a4 ` . .
where ai is an integer for all i with a1, a2, a3, ¨¨¨ą 0.
The numbers ai , i “ 0, 1, 2, ¨¨¨are called as partial quotients of the
continued fractions.
(Utkal University) Continued Fraction 6 / 25
Continued Fraction
Definition
A finite simple continued is a simple continued fraction with a finite
number of terms.In symbols:
1
a0 `
1
a1 `
1
a2 `
. 1
.. `
1
an´1 `
an
It is also common to express the finite simple continued fractions as
ra0; a1, a2, ¨¨¨, ans.
(Utkal University) Continued Fraction 7 / 25
Continued Fraction
Definition
An infinite simple continued fraction is a simple continued fraction with
infinite number of terms. In symbols:
1
a0 `
1
a1 `
1
a2 `
1
a3 `
.
a4 ` . .
It can be also expressed as ra0; a1, a2, ¨¨¨s.
(Utkal University) Continued Fraction 8 / 25
Continued Fraction
Theorem
Any rational number can be written as a finite continued fraction.
Example
Consider a rational number 19
51 . Now
51 “ 2.19 ` 13
19 “ 1.13 ` 6
13 “ 2.6 ` 1
6 “ 6.1 ` 0
(Utkal University) Continued Fraction 9 / 25
Continued Fraction
it is seen that
1 1 1 1 1
19
“ 1
“ 13 “
“ “ “
1 1 1 1
51
51
19 2` 19
2` 2` 2` 2`
19
1` 6
1 1
13 13
1` 1`
13
6 2` 1
6
which is the continued fraction expansion for 19{51, symbolically:
r0; 2, 1, 2, 6s.
Definition
The continued fraction made from ra0; a1, ¨¨¨, ans by cutting off the
expansion after kth partial denominatorak is called the kth convergent of
the given continued fraction and denoted by Ck ; in symbols,
Ck “ ra0; a1, ¨¨¨, ak s where 1 ď k ď n
(Utkal University) Continued Fraction 10 / 25
Continued Fraction
Going back to our previous example 19{51 “ r0; 2, 1, 2, 6s, the successive
convergents are
C0 “ 0
1 1
C1 “ r0; 2s “ 0 ` “
2 2
1 1
C2 “ r0; 2, 1s “ 0 ` 1 “
2` 1 3
1 3
C3 “ r0; 2, 1, 2s “ 0 ` “
1 8
2`
1` 1
2
19
C4 “ r0; 2, 1, 2, 6s “
51
(Utkal University) Continued Fraction 11 / 25
Continued Fraction
Let us define numbers pk and qk pk “ 0, 1, ¨¨¨, nq as follows:
p0 “ a0 q0 “ 1
p1 “ a1a0 ` 1 q1 “ a1
pk “ akpk´1 ` pk´2 qk “ akqk´1 ` qk´2
for k “ 2, 3, ¨¨¨, n. and p´2 “ 0, p´1 “ 1, q´2 “ 1, q´1 “ 0
Theorem
The kth convergent of the simple continued fraction ra0;a1, ¨¨¨, ans has
the value
pk
Ck “ 0ď k ď n
qk
(Utkal University) Continued Fraction 12 / 25
Continued Fraction
Theorem
If Ck “ pqkk is the kth convergent of finite simple continued
fractionra0;a1, ¨¨¨, ans,then
k´1
pkqk´1 ´ qkpk´1 “ p´1q 1ď k ď n
Theorem
(a) The convergents with even subscripts form a strictly increasing
sequence, i.e.
C0 ă C2 ă C4 ă ¨¨¨
(b)The convergents with odd subscripts form a strictly decreasing
sequence, i.e.
C1 ą C3 ą C5 ą ¨¨¨
(c) Every convergent with an odd subscript is greater than every convrgent
with an even subscript.
(Utkal University) Continued Fraction 13 / 25
Infinite Continud Fraction
Definition
If a0, a1, a2, ¨¨¨ is a infinite sequence of integers, all positive except
possibly a0, then the infinite simple continued fraction ra0; a1, a2, ¨¨¨s has
the value
lim ra0; a1, a2, ¨¨¨, ans
nÑ8
Theorem
The value of any infinite continued fraction is an irrational number.
Theorem
If the infinite continued fraction ra0;a1, a2, ¨¨¨s and rb0; b1, b2, ¨¨¨s are
equal, then an “ bn, for all n ě 0.i.e. two distinct infinite continued
fractions are represented two distinct irrational numbers.
(Utkal University) Continued Fraction 14 / 25
Infinite Continued Fraction
In general given by
1
ak “ rxk s xk`1 “ kě 0
xk ´ ak
?
Consider an example,let x “ 23 « 4.8.Now,
? ?
x0 “ 23 “ 4 ` p 23 ´ 4q a0 “ 4
? ?
1 1 23 ` 4 23 ´ 3
x1 “ “ ? “ “ 1` a1 “ 1
x0 ´rx0 s 23 ´ 4 7 7
? ?
1 7 23 ` 3 23 ´ 3
x2 “ “ ? “ “ 3` a2 “ 3
x1 ´rx1 s 23 ´ 3 2 2
1 ? ?
2 23 ` 3 23 ´ 4
x3 “ “ ? “ “ 1` a3 “ 1
x2 ´rx2 s 23 ´ 3 7 7
1 7 ? ?
x4 “ “ ? “ 23 ` 4 “ 8 ` p 2 3 ´ 4q a4 “ 8
x3 ´rx3 s 23 ´ 4
(Utkal University) Continued Fraction 15 / 25
Infinite Continued Fraction
Because x5 “ x1, also x6 “ x2,x7 “ x3,x8 “ x4; then we get x9 “ x5 “ x1,
and so on, which means that the block of integers 1,3,1,8 repeat
?
indefinitely.We find that the continued fractions expansion of 23 is
periodic with the form
?
23 “ r4; 1, 3, 1, 8, 1, 3, 1, 8, ¨¨¨s “ r4; 1, 3, 1, 8s
Theorem
Let x be an arbitrary irrational number. If the rational number a{b, where
b ě 1 and gcdpa, bq=1, satisfies
ˇ aˇ 1
ˇx ´ b ˇ ă b2
then a{b is one of the convergents pn{qn in the continued fraction
representation of x.
(Utkal University) Continued Fraction 16 / 25
Periodic Continued Fraction
Definition
A quadratic irrational is an irrational number which is a root of a
quadratic equation of the form ax2 ` bx ` c “ 0, where a, b, c P Z and
a ‰0
Theorem
A number
?
is quadratic irrational if and only if it can be written in the form
p` q
r , where p, q, r P Z and r ‰0, and q is positive and not a perfect
square.
Lemma
If x is quadratic irrational and a0, a1, a2, ¨¨¨, an are integers, then the
following expression ra0;a1, a2, ¨¨¨, an, xs is a quadratic rational.
˝ If a0, a1, ¨¨¨, an P Z and x “ ra0, a1, ¨¨¨, ans, then x is quadratic
irrational.
(Utkal University) Continued Fraction 17 / 25
Periodic Continued Fraction
Example
Consider x “ r3; 6, 1, 4s, let us write x “ r3; 6, ys,
where,y “ r1, 4s “ r1; 4, ys
1 5y `1
Then, y “ 1 ` “ 1 ` 44yy`1 “ 4y `1
4 ` y1
implies,4y2 ´ 4y ´ 1 “ 0.
As y ą 0, and this equation? has only one positive root,
so choose that, y “ 1`2 2
From x “ r3; 6, ys, ? ? ? ?
1 25 ` 19 2 p25 ` 19 2qp8 ´ 6 2q 14 ´ 2
x=3+ “ ? “ ? ? “
1 8` 6 2 p8 ` 6 2qp8 ´ 6 2q 4
6 ` 1` ? 2
2 ?
2.
that is,x “ r3; 6, 1, 4s “ 14´
?4
By using algebra, x “ 14´4 2 ñ 16x 2 ´ 108x ` 194 “ 0
(Utkal University) Continued Fraction 18 / 25
Periodic Continued Fraction
Lemma
?
Every quadratic irrational can be written in the form m `s d , where
m, s, r P Z, s ‰0, d ą 0 and d is not a perfect square and s|pd ´ m2q.
?
˝ Let us look at an example: 2` 511 is not in the form laid out in the
lemma above since 5 ∤ p11 ´ 22q,However we can write
? ? ? ?
2` 11 5 2` 11 10 ` 11.5 2 10 ` 2 7 5
“ . “ “ .
5 5 5 25 25
This is desired form since 25|p275 ´ 102q.
?
Period Length of a Quadratic Irrational d
We know that quadratic irrationals are periodic.And the length of period is
that how long that period is.
(Utkal University) Continued Fraction 19 / 25
Pell’s Equation
Pell’s Equation
x2 ´ dy 2 “ 1, where d is positive integer and d is not a perfect square.
Theorem
If p, q is a positive solution of x 2 ´ dy 2 “ 1, then p{q is convergent of the
?
continued fraction expansion of d.
Theorem
?
If p{q is a convergnt of the continued fraction expansion of d , then
x “ p, y “ q is a solution of one of the equations
x2 ´ dy 2 “ k
?
where |k| ă 1 ` 2 d.
(Utkal University) Continued Fraction 20 / 25
Pell’s Equation
To find the? solution of x ´ 13y “ 1 is the smallest positive integers, we
2 2
note that 13 “ r3; 1, 1, 1, 1,
? 6s and that there is a period of length 5.
The first 10 convergents of 13 are
3{1, 4{1, 7{2, 11{3, 18{5, 119{33, 137{38, 256{71, 393{109, 649{180
With reference to part (b) of just previous theorem, the least positive
integers, we note that x 2 ´ 13y 2 “ 1 is obtained from the convergent
p9{q9 “ 649{180, the solution itself being x1 “ 649, y1 “ 180.
Theorem
Let x1, y1 be the fundamental solution of x2 ´ dy2 “ 1. Then every pair of
integers xn, yn defined by the conditions
? ?
xn ` y n d “ px1 ` y 1 d qn n “ 1, 2, 3, ¨¨¨
is also a positive solution.
(Utkal University) Continued Fraction 21 / 25
Pell’s Equation
Lastly look at an example that x1 “ 6, y1 “ 1 forms fundamental solutions of
x 2 ´ 35y 2 “ 1. A second positive solution x2, y2 can be obtained from the formula
? ? ?
x2 ` y2 35 “ p6` 35q 2 “ 71 ` 2 35
which implies that x2 “ 71 , y2 “ 12. These integers satisfy the equation
x 2 ´ 35y 2 “ 1 because,712 ´ 35.122 “ 5041 ´ 5040 “ 1
A third positive solution arises from
? ? ? ? ?
x3 ` y3 35 “ p6` 35q 3 “ p71 ` 12 35qp6 ` 35q “ 846 ` 143 35
This gives x ´ 3 “ 846 , y3 “ 143, and in fact8462 ´ 35.1432 “ 1
so these values are provide another solution.
Returning to the equation x2 ´ dy2 “ 1, a final result outcomes that
any positive solution can be calculated from the formula
? ?
xn ` yn d “ px1 ` y 1 d qn
when n takes on integral values;i.e,u,v are the positive solution of x 2 ´ dy 2 “ 1,
then u “ xn, v “ yn for suitably chosen integer n.
(Utkal University) Continued Fraction 22 / 25
Reference
Burton, D. M. Elementary Number Theory, (seventh Edition),
McGraw-Hill, New York, 2011.
Koblitz, N. A Course of Number Theory and Cryptography, (second
Edition), Springer-Verlag, New York, 1987.
Koshy, T. Elementary Number Theory with Application , (second
Edition), Elsevier, 2007.
Kumanduri R. and Romero C. Number Theory with Computer
Applications, Prentice Hall, New jersey, 1998.
Rosen, K. H. Elementary Number Theory and its Application,
Addison-Wiseley, 1984.
(Utkal University) Continued Fraction 23 / 25
THANK YOU
(Utkal University) Continued Fraction 24 / 25
