## The Mastery of Computer Programming: Primary Algorithms - Sykalo Eugene 2023

# Algebraic and transcendental numbers

The Mathematical Background

## Algebraic Numbers

Algebraic numbers are a type of number that can be expressed as the root of a polynomial equation with rational coefficients. This means that there exists a polynomial equation with rational coefficients such that the algebraic number is a root of the equation. For example, the square root of 2 is an algebraic number because it is a root of the polynomial equation x^2 - 2 = 0.

One important property of algebraic numbers is that they are countable, which means that they can be placed in a one-to-one correspondence with the natural numbers. This is in contrast to transcendental numbers, which are uncountable.

There are many algorithms for computing algebraic numbers and their properties. One such algorithm is the Newton-Raphson method, which can be used to approximate the roots of a polynomial equation. Another algorithm is the Berlekamp-Zassenhaus algorithm, which can be used to factor polynomials over a finite field.

The study of algebraic numbers has many applications in computer programming and other fields of mathematics. For example, algebraic numbers can be used to represent solutions to Diophantine equations, which are equations that involve only integer variables. Algebraic numbers also have applications in cryptography, where they are used to generate secure encryption keys.

## Transcendental Numbers

Transcendental numbers are a type of number that cannot be expressed as the root of any polynomial equation with rational coefficients. The most famous transcendental number is pi (π), which is the ratio of a circle's circumference to its diameter. Other examples of transcendental numbers include e (the base of the natural logarithm) and the Euler-Mascheroni constant.

Unlike algebraic numbers, transcendental numbers are uncountable, which means that there are too many of them to be placed in a one-to-one correspondence with the natural numbers. This leads to interesting properties, such as the fact that almost all real numbers are transcendental.

Transcendental numbers have many applications in mathematics and computer programming. For example, they are used in the study of chaos theory and fractals, where they can be used to generate complex and intricate patterns. Transcendental numbers also have applications in physics, where they are used to describe natural phenomena such as the behavior of waves and the distribution of energy levels in atoms.

Despite their importance, computing transcendental numbers can be challenging. One common method for approximating transcendental numbers is to use continued fractions, which are a type of fraction that involves an infinite sequence of integers. Continued fractions can be used to approximate irrational numbers with a high degree of accuracy, making them a powerful tool for solving mathematical problems.

## Continued Fractions

Continued fractions are a generalization of ordinary fractions that involve an infinite sequence of integers. They are a powerful tool for approximating algebraic and transcendental numbers and have applications in many areas of mathematics, including number theory and analysis.

A continued fraction can be expressed in the form:

```
a_0 + 1/(a_1 + 1/(a_2 + 1/(a_3 + ...)))
```

where each `a_i`

is a positive integer. The `a_i`

are often called the partial quotients of the continued fraction.

To compute the value of a continued fraction, we can truncate the infinite sequence at some point and evaluate the resulting finite fraction. The more terms we include in the sequence, the more accurate our approximation will be.

Continued fractions have many useful properties. For example, they can be used to find rational approximations of irrational numbers. Specifically, if `x`

is an irrational number, then there exist infinitely many rational numbers `p/q`

such that:

```
|x - p/q| < 1/(q^2)
```

Furthermore, the sequence of convergents of a continued fraction approximates the value of the continued fraction itself. The `n`

th convergent of a continued fraction is the finite continued fraction obtained by truncating the sequence after the `n`

th term. The error between the value of the continued fraction and its `n`

th convergent is bounded by:

```
|a - p_n/q_n| < 1/(q_n * q_{n+1})
```

where `a`

is the value of the continued fraction and `p_n/q_n`

is the `n`

th convergent.

Continued fractions can be used to compute both algebraic and transcendental numbers. For example, the continued fraction expansion of the square root of 2 is:

```
[1;2,2,2,2,...]
```

which means that the square root of 2 can be approximated by the sequence of convergents:

```
1, 3/2, 7/5, 17/12, 41/29, ...
```

Similarly, the continued fraction expansion of pi is:

```
[3;7,15,1,292,1,1,1,2,1,3,1,...]
```

which means that pi can be approximated by the sequence of convergents:

```
3, 22/7, 333/106, 355/113, 103993/33102, ...
```

Continued fractions are a powerful tool for approximating irrational numbers and can be used to solve many mathematical problems.

## Diophantine Equations

Diophantine equations are equations that involve only integer variables. They are named after the ancient Greek mathematician Diophantus, who studied these types of equations extensively. Diophantine equations have many applications in number theory, cryptography, and computer science.

One famous example of a Diophantine equation is Fermat's Last Theorem, which states that there are no integer solutions to the equation x^n + y^n = z^n for n > 2. This theorem was famously proved by Andrew Wiles in 1994, using a combination of techniques from algebraic geometry and number theory.

There are many algorithms for solving Diophantine equations. One common approach is to use the Euclidean algorithm to find the greatest common divisor of two integers. This can be used to find integer solutions to linear Diophantine equations of the form ax + by = c.

Another approach is to use modular arithmetic to analyze the solutions to a Diophantine equation. This involves looking at the equation modulo some integer, and using the properties of modular arithmetic to derive information about the solutions. For example, the Chinese Remainder Theorem states that if we have a system of linear congruences of the form x = a_i (mod m_i), then there exists a unique solution modulo M, where M is the product of the m_i.

