О. ОРЕ - Приглашение в теорию чисел
- Название:Приглашение в теорию чисел
- Автор:
- Жанр:
- Издательство:Наука Главная редакция физико-математической литературы
- Год:1980
- Город:Москва
- ISBN:нет данных
- Рейтинг:
- Избранное:Добавить в избранное
-
Отзывы:
-
Ваша оценка:
О. ОРЕ - Приглашение в теорию чисел краткое содержание
Книга известного норвежского математика О. Оре раскрывает красоту математики на примере одного из ее старейших разделов — теории чисел. Изложение основ теории чисел в книге во многом нетрадиционно. Наряду с теорией сравнении, сведениями о системах счисления, в ней содержатся рассказы о магических квадратах, о решении арифметических ребусов и т. д. Большим достоинством книги является то, что автор при каждом удобном случае указывает на возможности практического применения изложенных результатов, а также знакомит читателя с современным состоянием теории чисел и задачами, ещё не получившими окончательного решения.
Приглашение в теорию чисел - читать онлайн бесплатно полную версию (весь текст целиком)
Интервал:
Закладка:
Здесь первый и последний коэффициенты равны единице. Средними биномиальными коэффициентами являются
C p 1= p /1, С р 2= p ( p -1)/(1 2), С р 3= p ( p -1)( p -2)/(1 • 2 • 3)… (7.5.3)
и вообще
С р r = p ( p -1)( p -2)… ( p — r + 1)/(1 2… r ), (7.5.4)
Так как эти коэффициенты получаются в результате последовательного умножения на бином ( х + у ), то ясно, что они являются целыми числами.
С этого момента будем считать, что р — простое число. Чтобы записать эти коэффициенты в целочисленном виде, необходимо сократить все общие множители знаменателя
1 • 2 • 3 •… • r
и числителя
p ( p -1)( p -2)… ( p — r + 1)
Однако знаменатель не содержит простого множителя р , поэтому после сокращения число р останется множителем в числителе. Мы делаем вывод.
Все биномиальные коэффициенты (кроме первого и последнего) в выражении (7.5.2) делятся на р, если р — простое число.
Пусть теперь х и у в выражении (7.5.2) будут целыми числами. Если мы рассмотрим формулу (7.5.2) как сравнение по модулю р , то можно сделать вывод, что для любых целых чисел х и у и простого р
( х + у ) p ≡ х р + у р (mod p ). (7.5.5)
В качестве примера возьмем р = 5:
( х + у ) 5= х 5+ 5 х 4 у + 10 x 3 y 2+ 10 x 2 y 3+ 5 xy 4+ у 5.
Так как все средние коэффициенты делятся на 5, то
( х + у ) 5≡ х 5+ у 5(mod 5)
в соответствии с (7.5.5).
Из сравнения (7.5.5) можно сделать важные выводы. Применим его для случая х = у = 1. Получаем
2 p = (1 + 1) p ≡ 1 p + 1 p = 2 (mod p ).
Возьмем затем х = 2, у = 1 и найдем, что
3 p = (2 + 1) p ≡ 2 p + 1 p ;
теперь, используя предыдущий результат, 2 p ≡ 2 (mod p ), получаем
2 p + 1 p ≡ 2 + 1 ≡ (mod p ).
Итак, 3 p ≡ 3 (mod p ). Далее для х = 3, у = 1 получаем
4 p ≡ 4 (mod p ).
Используя этот процесс, можно доказать по индукции, что а p ≡ a (mod p ) для всех значений числа
а = 0, 1…. р -1. (7.5.6)
Случаи a = 0 и а = 1 очевидны. Так как каждое число сравнимо (mod р ) с одним из остатков, записанных в (7.5.6), мы делаем вывод:
для любого целого числа а и любого простого числа р
a p ≡ a (mod p ). (7.5.7)
Это утверждение обычно называют теоремой Ферма , хотя некоторые авторы называют ее малой теоремой Ферма , чтобы отличить от последней теоремы Ферма, или гипотезы Ферма, о которой мы упоминали в § 3 главы 5.
Пример. Для р = 13 и а = 2 мы находим: 13 = 8+ 4 + 1, т. е. 2 13= 2 8+4+1= 2 8 2 4 • 2 1. Так как 2 4= 16 ≡ 3 (mod 13), 2 8≡ 9(mod 13), то
2 13= 2 8• 2 4• 2 ≡ 9 • 3 • 2 ≡ 2 (mod 13),
как и утверждает теорема Ферма.
В соответствии с правилом сокращения для сравнений, сформулированном в конце § 3, мы можем сократить общий множитель а в обеих частях записи теоремы Ферма (7.5.7) при условии, что число а взаимно просто с числом р , являющимся модулем сравнения. Это дает следующий результат:
если а является целым числом, не делящимся на простое число р, то
a p -1 ≡ 1 (mod p ). (7.5.8)
Этот результат также называют теоремой Ферма.
Пример. Когда а = 7, р = 19, мы находим, что
7 2= 49 ≡ 11 (mod 19)
7 4≡ 121 ≡ 7 (mod 19),
7 8≡ 49 ≡ 11 (mod 19),
7 16≡ 121 ≡ 7 (mod 19),
и это дает
a p -1= 7 18= 7 16 • 7 2≡ 7 • 11 ≡ 1 (mod 19),
что соответствует утверждению (7.5.8).
В качестве приложения теоремы Ферма вновь рассмотрим треугольники Пифагора, обсужденные в гл. 5 и докажем следующее утверждение:
произведение длин сторон треугольника Пифагора делится на 60.
Доказательство. Очевидно, достаточно доказать это для простейших треугольников. В соответствии с формулой (5.2.7), это произведение есть
Р = 2 mn ( m 2— n 2) ( m 2+ n 2) = 2 mn ( m 4— n 4).
Число Р делится на 60 тогда и только тогда, когда оно делится на 4, на 3 и на 5. Так как одно из чисел m и n четно, то 2 mn , а следовательно, и число Р , делится на 4. Оно делится на 3, если хотя бы одно из чисел m или n делится на 3, но если ни одно из них не делится на 3, то Р все же будет делиться на 3, так как из условий (7.5.8), а также D ( m , 3) = 1 и D ( n , 3) = 1 следует, что m 2 ≡ 1 (mod 3) и n 2 ≡ 1 (mod 3), так что
m 2— n 2≡ 1 – 1 = 0 (mod 3).
Аналогично, число Р делится на 5. Это очевидно, если m или n делится на 5. Если ни одно из них не делится на 5, то вновь по теореме Ферма (7.5.8) получаем
m 4— n 4≡ 1 – 1 = 0 (mod 5).
ГЛАВА 8
НЕКОТОРЫЕ ПРИМЕНЕНИЯ СРАВНЕНИЙ
§ 1. Проверка вычислений
Как мы уже упоминали, создателем теории сравнений был немецкий математик Карл Фридрих Гаусс. Его знаменитая работа по теории чисел «Арифметические исследования» появилась в 1801 году, когда ему было 24 года. В первых главах этой книги рассказывается о теории сравнений. Однако здесь следует упомянуть, что следы теории сравнений можно обнаружить за несколько столетий до Гаусса. Некоторые из них присутствуют в древних правилах проверки арифметических вычислений. Они составляют существенную часть инструкции по арифметическим операциям эпохи Ренессанса. Некоторые из них используются до сих пор, а из всего того, что нам известно об их происхождении, можно сказать, что их корни лежат в античности.
Мы не знаем, каким образом эти правила были впервые введены, однако попытаемся указать один из возможных путей, на котором они могли быть открыты. Вернемся к временам счетных досок. На таком абаке каждая цифра в числах, которые участвовали в вычислениях, обычно выкладывалась с помощью фишек, камней, палочек или орехов, причем каждая группа отмечала количество единиц, десятков, сотен и т. д. в соответствии с местом их нахождения. В нашей десятичной системе число
N = a n 10 n+ a n -110 n -1+… + a 210 2+ a 110 + a 0= ( a n, a n -1…, a 2, a 1, a 0) 10 (8.1.1)
потребовало бы для своей записи
S N = a n + a n -1+… + а 2+ а 1+ а 0(8.1.2)
фишек. Это число мы называем суммой цифр числа N .
Теперь предположим, что мы хотим выполнить на доске простое действие, а именно: сложить два числа N и M . Тогда мы должны отметить на доске также второе число
M = ( b m, b m -1, …, b 2, b 1, b 0) 10,
у которого на тех же линиях лежит
S M = b m + b m -1+ … + b 2+ b 1+ b 0
складываемых фишек. На некоторых линиях может теперь лежать больше, чем по 9 фишек. Операция, необходимая для нахождения числа N + М , состоит в замене десяти фишек на одной линии одной фишкой на следующей линии. И так нужно продолжать до тех пор, пока такой процесс возможен. На каждом шаге заменяют десять фишек одной-единственной и таким образом происходит потеря девяти фишек на доске. Итак, мы видим, что если сложение выполнено правильно, то число фишек, остающихся на доске, должно удовлетворять условию
Читать дальшеИнтервал:
Закладка: