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

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

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

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

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


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

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

Интервал:

Закладка:

Сделать

то последняя цифра а 0является остатком числа а при делении его на число m . Если мы используем этот факт, чтобы иначе выразить нашу интерпретацию сравнения, то можно сказать:

сравнение аb (mod m) выполняется для целых (положительных) чисел а и b тогда и только тогда, когда числа а и b имеют одинаковые последние цифры в записи при основании m.

Например,

37 ≡ 87 (mod 10),

так как эти два числа имеют одну и ту же последнюю цифру в десятичной системе чисел.

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

1. Найдите остатки —37(mod 7), — 111 (mod 11), — 365 (mod 30).

§ 3. Алгебра сравнений

Из алгебры мы помним, что уравнения можно складывать, вычитать, умножать. Точно такие же правила справедливы для сравнений. Предположим, что мы имеем сравнения

ab (mod m ), сd (mod m ). (7.3.1)

По определению, это означает, что

a = b + mk, c = d + ml , (7.3.2)

где k и l — целые числа. Сложим уравнения (7.3.2).

В результате получаем

а + с = b + d + m ( k + l ),

что можем записать как

а + сb + d (mod m ); (7.3.3)

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

a — cb — d (mod m ). (7.3.4)

Пример.

11 ≡ —5 (mod 8) и 7 = — 9 (mod 8). (7.3.5)

Складывая их, получаем

18 ≡ — 14 (mod 8),

а вычитая,

4 ≡ 4 (mod 8).

Оба эти сравнения справедливы.

Можно также перемножить два сравнения. Из (7.3.1) и (7.3.2) следует, что

ac = bd + m ( kd + bl + mkl ),

таким образом,

асbd (mod m ). (7.3.6)

Пример. Когда два сравнения из (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≡ b 2(mod m ).

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

a nb n (mod m )

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

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

8 ≡ -3 (mod 11)

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

64 ≡ 9 (mod 11),

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

512 ≡ -27 (mod 11).

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

3 89(mod 7).

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

9 = 3 2≡ 2 (mod 7),

3 4≡ 4,

3 8≡ 16 ≡ 2,

3 64≡ 4 (mod 7).

Так как

89 = 64 + 16 + 8 + 1 = 2 6+ 2 4+ 2 3+ 1,

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

3 89= 3 64• З 16• З 8• 3 = 4 • 4 • 2 • 3 ≡ 5 (mod 7).

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

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

89 = 2 6+ 2 4+ 2 3+ 1 = (1, 0, 1, 1, 0, 0, 1)

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

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

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

3 3≡ -1 (mod 7),

З 6≡ 1 (mod 7),

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

3 84= (3 6) 14≡ 1 (mod7).

Поэтому

3 89= 3 84 • 3 3 • 3 2≡ 1 • (-1) • 2 = -2 ≡ 5 (mod 7),

как и раньше.

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

F n = 2 2ⁿ+1.

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

F 0= 3, F 1= 5, F 2= 17, F 3= 257, F 4= 65537.

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

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

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

2 2ⁿ, n = 2, 3…

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

2 2²= 16 ≡ 6 (mod 10),

2 2³= 256 ≡ 6 (mod 10),

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

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

Предположим что для некоторого значения t возводя в квадрат это сравнение - фото 25

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

возводя в квадрат это сравнение мы находим что что и требовалось 5 - фото 26;

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

что и требовалось 5 Теорема Ферма Из алгебры мы знаем правила - фото 27,

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

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

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

( x + у ) 1= х + у ,

( х + у ) 2= x 2+ 2 xy + y 2,

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

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

и вообще

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

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

Интервал:

Закладка:

Сделать


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

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




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


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


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

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