Continued fractions

In this post, I will talk about the connection between continued fraction expansion of sqrt(d) (where d is a non-square positive integer) and the group of units in the ring of integers of a quadratic number field, namely  Q ( sqrt(d) ) , which consists of elements of the form a+b*sqrt(d) , where a and b are rationals.  There is a few special elements in the field  Q ( sqrt(d) ) ,  the first one is the integral element , which is a root of a monic polynomial with integer coefficients. Note that a monic polynomial is a polynomial whose highest term has a coefficient of 1 . For example, consider x = 2 - sqrt(5) in  Q ( sqrt(5) ) , and we can find the monic quadratic polynomial that x is a root of:  x - 2 = sqrt(5) (x − 2) 2  = 5 x 2  − 4x − 1 = 0 Since  x 2  −  4 x  −  1 is a monic polynomial, and x is one of its roots, we conclude that x is an integral element of  Q ( sqrt(5) ) . Secondly, the ring of integers is the ring of all integral elements contained in  Q ( sqrt(d) ) , an

Some Background Pell's Equation is a classic problem in number theory. It takes the form:  x 2  −  dy 2  = 1 , where x and y are unknown integers, and d is a positive non-square integer. The equation seeks integer solutions, making it a type of Diophantine equation - equations that require integer solutions.  Even though the equation is often referred to as "Pell's Equation", John Pell (1611 - 1685) had very little to do with this equation. Euler named the equation after Pell because he mistakenly attributed a solution method discovered by Lord Brouncker as Pell's work. Some people also refer the equation as "Fermat's  Equation" - it was in 1657 that Fermat issued the challenge: find a number y such that  dy 2  + 1  is a square number. In other words, find a number y such that  dy 2  + 1 = x 2 for some integer x . However, work on this equation dates back much further than these mathematicians mentioned above; it has been studied by Brahmagupta

Approximations to a given probability T here are many uses of continued fractions, one such common application is seeking a fraction with a relatively small denominator that well approximates a given probability. For example, a baseball player has a batting average of 0.334 , rounded to 3 digits, others may be interested at the possible "at bats" the player could have given this batting average. We have 0.334 = 167/500 , now it's quite common to feel quite certain that 500 must be the fewest "at bats" possible, but is this correct? We have a rational number x that when rounded to 3 digits is 0.334 , so we have 0.3335 < x < 0.33345 . Let us look at the continued fraction expansion of these two numbers: 0.3335 = [0; 2, 1, 666] , 0.3345 = [0; 2, 1, 94, 1, 1, 3] . We now want to choose the continued fraction a such that  [0; 2, 1, 666] < a <  [0; 2, 1, 94, 1, 1, 3] , note that the expansion are the same until the 3rd entry, hence we want the 3rd entr

A finite continued fraction  (FCF) is an expression of the form: where  a 0 , a 1 , ..., a n  are real numbers, all of which except possibly  a 0  are positive. Such a fraction is called  simple   if all the  a i  are integers. The expression is denoted as [ a 0 ;  a 1 , . . . , a n ]. Any rational number can be expressed as a FCF. Recall that the reciprocal  of a number is simply obtained by dividing 1 by that number. Consider the fraction 45/16, using reciprocals, this fraction can be written as:  Hence we obtain 45/16 = [2; 1, 4, 3] . Euclid's Algorithm is well known for finding the highest common factor between two integers, where we repeatedly employ division by remainder. The procedure is as follows: given two natural numbers a, b with a > b > 0 , we can write a =  q 1 b + r 1      where b  >r 1  ≥  0  b =  q 2 r 1 + r 2     where  r 1  > r 2  ≥  0  r 1 =  q 3 r 2 + r 3    where  r 2  > r 1  ≥  0 in general  r t  =  q t +2 r t +1  +  r t +2 with  r t +1  >