My-library.info
Все категории

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

На электронном книжном портале my-library.info можно читать бесплатно книги онлайн без регистрации, в том числе О. ОРЕ - Приглашение в теорию чисел. Жанр: Прочая научная литература издательство -, год 2004. В онлайн доступе вы получите полную версию книги с кратким содержанием для ознакомления, сможете читать аннотацию к книге (предисловие), увидеть рецензии тех, кто произведение уже прочитал и их экспертное мнение о прочитанном.
Кроме того, в библиотеке онлайн my-library.info вы найдете много новинок, которые заслуживают вашего внимания.

Название:
Приглашение в теорию чисел
Автор
Издательство:
-
ISBN:
нет данных
Год:
-
Дата добавления:
31 январь 2019
Количество просмотров:
201
Читать онлайн
О. ОРЕ - Приглашение в теорию чисел

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

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

Приглашение в теорию чисел читать онлайн бесплатно

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

Пример. Когда два сравнения из (7.3.5) перемножены, получается

77 = 45 (mod 8).

Сравнение ab (mod m) может быть умножено на любое целое число с, при этом получаем

асbc (mod m). (7.3.7)

Это можно рассматривать как частный случай умножения сравнений (7.3.6) при с = d. Его можно также рассматривать как прямое следствие из определения сравнения.

Пример. Когда первое сравнение из (7.3.5) умножается на 3, получаем, что

33 = -15 (mod 8).

Возникает естественный вопрос: в каком случае можно в сравнении (7.3.7) сократить общий множитель с и получить при этом верное сравнение

ab (mod m)?

Именно здесь сравнения отличаются от уравнений. Например, верно, что

22 ≡ -2 (mod 8),

но сокращение на множитель 2 дало бы сравнение

11 ≡ -1 (mod 8),

которое неверно.

В одном важном случае сокращение допустимо:

если асbc (mod m), то ab (mod m) при условии, что числа m и с взаимно просты.

Доказательство. Первое сравнение означает, что

ас — bc = (а — b) с = mk.

Если D(m, с) = 1, то отсюда следует, что а — b делится на m в соответствии с результатом, доказанным в § 2 главы 4.

Пример. В сравнении

4 ≡ 48 (mod 11)

мы можем сократить на множитель 4, так как D(11, 4) = 1. Это дает

1 ≡ 12 (mod 11).

Система задач 7.3.

1. Придумайте еще несколько примеров на использование изложенных правил действий со сравнениями.

§ 4. Возведение сравнений в степень

Предположим вновь, что имеется сравнение

ab (mod m).

Как мы только что видели, можно умножить это сравнение на себя, получив

а2 ≡ b2 (mod m).

Вообще можно, умножив это сравнение на себя нужное количество раз, получить

anbn (mod m)

для любого целого положительного числа m.

Пример. Из сравнения

8 ≡ -3 (mod 11)

после возведения в квадрат следует сравнение

64 ≡ 9 (mod 11),

а после возведения в куб получаем сравнение

512 ≡ -27 (mod 11).

Многие результаты теории сравнений связаны с остатками высоких степеней чисел, поэтому покажем, как можно продолжить процесс возведения в степень. Предположим, например, что мы хотим найти остаток сравнения

389 (mod 7).

Одним из путей для выполнения этого является повторное возведение в квадрат. Мы находим:

9 = 32 ≡ 2 (mod 7),

34 ≡ 4,

38 ≡ 16 ≡ 2,

364 ≡ 4 (mod 7).

Так как

89 = 64 + 16 + 8 + 1 = 26 + 24 + 23 + 1,

то отсюда следует, что

389 = 364 • З16 • З8 • 3 = 4 • 4 • 2 • 3 ≡ 5 (mod 7).

Таким образом, остаток (по модулю 7) есть 5, или, говоря другими словами, в соответствии с изложенным в § 2, последняя цифра числа З89, записанного в системе счисления при основании 7, равна 5.

В действительности, для того чтобы найти этот остаток, мы записали показатель степени

89 = 26 + 24 + 23 + 1 = (1, 0, 1, 1, 0, 0, 1)

в двоичной системе счисления. Повторным возведением в квадрат мы нашли остатки (по модулю 7) тех степеней числа 89, которые сами являются степенями числа 2:

1, 2, 4, 8, 16, 32, 64.

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

33 ≡ -1 (mod 7),

З6 ≡ 1 (mod 7),

откуда заключаем, что

384 = (36)14 ≡ 1 (mod7).

Поэтому

389 = 384 • 33 • 32 ≡ 1 • (-1) • 2 = -2 ≡ 5 (mod 7),

как и раньше.

В качестве другой иллюстрации сказанного можно рассмотреть числа Ферма, с которыми мы познакомились в § 3 гл. 2:

Fn = 22ⁿ+1.

Первые пять чисел Ферма таковы:

F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537.

Отсюда можно высказать предположение:

десятичная запись всех чисел Ферма, за исключением F0 и F1 оканчивается цифрой 7.

Докажем с помощью сравнений, что это действительно так. Очевидно, что оно равносильно утверждению, что числа

22ⁿ, n = 2, 3…

оканчиваются цифрой 6. Это можно доказать по индукции. Заметим, что

22² = 16 ≡ 6 (mod 10),

22³ = 256 ≡ 6 (mod 10),

22ˆ4 = 65536 ≡ 6 (mod 10),

Более того, если мы возводим в квадрат число 22ˆk, то результатом будет число

Предположим, что для некоторого значения t

;

возводя в квадрат это сравнение, мы находим, что

,

что и требовалось.

§ 5. Теорема Ферма

Из алгебры мы знаем правила возведения бинома в степень:

(x + у)1 = х + у,

(х + у)2 = x2 + 2xy + y2,

(x + y)3 = х3 + Зx2y + Зху2 + у3,

(x + у)4 = х4 + 4х3у + 6х2у2 + 4ху3 + у4 (7.5.1)

и вообще

(х + у)p = хр + Cp1xp-1y + Ср2хр-2y2 +… + ур. (7.5.2)

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

Cp1 = 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у + 10x3y2 + 10x2y3 + 5xy4 + у5.

Так как все средние коэффициенты делятся на 5, то

(х + у)5 ≡ х5 + у5 (mod 5)

в соответствии с (7.5.5).

Из сравнения (7.5.5) можно сделать важные выводы. Применим его для случая х = у = 1. Получаем

2p = (1 + 1)p ≡ 1p + 1p = 2 (mod p).

Возьмем затем х = 2, у = 1 и найдем, что

3p = (2 + 1)p ≡ 2p + 1p;

теперь, используя предыдущий результат, 2p ≡ 2 (mod p), получаем

2p + 1p ≡ 2 + 1 ≡ (mod p).

Итак, 3p ≡ 3 (mod p). Далее для х = 3, у = 1 получаем

4p ≡ 4 (mod p).


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

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


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

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

Прокомментировать
Подтвердите что вы не робот:*
Подтвердите что вы не робот:*
Все материалы на сайте размещаются его пользователями.
Администратор сайта не несёт ответственности за действия пользователей сайта..
Вы можете направить вашу жалобу на почту librarybook.ru@gmail.com или заполнить форму обратной связи.