More advanced algorithms for solving Diophantine equations involve techniques from algebraic geometry and number theory. For example, the LLL algorithm can be used to find small solutions to systems of linear equations, and the Sieve of Eratosthenes can be used to find solutions to certain types of Diophantine equations.

Diophantine equations have many applications in computer programming and other fields. For example, they can be used to generate pseudorandom numbers for encryption and secure communication. They are also used in the design of cryptographic protocols, where they are used to ensure that certain computations can be performed securely without revealing any sensitive information.

## Euclidean Algorithm

The Euclidean algorithm is a fundamental algorithm for finding the greatest common divisor (GCD) of two integers. The GCD of two integers `a`

and `b`

is the largest integer that divides both `a`

and `b`

without leaving a remainder. For example, the GCD of 12 and 18 is 6, because 6 is the largest integer that divides both 12 and 18 without leaving a remainder.

The Euclidean algorithm works by repeatedly finding the remainder when one integer is divided by the other, and then using the smaller integer as the new divisor. Specifically, if we want to find the GCD of `a`

and `b`

, we can perform the following steps:

- Let
`r_0 = a`

and`r_1 = b`

. - Divide
`r_0`

by`r_1`

to obtain a quotient`q_1`

and a remainder`r_2`

. - If
`r_2`

is zero, then`r_1`

is the GCD of`a`

and`b`

. Otherwise, set`r_0 = r_1`

and`r_1 = r_2`

, and go back to step 2.

For example, suppose we want to find the GCD of 12 and 18. We can perform the following steps:

```
r_0 = 12, r_1 = 18
r_0 / r_1 = 0 with remainder 12
r_1 / 12 = 1 with remainder 6
12 / 6 = 2 with remainder 0
Therefore, the GCD of 12 and 18 is 6.
```

The Euclidean algorithm is very efficient and can be used to find the GCD of very large integers. It also has many applications in computer programming and other fields. For example, the Euclidean algorithm can be used to simplify fractions, compute modular inverses, and solve certain types of Diophantine equations.

One variant of the Euclidean algorithm is the extended Euclidean algorithm, which can be used to find the coefficients of the Bezout's identity. Bezout's identity states that for any two integers `a`

and `b`

, there exist integers `x`

and `y`

such that `ax + by = gcd(a, b)`

. The extended Euclidean algorithm can be used to find these integers `x`

and `y`

.

The extended Euclidean algorithm works by repeatedly applying the Euclidean algorithm and keeping track of the remainders and quotients. Specifically, if we want to find the coefficients of the Bezout's identity for `a`

and `b`

, we can perform the following steps:

- Let
`r_0 = a`

,`r_1 = b`

,`s_0 = 1`

, and`s_1 = 0`

. - Divide
`r_0`

by`r_1`

to obtain a quotient`q_1`

and a remainder`r_2`

. - If
`r_2`

is zero, then`s_1`

and`t_1`

are the coefficients of the Bezout's identity for`a`

and`b`

. Otherwise, set`r_0 = r_1`

,`r_1 = r_2`

,`s_0 = s_1`

, and`s_1 = s_0 - q_1 * s_1`

, and go back to step 2.

For example, suppose we want to find the coefficients of the Bezout's identity for 12 and 18. We can perform the following steps:

```
r_0 = 12, r_1 = 18, s_0 = 1, s_1 = 0
r_0 / r_1 = 0 with remainder 12
r_1 / 12 = 1 with remainder 6
12 / 6 = 2 with remainder 0
Therefore, the GCD of 12 and 18 is 6, and the coefficients of the Bezout's identity are s_1 = -1 and t_1 = 1.
```

The extended Euclidean algorithm is also very efficient and can be used to find the coefficients of the Bezout's identity for very large integers. It has many applications in cryptography, where it is used to compute modular inverses and generate secure encryption keys.

## Fourier Analysis

Fourier analysis is a powerful tool for understanding the behavior of functions. It is named after the French mathematician Joseph Fourier, who first introduced the concept in the early 19th century.

The basic idea behind Fourier analysis is that any periodic function can be expressed as a sum of simple sine and cosine functions. Specifically, if `f(x)`

is a periodic function with period `T`

, then it can be expressed as:

```
f(x) = a_0/2 + sum_{n=1}^infinity [a_n cos(n omega x) + b_n sin(n omega x)]
```

where `a_0`

, `a_n`

, and `b_n`

are constants that depend on the function `f`

, and `omega = 2 pi / T`

is the angular frequency of the function. The terms `a_0/2`

, `a_n cos(n omega x)`

, and `b_n sin(n omega x)`

are called the Fourier coefficients of `f`

.

The Fourier coefficients can be computed using a technique called Fourier series, which involves integrating `f(x)`

with respect to `x`

over one period of the function. This yields the values of the constants `a_0`

, `a_n`

, and `b_n`

, which can then be used to express `f(x)`

in terms of its Fourier series.

Fourier analysis has many applications in mathematics and computer programming. For example, it is used in signal processing, where it can be used to analyze and filter signals. It is also used in image processing, where it can be used to analyze and compress images.

In addition to Fourier series, there are many other techniques for analyzing functions using Fourier analysis. One such technique is Fourier transforms, which involve expressing a function as a sum of complex exponential functions rather than sine and cosine functions. Fourier transforms have many applications in physics, where they are used to study the behavior of waves and the distribution of energy levels in atoms.