Welcome guest
You're not logged in.
219 users online, thereof 0 logged in

Motivation: Rational Numbers and the Greatest Common Divisor

Let $\frac{a}b\in\mathbb Q$ be a rational number with $0 < a$ and $0 < b.$ In the proof of the greatest common divisor for the calculation of the greatest common divisor $\gcd(a,b)$, the Euclidean algorithm can be written with a sequence of rational numbers defined as follows:

$$\begin{array}{rclclcl}
\frac{a}{b} & = & q_0 & + & \frac{r_1}{b} & \text{with} & q_0\in\mathbb N,\; 0 < r_1 < b\\
\frac{b}{r_1} & = & q_1 & + & \frac{r_2}{r_1} & \text{with} & q_1\in\mathbb N,\; 0 < r_2 < r_1\\
\frac{r_1}{r_2} & = & q_2 & + & \frac{r_3}{r_2}& \text{with} & q_2\in\mathbb N,\; 0 < r_3 < r_2\\
&\vdots&\\
\frac{r_{n-3}}{r_{n-2}} & = & q_{n-2}& + & \frac{r_{n-1}}{r_{n-2}} & \text{with} & q_{n-2}\in\mathbb N,\; 0 < r_{n-1} < r_{n-2}\\
\frac{r_{n-2}}{r_{n-1}} & = & q_{n-1}& + & \frac{r_{n}}{r_{n-1}} & \text{with} & q_{n-1}\in\mathbb N,\; 0 < r_{n} < r_{n-1}\\
\frac{r_{n-1}}{r_{n}} & = & q_{n} &&& \text{with} & q_{n}\in\mathbb N
\end{array}$$

Therefore, we can put the ratios in each other and get the following representation of the number $\frac ab$:

$$\frac{a}b=q_0+\cfrac{1}{q_1+\cfrac{1}{q_2+\cfrac{1}{\ddots+\cfrac{1}{q_{n-2}+\cfrac{1}{q_{n-1}+\cfrac{1}{q_n}}}}}}$$

Please note that because $r_{n} < r_{n-1}$, we have $q_n > 1$ and thus $q_n\neq 0.$ Thus, this representation is well-defined. It is possible to represent any positive rational number this way. But how about irrational numbers? In order to answer this question, we will introduce a new concept, the concept of continued fractions.

| | | | created: 2019-06-23 21:00:27 | modified: 2019-06-27 17:22:15 | by: bookofproofs | references: [701], [8189]


This work was contributed under CC BY-SA 3.0 by:

This work is a derivative of:

(none)

Bibliography (further reading)

[8189] Kraetzel, E.: “Studienb├╝cherei Zahlentheorie”, VEB Deutscher Verlag der Wissenschaften, 1981

[701] Scheid Harald: “Zahlentheorie”, Spektrum Akademischer Verlag, 2003, 3. Auflage

FeedsAcknowledgmentsTerms of UsePrivacy PolicyImprint
© 2018 Powered by BooOfProofs, All rights reserved.