JP Journal of Algebra, Number Theory and Applications
Volume 6, Issue 2, Pages 361 - 369
(August 2006)
|
|
THE EXTENDED EUCLIDEAN ALGORITHM PROVIDES OPTIMAL BÉšOUT NUMBERS
M. Polezzi (Brazil) and T. P. Da Nó¢²¥ga Neto (Brazil)
|
Abstract: In this note we show that the Extended Euclidean Algorithm provides B麯ut numbers with minimal absolute values, and we obtain, via simple continued fractions, explicit formulas for those optimal B麯ut numbers. As a corollary, we derive an explicit formula for the inverse of a number modulo n. Furthermore, we also show how to obtain the optimal B麯ut numbers geometrically. |
Keywords and phrases: Extended Euclidean Algorithm, continued fractions, inverse of a number modulo n. |
|
Number of Downloads: 398 | Number of Views: 1137 |
|