Extended Euclidean Algorithm and CRT Algorithm

Hiroyuki Okazaki; Yosiki Aoki; Yasunari Shidama

Formalized Mathematics (2012)

  • Volume: 20, Issue: 2, page 175-179
  • ISSN: 1426-2630

Abstract

top
In this article we formalize some number theoretical algorithms, Euclidean Algorithm and Extended Euclidean Algorithm [9]. Besides the a gcd b, Extended Euclidean Algorithm can calculate a pair of two integers (x, y) that holds ax + by = a gcd b. In addition, we formalize an algorithm that can compute a solution of the Chinese remainder theorem by using Extended Euclidean Algorithm. Our aim is to support the implementation of number theoretic tools. Our formalization of those algorithms is based on the source code of the NZMATH, a number theory oriented calculation system developed by Tokyo Metropolitan University [8].

How to cite

top

Hiroyuki Okazaki, Yosiki Aoki, and Yasunari Shidama. "Extended Euclidean Algorithm and CRT Algorithm." Formalized Mathematics 20.2 (2012): 175-179. <http://eudml.org/doc/268049>.

@article{HiroyukiOkazaki2012,
abstract = {In this article we formalize some number theoretical algorithms, Euclidean Algorithm and Extended Euclidean Algorithm [9]. Besides the a gcd b, Extended Euclidean Algorithm can calculate a pair of two integers (x, y) that holds ax + by = a gcd b. In addition, we formalize an algorithm that can compute a solution of the Chinese remainder theorem by using Extended Euclidean Algorithm. Our aim is to support the implementation of number theoretic tools. Our formalization of those algorithms is based on the source code of the NZMATH, a number theory oriented calculation system developed by Tokyo Metropolitan University [8].},
author = {Hiroyuki Okazaki, Yosiki Aoki, Yasunari Shidama},
journal = {Formalized Mathematics},
language = {eng},
number = {2},
pages = {175-179},
title = {Extended Euclidean Algorithm and CRT Algorithm},
url = {http://eudml.org/doc/268049},
volume = {20},
year = {2012},
}

TY - JOUR
AU - Hiroyuki Okazaki
AU - Yosiki Aoki
AU - Yasunari Shidama
TI - Extended Euclidean Algorithm and CRT Algorithm
JO - Formalized Mathematics
PY - 2012
VL - 20
IS - 2
SP - 175
EP - 179
AB - In this article we formalize some number theoretical algorithms, Euclidean Algorithm and Extended Euclidean Algorithm [9]. Besides the a gcd b, Extended Euclidean Algorithm can calculate a pair of two integers (x, y) that holds ax + by = a gcd b. In addition, we formalize an algorithm that can compute a solution of the Chinese remainder theorem by using Extended Euclidean Algorithm. Our aim is to support the implementation of number theoretic tools. Our formalization of those algorithms is based on the source code of the NZMATH, a number theory oriented calculation system developed by Tokyo Metropolitan University [8].
LA - eng
UR - http://eudml.org/doc/268049
ER -

References

top
  1. [1] Grzegorz Bancerek. The fundamental properties of natural numbers. Formalized Mathematics, 1(1):41-46, 1990. Zbl06213858
  2. [2] Grzegorz Bancerek. The ordinal numbers. Formalized Mathematics, 1(1):91-96, 1990. 
  3. [3] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Formalized Mathematics, 1(1):107-114, 1990. 
  4. [4] Czesław Bylinski. Functions and their basic properties. Formalized Mathematics, 1(1):55-65, 1990. 
  5. [5] Czesław Bylinski. Functions from a set to a set. Formalized Mathematics, 1(1):153-164, 1990. 
  6. [6] Czesław Bylinski. Some basic properties of sets. Formalized Mathematics, 1(1):47-53, 1990. 
  7. [7] Czesław Bylinski. The sum and product of finite sequences of real numbers. FormalizedMathematics, 1(4):661-668, 1990. 
  8. [8] NZMATH development Group. http://tnt.math.se.tmu.ac.jp/nzmath/. 
  9. [9] Donald E. Knuth. Art of Computer Programming. Volume 2: Seminumerical Algorithms, 3rd Edition, Addison-Wesley Professional, 1997. Zbl0895.68055
  10. [10] Rafał Kwiatek and Grzegorz Zwara. The divisibility of integers and integer relative primes. Formalized Mathematics, 1(5):829-832, 1990. 
  11. [11] Andrzej Trybulec. Tuples, projections and Cartesian products. Formalized Mathematics, 1(1):97-105, 1990. 
  12. [12] Michał J. Trybulec. Integers. Formalized Mathematics, 1(3):501-505, 1990. 
  13. [13] Zinaida Trybulec. Properties of subsets. Formalized Mathematics, 1(1):67-71, 1990. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.