- Главная
- Математика
- Алгоритм Евклида
Содержание
- 2. АЛГОРИТМ ЕВКЛИДА Алгоритм Евклида - это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел.
- 3. Вычисление НОД НОД = наибольший общий делитель двух натуральных чисел – это наибольшее число, на которое
- 4. Найдите НОД и НОК чисел, используя Алгоритм Евклида М=32, N=24; M=696, N=234. 1. Проверить, являются ли
- 5. Найдите НОД (111 … 111,11 … 11) – в записи первого числа 100 единиц, в записи
- 7. Скачать презентацию
Слайд 2АЛГОРИТМ ЕВКЛИДА
Алгоритм Евклида - это алгоритм нахождения наибольшего общего делителя (НОД) двух
АЛГОРИТМ ЕВКЛИДА
Алгоритм Евклида - это алгоритм нахождения наибольшего общего делителя (НОД) двух
Евклид
(365-300 до. н. э.)
Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание».
Слайд 3Вычисление НОД
НОД = наибольший общий делитель двух натуральных чисел – это наибольшее
Вычисление НОД
НОД = наибольший общий делитель двух натуральных чисел – это наибольшее
НОД(a, b)= НОД(a-b, b)= НОД(a, b-a)
Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД.
НОД (18, 45) = НОД (18, 45-18) = НОД (18, 27)= НОД (18, 9) = =НОД(9,9)=9
Пример :
Слайд 4Найдите НОД и НОК чисел, используя Алгоритм Евклида М=32, N=24; M=696, N=234.
1.
1.
Примечание. Два числа называются взаимно простыми, если их наибольший общий делитель равен 1.
2. Найти наименьшее общее кратное (НОК) чисел 645 и 381, если
НОК(n, m) = n * m / НОД (n, m).
3. Даны натуральные числа m(120) и n(75). Найти такие натуральные p и q, не имеющие общих делителей, что
p / q = m / n.
4. Найти НОД трех чисел 112, 81, 342.
Примечание. НОД(a, b, c)= НОД(НОД(a, b), c)
Задачи
Слайд 5Найдите НОД (111 … 111,11 … 11) – в записи первого числа
Найдите НОД (111 … 111,11 … 11) – в записи первого числа
в записи второго – 60.
Докажите, что существуют целые числа m и n такие, что ma + nb = 1. e)
Какова последняя цифра числа ?
Найти наибольший общий делитель чисел 420 и 148, путем разложения
на простые множители.