Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



It is easy to determine whether a given integer is prime

Author: Andrew Granville
Journal: Bull. Amer. Math. Soc. 42 (2005), 3-38
MSC (2000): Primary 11A51, 11Y11; Secondary 11A07, 11A41, 11B50, 11N25, 11T06
Published electronically: September 30, 2004
MathSciNet review: 2115065
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: “The problem of distinguishing prime numbers from composite numbers, and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length. Nevertheless we must confess that all methods that have been proposed thus far are either restricted to very special cases or are so laborious and difficult that even for numbers that do not exceed the limits of tables constructed by estimable men, they try the patience of even the practiced calculator. And these methods do not apply at all to larger numbers ... It frequently happens that the trained calculator will be sufficiently rewarded by reducing large numbers to their factors so that it will compensate for the time spent. Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated ... It is in the nature of the problem that any method will become more complicated as the numbers get larger. Nevertheless, in the following methods the difficulties increase rather slowly ... The techniques that were previously known would require intolerable labor even for the most indefatigable calculator.” —from article 329 of Disquisitiones Arithmeticae (1801) by C. F. Gauss

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 11A51, 11Y11, 11A07, 11A41, 11B50, 11N25, 11T06

Retrieve articles in all journals with MSC (2000): 11A51, 11Y11, 11A07, 11A41, 11B50, 11N25, 11T06

Additional Information

Andrew Granville
Affiliation: Département de Mathématiques et Statistique, Université de Montréal, CP 6128 succ. Centre-Ville, Montréal, QC H3C 3J7, Canada
MR Author ID: 76180
ORCID: 0000-0001-8088-1247

Received by editor(s): January 27, 2004
Received by editor(s) in revised form: August 19, 2004
Published electronically: September 30, 2004
Additional Notes: L’auteur est partiellement soutenu par une bourse du Conseil de recherches en sciences naturelles et en génie du Canada.
Dedicated: Dedicated to the memory of W. ‘Red’ Alford, friend and colleague
Article copyright: © Copyright 2004 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.