Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Наибольший общий делитель. Алгоритм Евклида

Читайте также:
  1. CRC-алгоритмы обнаружения ошибок
  2. VII. Алгоритмы продаж
  3. Алгоритм 4. Транспонування бази даних
  4. Алгоритм 5. Пошук автофильтром
  5. Алгоритм Apriori
  6. Алгоритм De Boor
  7. Алгоритм De Boor для Кривых NURBS

 

Если d делит а и d делит b, то d - общий делитель чисел а и b. Так как делителей чисел а и b конечное число, то и общих делителей чисел а и b конечное число. Среди любого конечного числа целых чисел существует наибольшее. Наибольший из общих делителей называется наибольшим общим делителем чисел а и b и обозначается НОД или просто Аналогично вводится наибольший делитель нескольких целых чисел Если наибольший общий делитель чисел равен 1, то эти числа называются взаимно простыми. Числа попарно взаимно простые являются и взаимно простыми, но числа взаимно простые не обязательно попарно взаимно простые. Например, числа 10, 12, 27 взаимно простые, но пары 10 и 12, 12 и 27 имеют общие множители.

 

Алгоритм Евклида нахождения наибольшего общего делителя двух целых чисел. Пусть а и b – положительные целые числа и Применим теорему о делении с остатком несколько раз:

............

Процесс деления предыдущего остатка на следующий конечен, так как в последовательности:

может быть только конечное число чисел (не более, чем b чисел).

Пусть х – общий делитель чисел а и b. Тогда двигаясь от равенства к следующему, начиная с первого, получим делится на х, делится на х и т.д., делится на х. Двигаясь же от последнего равенства к первому, заметим, что делится на делится на и т.д., b делится на , а делится на . Таким образом, - общий делитель чисел а и b, делящийся на любой другой общий делитель этих чисел, т.е. Таким образом, последний ненулевой остаток в алгоритме Евклида – наибольший общий делитель.

 

Пример. Найти НОД(1173, 323).

Решение:

Ответ: 17.

 

Упражнения и задачи

 

Найти наибольший общий делитель систем чисел:

а) 546 и 231; б) 1001 и 6253; в) 1517 и 2257;

г) 2737, 9163 и 9639; д) 1411, 4641 и 5253.

Доказать, что если то

Доказать, что если а делится на b, то

Для любого целого положительного числа т доказать равенство:

Если то Доказать.

Доказать, что

Доказать, что для любых натуральных а и b имеет место равенство:

Если то Доказать.

 

 


Дата добавления: 2015-10-23; просмотров: 197 | Нарушение авторских прав


Читайте в этой же книге: Основная теорема арифметики кольца целых чисел | Упражнения и задачи | Упражнения и задачи | Упражнения и задачи | Алгебраическая форма комплексного числа | Геометрическая интерпретация комплексных чисел | Упражнения и задачи | Упражнения и задачи | Извлечение корня из комплексного числа | Упражнения и задачи |
<== предыдущая страница | следующая страница ==>
Упражнения и задачи| Наименьшее общее кратное

mybiblioteka.su - 2015-2024 год. (0.006 сек.)