Вступление. Пьер де Ферма это увлекательная матема
Продолжение серии "О математике и математиках"
Изложение чужих результатов, критика, оценка
— работа для умов второго сорта.
Г. Г. Харди. Апология математика.
Ферма родился в 17 августа 1601 и жил до— 12 января 1665. По образованию он был юрист. Ферма получил юридическое образование — сначала в Тулузе, а затем в Бордо и Орлеане.
В 1631 году, успешно закончив обучение, Ферма выкупил должность королевского советника парламента (другими словами, члена высшего суда) в Тулузе. В этом же году он женился на дальней родственнице матери, Луизе де Лонг. У них было пятеро детей. Быстрый служебный рост позволил Ферма стать членом Палаты эдиктов в городе Кастр (1648). Именно этой должности он обязан добавлением к своему имени признака знатности — частицы de; с этого времени он становится Пьером де Ферма.
Несмотря на свою профессию и серьёзную занятость он увлекался математикой. Наверное, сочетание ‘нормальной профессии” с занятием математикой объясняет, почему его работы привлекали внимание не только математиков - профессионалов, но многих людей – любителей математики.
Ферма внес значительный вклад в математику В такие разделы, как аналитическая геометрия, математический анализ. Его работы позволили заложить основы таких разделов, как теория чисел, теория вероятностей.
Посмотрим, какие идеи Ферма доставили человечеству много хлопот и удовольствия.
Основные понятия теории чисел
Великий математик Карл Фридрих Гаусс говорил: «Математика — царица наук, а теория чисел — королева математики». (Многие ссылаются на эти слова, но никто не подтвердил это документально, что они принадлежат Гауссу). Далее часто добавляют, что это потому, что её результаты просты и красивы, но трудно доказуемы и абсолютно бесполезны. Об этом мы поговорим далее.
Для того чтобы понять основные теоремы Ферма, необходимо хотя бы немного ознакомиться с основными понятиями теории чисел.
МОДУЛЬНАЯ АРИФМЕТИКА
Хорошо известное арифметическое действие - деление (a= q x n + r) имеет две входных переменных - делимое и делитель (a и n) и дает в результате два значения частное и остаток (q и r).
В модульной арифметике, мы интересуемся только одним из результатов - остатком r. Мы не заботимся о частном q. Другими словами, когда мы делим a на n, мы интересуемся только, тем что - значение остатка равно r. Это подразумевает, что мы можем представить изображение вышеупомянутого уравнения как бинарный оператор с двумя входами a и n и одним выходом r.
Операции по Модулю
Вышеупомянутый бинарный оператор назван оператором по модулю и обозначается как mod. Второй символ (n) назван модулем. Операция определения остатка r называется вычетом.
Оператор (mod)определяет по заданному целому числу (a) из множества натуральных чисел и заданному положительному модулю (n) неотрицательный остаток (r).
Это действие обозначается, а mod n =r
Например:
• 27mod 5 = 2
• 36 mod 12 =0
• -18 mod 14= -4. Однако, мы должны прибавить модуль (14), чтобы сделать остаток неотрицательным. Мы имеем r =-4 + 14 = 10. Это означает, что -18 mod 14 = 10.
• . -7 mod 10 =-7
После добавления модуля 10, мы имеем r = 3. Это означает, что -7 mod 10 = 3.
Результат операции по модулю n - всегда целое число между 0 и n - 1. Другими словами, результат a mod n - всегда неотрицательное целое число меньше чем n.
Сравнения
В криптографии, мы часто используем понятие сравнения (конгруэнтность) вместо равенства. Отображение натуральных целых чисел Z в равенства модульной арифметики Zn не отображаются «один в один». Бесконечные элементы множества Z могут быть отображены одним элементом Zn.
Например, результат 2 mod 10 =2, 12 mod 10 = 2, 22 mod 10=2, и так далее. В модульной арифметике целые числа подобные 2, 12, и 22 называются сравнимыми по модулю 10 (по mod 10).
Для того чтобы указать, что два целых числа сравнимы, мы используем, оператор сравнения. Мы добавляем, а mod n к правой стороне сравнения, чтобы показать значение модуля и сделать равенство правильным.
Обозначение оператора сравнения напоминает оператор равенства, но есть различия.
Первое, в отличие от оператора равенства оператор “сравнение” содержит 3 параллельных черты (возможность печати этого символа, к сожалению, в данном случае не доступна).
Второе, оператор равенства отображает целое натуральное число самого на себя; оператор сравнения отображает целое натуральное число на набор чисел n. Оператор равенства показывает, что наборы слева и справа соответствуют друг другу “один в один”, оператор сравнения - "многие - одному".
Система вычетов
Система вычетов [a] - множество целых чисел сравнимых по модулю n. Другими словами, это - набор всех целых чисел таких, что x = a mod(n). Например, если n = 5, мы имеем множество из пяти элементов [0], [1], [2], [3], и [4] таких как это показано ниже:
[0] ={…..,-15, 10, -5, 0, 5, 10, 15, ….}
[1] ={…. ,-14, -9, - 4, 1, 6 ,11,16,.….}
[2]= {…,.-13, -8, -3, 2, 7, 12,17,…}
[3] = {....,-12, -7, -2, 3, 8, 13, 18,…}
[4] = {….., 11, -6, -1, 4 , 9, 14, 19,…}
Целые числа в наборе [0] все дают остаток 0 при делении на 5, (сравнимы по модулю 5). Целые числа в наборе [1] все дают остаток 1 при делении на 5, (сравнимы по модулю 5), и так далее. В каждом наборе, есть один элемент, называемый наименьшим (неотрицательным) вычетом. В наборе [0] это элемент - 0; в наборе [1], этот элемент 1; и так далее. Набор, который показывает все наименьшие вычеты Z5 = {0, 1, 2, 3, 4}. Другими словами, набор Zn - набор всех наименьших вычетов по модулю n.
Операции в системе вычетов
В этой системе определены три бинарных операции (сложение, вычитание, и умножение).
Ниже показаны два шага для каждой операции:
(14+7) mod15 =(21)mod15 (21)mod15=6
(7-11) mod13 =(-4)mod13 (-4)mod13=9
(11x7) mod20 =(77)mod20 (77)mod15=17
Теперь можно рассматривать теоремы Ферма
Продолжение следует
Свидетельство о публикации №215111401681