числом, которое не может быть разложено на простые множители. Мы знаем, что это число не 1, потому что мы исключили такую возможность в формулировке теоремы. Не может оно быть и простым числом, так как тогда бы оно раскладывалось только на себя. Таким образом, это число должно быть составным вида n = а х Ь, где а и Ь меньше, чем n. Но так как n — это наименьшее число, которое не может быть разложено на простые множители, значит, а и b могут быть разложены на простые множители, что дает разложение и для n. Таким образом, мы пришли к противоречию.
Вторая часть доказательства опирается на следующий результат.
Если р — простое число, на которое делится произведение множителей, то на р обязательно должен делиться один из этих множителей. (Этот результат может быть доказан с помощью соотношения Безу.) Предположим, что натуральное число, большее 1, может быть разложено на простые множители двумя способами, тогда мы возьмем простое число р из первого разложения. На это число должно обязательно делиться второе разложение и, следовательно, один из его множителей.
А так как этот множитель — тоже простое число, он должен быть равен р. Таким образом, мы нашли два одинаковых множителя в разных разложениях. Повторяя процесс для любого другого простого числа из первого разложения, мы докажем, что оба разложения содержат одинаковый набор простых множителей.
В терминах теории сравнений, как в пятой главе, теорема формулируется так: «Если р — простое число, то для любого натурального числа а, ар
a (mod р)». Это равносильно тому, что ар — а делится на р.
Докажем теорему с помощью метода индукции. Другими словами, мы предположим, что это верно для некоторого натурального числа а, и затем покажем, что это также верно для числа а + 1.
Начнем с предположения, что ар — а делится на р. Согласно биномиальному разложению Ньютона,
Перенося члены ар и 1 налево, мы получим:
Множитель р содержится во всех слагаемых в правой части, поэтому правая часть уравнения делится на р и, следовательно, левая часть (а + 1)р — ар — 1 тоже делится на р. Так как по индукции ар — а делится на р, то и следующая сумма также делится на р:
Эту сумму можно переписать в виде:
Следовательно, делимость на р верна и в случае а + 1, то есть теорема доказана.
РОССИЯ Издатель, учредитель, редакция: ООО «Де Агостини», Россия Юридический адрес: Россия, 105066, г. Москва, ул. Александра Лукьянова, д. 3, стр. 1 Письма читателей по данному адресу не принимаются. Генеральный директор: Николаос Скилакис Главный редактор: Анастасия Жаркова Старший редактор: Дарья Клинг Финансовый директор: Наталия Василенко Коммерческий директор: Александр Якутов Менеджер по маркетингу: Михаил Ткачук Менеджер по продукту: Яна Чухиль Для заказа пропущенных книг и по всем вопросам, касающимся информации о коллекции, заходите на сайт www.deagostini.ru, по остальным вопросам обращайтесь по телефону бесплатной горячей линии в России: 8-800-200-02-01 Телефон горячей линии для читателей Москвы: 8-495-660-02-02 Адрес для писем читателей: Россия, 170100, г. Тверь, Почтамт, а/я 245, «Де Агостини», «Мир математики» Пожалуйста, указывайте в письмах свои контактные данные для обратной связи (телефон или e-mail). Распространение: ООО «Бурда Дистрибьюшен Сервисиз»
УКРАИНА Издатель и учредитель: ООО «Де Агостини Паблишинг» Украина Юридический адрес: 01032, Украина, г. Киев, ул. Саксаганского, 119 Генеральный директор: Екатерина Клименко Для заказа пропущенных книг и по всем вопросам, касающимся информации о коллекции, заходите на сайт www.deagostini.ua, по остальным вопросам обращайтесь по телефону бесплатной горячей линии в Украине: 0-800-500-8-40 Адрес для писем читателей: Украина, 01033, г. Киев, a/я «Де Агостини», «Мир математики» Украïnа, 01033, м. Киïв, а/с «Де Агостiнi»
БЕЛАРУСЬ Импортер и дистрибьютор в РБ: ООО «Росчерк», 220037, г. Минск, ул. Авангардная, 48а, литер 8/к, тел./факс: +375 17 331 94 27 Телефон «горячей линии» в РБ: + 375 17 279-87-87 (пн-пт, 9.00–21.00) Адрес для писем читателей: Республика Беларусь, 220040, г. Минск, а/я 224, ООО «Росчерк», «Де Агостини», «Мир математики»
КАЗАХСТАН Распространение: ТОО «КГП «Бурда-Алатау Пресс» Издатель оставляет за собой право увеличить рекомендуемую розничную цену книг. Издатель оставляет за собой право изменять последовательность заявленных тем томов издания и их содержание. Отпечатано в соответствии с предоставленными материалами в типографии: Grafica Veneta S.p.A Via Malcanton 2 35010 Trebaseleghe (PD) Italy Подписано в печать: 01.08.2013 Дата поступления в продажу на территории России: 04.02.2014 Формат 70 х 100 / 16. Гарнитура «Academy». Печать офсетная. Бумага офсетная. Печ. л. 4,5. Усл. печ. л. 5,832. Тираж: 200 000 экз. © Enrique Gracian, 2010 (текст) © RBA Collecionables S.A., 2010 © ООО «Де Агостини», 2014 ISBN 978-5-9774-0682-6 ISBN 978-5-9774-0637-6 (т. 3)
2. Доказательство малой теоремы Ферма
В терминах теории сравнений, как в пятой главе, теорема формулируется так: «Если р — простое число, то для любого натурального числа а, ар
Перенося члены ар и 1 налево, мы получим:
Множитель р содержится во всех слагаемых в правой части, поэтому правая часть уравнения делится на р и, следовательно, левая часть (а + 1)р — ар — 1 тоже делится на р. Так как по индукции ар — а делится на р, то и следующая сумма также делится на р:
Эту сумму можно переписать в виде:
Следовательно, делимость на р верна и в случае а + 1, то есть теорема доказана.
Список литературы
Bentley, Р. J., The Book of Numbers, Ontario, Firefly Books, 2008. Hardy, G. H., A Mathematician’s Apology, Cambridge University Press, 1940. Hardy, G. H., Ramanujan, London, Cambridge University Press, 1940. Ifrah, G., The Universal History of Numbers, London, The Harvill Press, 1987. Kanigel, R., The Man who knew Infinity, New York, Washington Square Press, 1991. Kline, M., Mathematical Thought (3 Volumes), USA, Oxford University Press, 1990. Pickover, C. A., Wonders of Numbers, USA, Oxford University Press, 2002. Sautoy, M. du, The Music of the Primes, London, Harper Perennial, 2004. Stewart, I., From Here to Infinity, Oxford Paperbacks, 1996. Szpiro, G., Poincare’s Prize, USA, E. P. Dutton & Co.Inc., 2007. * * * Научно-популярное издание Выходит в свет отдельными томами с 2014 года Мир математики Том 3 Энрике Грасиан Простые числа. Долгая дорога к бесконечностиРОССИЯ Издатель, учредитель, редакция: ООО «Де Агостини», Россия Юридический адрес: Россия, 105066, г. Москва, ул. Александра Лукьянова, д. 3, стр. 1 Письма читателей по данному адресу не принимаются. Генеральный директор: Николаос Скилакис Главный редактор: Анастасия Жаркова Старший редактор: Дарья Клинг Финансовый директор: Наталия Василенко Коммерческий директор: Александр Якутов Менеджер по маркетингу: Михаил Ткачук Менеджер по продукту: Яна Чухиль Для заказа пропущенных книг и по всем вопросам, касающимся информации о коллекции, заходите на сайт www.deagostini.ru, по остальным вопросам обращайтесь по телефону бесплатной горячей линии в России: 8-800-200-02-01 Телефон горячей линии для читателей Москвы: 8-495-660-02-02 Адрес для писем читателей: Россия, 170100, г. Тверь, Почтамт, а/я 245, «Де Агостини», «Мир математики» Пожалуйста, указывайте в письмах свои контактные данные для обратной связи (телефон или e-mail). Распространение: ООО «Бурда Дистрибьюшен Сервисиз»
УКРАИНА Издатель и учредитель: ООО «Де Агостини Паблишинг» Украина Юридический адрес: 01032, Украина, г. Киев, ул. Саксаганского, 119 Генеральный директор: Екатерина Клименко Для заказа пропущенных книг и по всем вопросам, касающимся информации о коллекции, заходите на сайт www.deagostini.ua, по остальным вопросам обращайтесь по телефону бесплатной горячей линии в Украине: 0-800-500-8-40 Адрес для писем читателей: Украина, 01033, г. Киев, a/я «Де Агостини», «Мир математики» Украïnа, 01033, м. Киïв, а/с «Де Агостiнi»
БЕЛАРУСЬ Импортер и дистрибьютор в РБ: ООО «Росчерк», 220037, г. Минск, ул. Авангардная, 48а, литер 8/к, тел./факс: +375 17 331 94 27 Телефон «горячей линии» в РБ: + 375 17 279-87-87 (пн-пт, 9.00–21.00) Адрес для писем читателей: Республика Беларусь, 220040, г. Минск, а/я 224, ООО «Росчерк», «Де Агостини», «Мир математики»
КАЗАХСТАН Распространение: ТОО «КГП «Бурда-Алатау Пресс» Издатель оставляет за собой право увеличить рекомендуемую розничную цену книг. Издатель оставляет за собой право изменять последовательность заявленных тем томов издания и их содержание. Отпечатано в соответствии с предоставленными материалами в типографии: Grafica Veneta S.p.A Via Malcanton 2 35010 Trebaseleghe (PD) Italy Подписано в печать: 01.08.2013 Дата поступления в продажу на территории России: 04.02.2014 Формат 70 х 100 / 16. Гарнитура «Academy». Печать офсетная. Бумага офсетная. Печ. л. 4,5. Усл. печ. л. 5,832. Тираж: 200 000 экз. © Enrique Gracian, 2010 (текст) © RBA Collecionables S.A., 2010 © ООО «Де Агостини», 2014 ISBN 978-5-9774-0682-6 ISBN 978-5-9774-0637-6 (т. 3)