Составители:
Рубрика:
113
6. ТЕОРИЯ ЧИСЕЛ И НЕКОТОРЫЕ ЕЕ ПРИЛОЖЕНИЯ
Одним из разделов дискретной математики является теория чи
сел, которая первоначально изучала свойства целых чисел. Целое
число является одним из древнейших математических понятий, свя
занных с подсчетом окружающих предметов. Теория чисел возник
ла из задач арифметики и первоначально оперировала четырьмя
арифметическими действиями над натуральными (целыми, положи
тельными) числами. Основными понятиями этой теории являлись
простые числа, составные числа, квадратные числа (числа, равные
квадрату некоторого другого числа), совершенные числа (число, рав
ное сумме своих делителей). В 6 в. до н. э. в Древней Греции было
известно решение уравнения x
2
+ y
2
= z
2
в целых числах. В 3 в. до н. э.
Евклид в «Началах» обосновал алгоритм нахождения наибольшего
общего делителя двух произвольных целых чисел и доказал, что ко
личество простых чисел является бесконечным. Эратосфен предло
жил метод нахождения простых чисел («Решето Эратосфена»). Систе
матизация проблем теории чисел и методов их решений была выпол
нена в 3 в. н. э. Диофантом в «Арифметике». В 17 в. н. э. Ферма
исследовал решения многих уравнений в целых числах и высказал
гипотезу, что уравнение x
n
+ y
n
= z
n
, n>2, x, y, z – целые, не имеет
решений (великая теорема Ферма). Ему также принадлежит утвер
ждение о том, что если a и p взаимно простые числа (наибольший
общий делитель этих чисел равен 1), где a – целое, p – простое, то
a
p
– a делится на p нацело (малая теорема Ферма). Эйлер доказал
великую теорему Ферма при n = 3 и обобщил малую теорему Ферма,
введя понятие функции j(m) – количества чисел ряда 1, 2, 3, …, m
взаимно простых с m, ныне называемую функцией Эйлера от целого
m, и показал, что любое число a, взаимно простое с m, возведенное
в степень j(m), при делении на m дает в остатке 1. Проблема нахож
дения целых положительных остатков при делении одного целого
на другое возникла из задач календарных расчетов в Китае (Сунь
цзы, Цинь Цзюшао) и в современном виде формулируется как ки
тайская теорема об остатках.
Важным понятием теории чисел являются сравнения, основные
свойства которых были доказаны Гауссом. Сравнение является свой
ством эквивалентности чисел, имеющих одинаковые положительные
остатки при делении на некоторое целое число – модуль.
Страницы
- « первая
- ‹ предыдущая
- …
- 111
- 112
- 113
- 114
- 115
- …
- следующая ›
- последняя »
