Исторические замечания и литература

1. Наше представление теории множеств «наивно», потому что мы предполагаем, что любое внушающее доверие описание определяет множество. В начале нашего столетия Бертран Рассел удивил логиков и математиков, выведя несколько логических противоречий в наивной теории множеств. Рассмотрим множество , т.е. множество, содержащее все множества, которые не содержат себя в качестве элемента. Для наших целей не важно знать, существует ли множество, которое содержит себя в качестве элемента, нас заботит, что у может быть множеством всех множеств. Возникает вопрос, верно ли, что ? Если , то по определению у. С другой стороны, если , то . Оба случая, как так и ведут к противоречию. Это — один из парадоксов Рассела, и он аналогичен парадоксу цирюльника: в деревне живет цирюльник, который бреет только тех мужчин, которые не бреются сами. Кто бреет цирюльника? Бреет себя цирюльник или не бреет, оба случая ведут к противоречию. Усилия развить состоятельную теорию множеств привели математиков к построению аксиоматической

теории множеств, которая указывает точные способы, как может быть построено множество. Однако если не забираться слишком глубоко и использовать теорию множеств преимущественно как инструмент, то годится наивная теория множеств.

2. Леонардо Пизанский, широко известный как Фибоначчи, был одинокой звездой первой величины на темном математическом небосклоне средневековья. Он жил около 1200 г., много путешествовал по Аравии и с помощью своей «Книги абака» принес в Европу индо-арабскую числовую систему и другие достижения Востока.

3. Интересно отметить, что в 1896 г., почти через сто лет после того, как были сформулированы гипотезы Гаусса и Лежандра, Адамар и Валле Пуссен доказали «теорему о простых числах», пользуясь «аналитическими» методами, т.е. математическими средствами, не относящимися к области целых чисел. Первое доказательство без использования таких средств было получено в 1949 г. (Эрдёш).

4. Пьер Ферма сформулировал свою «малую теорему» в письме к другу Френиклу де Бесси 18 октября 1640 г. Модулярная арифметика была изобретена и сформулирована Карлом Фридрихом Г ауссом.

5. Кармайкловы числа были названы по имени американского математика Кармайкла (R.D. Carmichael), исследовавшего их свойства в 1909 г.

6. В литературе греко-китайская теорема об остатках называется просто «китайской теоремой об остатках» и приписывается Сунь-Цзы, жившему в первом веке нашей эры. В своей книге «Суань Цзинь» («Математический трактат») Сунь-Цзы дает правило «тья-тен» (большое обобщение) определения натурального числа, дающего остатки 2, 3, 2 при делении на 3, 5, 7 соответственно. Однако греческий математик Никомах из Герасы, также живший в первом веке нашей эры, упоминает подобную задачу в своей книге «Введение в арифметику», а именно он вводит как игру метод для определения натурального числа по остаткам, полученным от деления этого числа на другие натуральные числа (Nicomachi Geraseni Pythagorei Introductionis Arithmeticae, Libri II, Lipsiae, 1866). Эти методы сходны, и мы отдаем должное обоим. (Следует также отметить, что Никомах был пифагорийским философом и что решето Эратосфена описано в его книге.)

Абрамов С.А. Некоторые оценки, связанные с алгоритмом Евклида, Журнал выч. мат. и мат. физ. 19, 756-760, 1979.

Абрамов С.А., Рыбин С.И. Обобщение бинарного алгоритма вычисления наибольшего общего делителя целых чисел. В кн. Вопросы математической логики и теории алгоритмов, 34-37, ВИ АН СССР, Москва, 1988.

Adleman L.M., Pomerance С., Rumely R.S. On distinguishing prime numbers from composite numbers, Annals of Mathematics 117, 173-206, 1983.

Bradley G.H. Algorithm and bound for the greatest common divisor of n integers, Communications of the ACM 13, 433-436, 1970.

Childs L. A concrete introduction to higher algebra. Springer-Verlag, New York, 1979.

Cohen H., Lenstra H.W. Jr. Primality testing and Jacobi sums. Report 82-18, Mathematical Institut of the University of Amsterdam, Amsterdam, 1982.

Dickson L.E. History of the theory of numbers. Chelsea, New York, 1952.

Dirichlet P.G.L. Abhandlungen der koeniglichen preussischen Akademie der Wissenschaften, 1849, 69-83.

