Алгоритм Евклида - Студенческий научный форум

XI Международная студенческая научная конференция Студенческий научный форум - 2019

Алгоритм Евклида

 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

Арифметика изучает свойства натуральных чисел 1, 2, 3, … Эти числа интересуют людей с древнейших времен, причем особое внимание всегда уделялось простым числам. Простым называется такое натуральное число, большее единицы, которое не имеет других делителей, кроме единицы и самого себя. Значение простых чисел заключается в том, что любое натуральное число, большее единицы, является простым либо разлагается в произведение простых. свойство единственности разложения на простые множители.

Предпосылки основной теоремы арифметики берут свои истоки в Древней Греции. Несмотря на то, что в древнегреческой математике основная теорема арифметики в современной формулировке не встречается, в «Началах» Евклида есть эквивалентные ей предложения. Прежде чем начать изучение Алгоритма Евклида мне бы хотелось узнать больше о самом математике.

Евклид — первый математик Александрийской школы. Его главная работа «Начала» содержит изложение планиметрии, стереометрии и ряда вопросов теории чисел; в ней он подвёл итог предшествующему развитию древнегреческой математики и создал фундамент дальнейшего развития математики. Начала состоят из тринадцати книг:

В I книге изучаются свойства треугольников и параллелограммов; эту книгу венчает знаменитая теорема Пифагора для прямоугольных треугольников.

Книга II посвящена «геометрической алгебре».

В III и IV книгах излагается геометрия окружностей, а также вписанных и описанных многоугольников;

В V книге вводится общая теория пропорций.

В VI книге она прилагается к теории подобных фигур.

VII—IX книги посвящены теории чисел

ВVIII книги рассматриваются теоремы о пропорциях и геометрических прогрессиях, вводится метод для нахождения наибольшего общего делителя двух чисел (известный ныне как алгоритм Евклида),

В X книге, строится классификация иррациональностей

В XI книге содержатся основы стереометрии.

В XII книге с помощью метода исчерпывания доказываются теоремы об отношениях площадей кругов, а также объёмов пирамид и конусов.

XIII книга посвящена построению пяти правильных многогранников.

Теперь узнав немного об выдающемся математике можно переходить на изучение Алгоритма Евклида. Но в первую очередь нам надо узнать : «Что же такое алгоритм Евклида и в каком виде она нам знакома?»

И так, Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.

Не подозревая еще со школьной скамьи мы работали с теоремой Евклида в школе. Данная теорема известна нам в виде (НОД). Теперь нам следует вспомнить, что такое НОД и алгоритм его нахождения.

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

Алгоритм нахождения НОД делением

Большее число делим на меньшее.

Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).

Если есть остаток, то большее число заменяем на остаток от деления.

Переходим к пункту 1.

Пример: Найти НОД для 30 и 18.

30/18 = 1 (остаток 12)

18/12 = 1 (остаток 6)

12/6 = 2 (остаток 0). Конец: НОД – это делитель.

НОД (30, 18) = 6

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

Алгоритм нахождения НОД вычитанием

Из большего числа вычитаем меньшее.

Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).

Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.

Переходим к пункту 1.

Пример:

Найти НОД для 30 и 18.

30 - 18 = 12

18 - 12 = 6

12 - 6 = 6

6 – 6 = 0 Конец: НОД – это уменьшаемое или вычитаемое.

НОД (30, 18) = 6

Первая теорема Евклида. Если произведение двух чисел делится на простое число

Просмотров работы: 8