|
|
Pell's equation, continued fractions and Diophantine approximations of irrational numbers
Kodýtek, Jakub ; Beran, Filip (advisor) ; Jančařík, Antonín (referee)
This bachelor's thesis deals with Pell's equation, while clearly presenting structured information from studied domestic and foreign books, articles, and other sources. The goal of this thesis is to create study material primarily for university students but also for inquisitive high school students, and thus explain as intuitively as possible what Pell's equation is, how to find its solutions, and how it is related, for example, to continued fractions, approximations of irrational numbers, and invertible elements in Z[√n ]. The main motivation for solving Pell's equation throughout the work is specifically that its solutions give best approximations of irrational square roots. Pell's equation is presented in a brief historical context. Further, it is proved that there is a non-trivial integer solution for every Pell equation, and the theory of continued fractions is used to find it. To make the creation of continued fractions easier, the so-called Tenner's algorithm is introduced. Specifically, the search for a solution to Pell's equation is derived using convergents and the periodicity of continued fractions of irrational roots. Subsequently, the structure of the solution is described: it is proved that there is a so-called minimal solution that generates all positive solutions, and a set of...
|
|
|
Linear Diophantine equations and congruences
Kaňáková, Natálie ; Beran, Filip (advisor) ; Jančařík, Antonín (referee)
This bachelor's thesis summarizes and systematizes knowledge about congruences and linear Diophantine equations. This work is divided into two parts. The first part is dedicated to congruences. At first, it shows where we can find congruences in real life, congruence as a relation, its properties, and applications in calculating the last ciphers of large numbers, proofs of divisibility rules, or calculating the date of Easter. Afterward, we look into congruences containing unknowns - linear congruence equations. It looks into methods of solving linear congruences and illustrates them in exercises. The last topic of the first part is oriented on systems of linear congruences and the Chinese remainder theorem, both for non-coprime and coprime moduli, the algebraic version, applications in various types of problems, and modular representation of numbers. The second part of this thesis is dedicated to linear Diophantine equations - equations with integer solutions. It shows various methods of solving linear Diophantine equations with two, three, or more unknowns - the extended Euclidean algorithm, reduction method, substitution method, and others. This part also describes the relationship between linear congruences and linear Diophantine equations and the use of this relationship in solving both linear...
|
|
| |
|
|
Simulation of the enciphering algorithm RSA in MATLAB
Čížek, Václav ; Švandová, Hana
Enciphering algorithm RSA is up to now hold for one almost not decipherable methods of enciphering. At present it is used also for the electronic signature. The algorithm is based on elementary knowledge in number theory like congruence, Euler function and modular inversion. Because some number theoretic operations mey be processed in MATLAB it is shown, how the RSA algorithm can be simulated in MATLAB. Results and some simulation difficulties of the RSA algorithm are presented.
|
guest ::
