О. ОРЕ - Приглашение в теорию чисел

Тут можно читать онлайн О. ОРЕ - Приглашение в теорию чисел - бесплатно полную версию книги (целиком) без сокращений. Жанр: Прочая научная литература, издательство Наука Главная редакция физико-математической литературы, год 1980. Здесь Вы можете читать полную версию (весь текст) онлайн без регистрации и SMS на сайте лучшей интернет библиотеки ЛибКинг или прочесть краткое содержание (суть), предисловие и аннотацию. Так же сможете купить и скачать торрент в электронном формате fb2, найти и слушать аудиокнигу на русском языке или узнать сколько частей в серии и всего страниц в публикации. Читателям доступно смотреть обложку, картинки, описание и отзывы (комментарии) о произведении.
  • Название:
    Приглашение в теорию чисел
  • Автор:
  • Жанр:
  • Издательство:
    Наука Главная редакция физико-математической литературы
  • Год:
    1980
  • Город:
    Москва
  • ISBN:
    нет данных
  • Рейтинг:
    4/5. Голосов: 101
  • Избранное:
    Добавить в избранное
  • Отзывы:
  • Ваша оценка:
    • 80
    • 1
    • 2
    • 3
    • 4
    • 5

О. ОРЕ - Приглашение в теорию чисел краткое содержание

Приглашение в теорию чисел - описание и краткое содержание, автор О. ОРЕ, читайте бесплатно онлайн на сайте электронной библиотеки LibKing.Ru

Книга известного норвежского математика О. Оре раскрывает красоту математики на примере одного из ее старейших разделов — теории чисел. Изложение основ теории чисел в книге во многом нетрадиционно. Наряду с теорией сравнении, сведениями о системах счисления, в ней содержатся рассказы о магических квадратах, о решении арифметических ребусов и т. д. Большим достоинством книги является то, что автор при каждом удобном случае указывает на возможности практического применения изложенных результатов, а также знакомит читателя с современным состоянием теории чисел и задачами, ещё не получившими окончательного решения.


Приглашение в теорию чисел - читать онлайн бесплатно полную версию (весь текст целиком)

Приглашение в теорию чисел - читать книгу онлайн бесплатно, автор О. ОРЕ
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

Здесь первый и последний коэффициенты равны единице. Средними биномиальными коэффициентами являются

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 ).

Используя этот процесс, можно доказать по индукции, что а pa (mod p ) для всех значений числа

а = 0, 1…. р -1. (7.5.6)

Случаи a = 0 и а = 1 очевидны. Так как каждое число сравнимо (mod р ) с одним из остатков, записанных в (7.5.6), мы делаем вывод:

для любого целого числа а и любого простого числа р

a pa (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 + М , состоит в замене десяти фишек на одной линии одной фишкой на следующей линии. И так нужно продолжать до тех пор, пока такой процесс возможен. На каждом шаге заменяют десять фишек одной-единственной и таким образом происходит потеря девяти фишек на доске. Итак, мы видим, что если сложение выполнено правильно, то число фишек, остающихся на доске, должно удовлетворять условию

Читать дальше
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать


О. ОРЕ читать все книги автора по порядку

О. ОРЕ - все книги автора в одном месте читать по порядку полные версии на сайте онлайн библиотеки LibKing.




Приглашение в теорию чисел отзывы


Отзывы читателей о книге Приглашение в теорию чисел, автор: О. ОРЕ. Читайте комментарии и мнения людей о произведении.


Понравилась книга? Поделитесь впечатлениями - оставьте Ваш отзыв или расскажите друзьям

Напишите свой комментарий
x