Electronic Proceedings of the Sixteenth Annual International Conference on Technology in Collegiate Mathematics

Chicago, Illinois, October 30-November 2, 2003

Paper S047

This is an electronic reprint, reproduced by permission of Pearson Education Inc. Originally appeared in the Proceedings of the Sixteenth Annual International Conference on Technology in Collegiate Mathematics, Edited by Corinna Mansfield, ISBN 0-321-30456-x, Copyright (C) 2005 by Addison-Wesley Publishing Company, Inc.


Exploring Euclid's Algorithm for Fun and Profit

Edmund A. Lamagna


Department of Computer Science
University of Rhode Island
Kingston, RI 02881
USA


list of all papers by this author

Click to access this paper: paper.pdf

ABSTRACT

Euclid's algorithm for greatest common divisor is perhaps the oldest nontrivial algorithm still in use. Polynomial GCD computation is at the heart of every computer algebra system. We consider how the Euclidean algorithm for polynomials can be implemented efficiently and present some surprising applications to polynomial factorization, simplification of expressions involving radicals, and rational function integration.

Keyword(s): number theory, computer algebra systems, calculus