Dixon J.D. Asymptotically fast factorization of integers. Mathematics of Computation 36, 255-260, 1981.

Dixon J.D. Factorization and primality tests. American Mathematical Monthly 91, 333-352, 1984.

Dudley U. Formulas for primes. Mathematics Magazine 56, 17-22, 1983.

Erdoes P. On a new method in elementary number theory which leads to an elementary proof of the prime number theorem. Proceedings of the National Academy of Sciences (USA) 35, 374-384, 1949.

Goldstein L.J. A history of the prime number theorem. American Mathematical Monthly 80, 599-614, 1973.

Gregory R.T., Krishnamurthy E.V. Methods and Applications of Error-free Computation. Springer-Verlag, New York, 1984. [Имеется перевод: Грегори P., Кришнамурти E. Безошибочные вычисления. Методы и приложения. — М.: Мир, 1988.]

Guy R.K. How to factor a number. Congressus Numerantium XVI, Proceedings of the Fifth Manitoba Conference on Numerical Mathematics (Winnipeg, 1976) pp. 49-89.

Knuth D. The art of computer programming. Vol. 2. Seminumerical algorithms. Addison-Wesley, Reading, MA, 1969. [Имеется перевод:

Кнут Л. Искусство программирования для ЭВМ. Т. 2. — М.: Мир, 1977.]

Lagrange J.L. Traite de la resolution des equations numeriques. Paris, 1798.

Lame Gabriel. Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers. Comptes Rendues de I’Acadimie des Sciences (Paris) 19, 867-870, 1844.

Lang S., Ttotter H. Continued fractions for some algebraic numbers. Journal fuer die reine und angewandte Mathematik 255, 112-134, 1972.

Legendre A.M. Theorie des nombres. Paris, 1798.

Lehman R.S. Factoring large integers. Mathematics of Computation 28, 637-646, 1974.

LeVeque W.J. Fundamentals of number theory. Addison-Wesley, Reading, MA, 1977.

Levinson N. A motivated account of an elementary proof of the prime number theorem. American Mathematical Monthly 76, 225-245, 1969.

Lipson J.D. Elements of algebra and algebraic computing. Addison-Wesley, Reading, MA, 1981.

Lucas E. Theorie des nombres. Blanchard, Paris, 1961.

Mills W.H. A prime representing function. Bulletin of the American Mathematical Society 53, 604, 1947.

Morrison M.A., Brillhart J. A method of factoring and the factorization ofF7. Mathematics of Computaion 29, 183-205, 1975.

Motzkin T.S. The Euclidean algorithm. Bulletin of the American Mathematical Society 55, 1142-1146, 1949.

Niven I., Zuckerman H.S. An introduction to the theory of numbers, 4th ed. Wiley, New York, 1980.

Olds C.D. Continued fractions. Random House, New York, 1963.

Pomerance C. Recent developments in primality testing. The Mathematics Intelligencer 3, 97-105, 1981.

Pratt V.R. Every prime has a succinct certificate. SIAM Journal of Computing 4, 214-220, 1975.

Rabin M.O. Probabilistic algorithm for testing primality. Journal of Number Theory 12, 128-138, 1980.

Richards I. Continued fractions without tears. Mathematics Magazine 54, 163-171, 1981.

Schroeder M.R. Number theory in science and communication. Springer-Verlag, New York, 1984 and 1986 (2nd ed.)

Scott N.R. Computer number systems and arithmetic. Prentice-Hall, Englewood Cliffs, N.J., 1985.

Sims C.C. Abstract algebra, a computational approach. Wiley, New York, 1984.

Solovay R., Strassen V. A fast Monte Carlo test for primality. SIAM Journal of Computing 6, 1977, 84-85; erratum ibid., 7, 118, 1978.

Wilf H.S. Algorithms and complexity. Prentice-Hall, Englewood Cliffs, N.J., 1986.

Williams H.C. Primality testing on a computer. An Combmatoria 5, 127-185, 1978.

Williams H.C. The influence of computers in the development of number theory. Computers and Mathematics with Applications 8, 75-93, 1982.

Williams H.C. Factoring on a computer. The Mathematics Intelligencer 6, 29-36, 1984.

Wunderlich M. A running time analysis of Brillhart’s continued fraction factoring method. Number theory Cardondale 1979, Lecture notes in Mathematics no. 751. Springer-Verlag, Berlin, 1979, pp. 328-342.