Урок по теме "Алгоритм Евклида"

1. Проверка д/з: вопросы? Проверить рассуждения и ответы в задачах. №674 [41 чел.; 3 ап. + 2 яб.]; №695 [300 см]; №725 – выписать на доске результаты разложений чисел на множители и ответы:

1) 2450 = 2×5²×7²; 3500 = 2²×5³×7; н.о.д.(2450; 3500) = 2×5²×7 = 350; н.о.к.(2450; 3500) = 2²×5³×7² = 24500. 2) 792 = 2³×3²×11; 2178 = 2×3²×11²; н.о.д.(792; 2178) = 2×3²×11 = 198; н.о.к.(792; 2178) = 2³×3²×11² = 8712.

2. Устно: Верны ли утверждения? Почему?

а) Если числа а и b кратны с, то н.о.д.(а; b) кратен с.

б) Если с делится на а и с делится на b, то с делится на н.о.к.(а; b).

3. Новый материал. Выясним еще некоторые свойства н.о.д. и н.о.к., используя решение домашнего №725.

1) Найдем произведение: н.о.д.(2450; 3500)×н.о.к.(2450; 3500) = 2×5²×7×2²×5³×7² = 2³×5⁵×7³.

Найдем произведение: 2450×3500 = 2×5²×7²×2²×5³×7 = 2³×5⁵×7³.

Случаен ли полученный нами результат? Проверьте самостоятельно верна ли аналогичная закономерность для чисел из примера 2). Сформулируйте и объясните эту закономерность.

Для любых двух натуральных чисел a и b: н.о.д.(a; b)× н.о.к.(a; b) = ab.

2) Приведите пример такой пары чисел, чтобы их н.о.д. являлось одно из этих чисел. Чему равно их н.о.к.? Приведите пример такой пары чисел, чтобы их н.о.к. являлось одно из этих чисел. Чему равен их н.о.д.? Как объяснить полученные результаты? Запишем их.

н.о.д.(a; b) = a т. и т. т., когда н.о.к.(a; b) = b.

3) Приведите примеры таких пар чисел, чтобы их н.о.д. равнялся 1. Чему равны их н.о.к.?

Сформулируйте закономерность. Верно ли обратное утверждение? Как объяснить полученные результаты? Запишем их.

н.о.к.(a; b) = ab т. и т. т., когда н.о.д.(a; b) = 1.

4) Рассмотрим еще один способ поиска н.о.д. двух чисел, который носит название Алгоритм Евклида. Его удобно применять прежде всего для тех случаях, когда данные числа трудно разложить на простые множители.

Пример. Пусть надо найти н.о.д. чисел 323 и 437. Сделать это подбором или разложением на простые множители не просто, так как ни одно из этих чисел не кратно 2, 3, 5, 7, 11. Поступаем следующим образом (комментарий):

437 = 323×1 + 114;

323 = 114×2 + 95;

114 = 95×1 + 19;

95 = 19×5.

н.о.д.(323; 437) = 19. Как, в этом случае, удобно искать н.о.к. этих чисел?

н.о.к. (323; 437) = 437×323:19 = 323×23 = 7429.

Алгоритм Евклида основан на следующем факте:

если a = b×q + r, то н.о.д.(a; b) = н.о.д.(b; r)

Действительно, если с – произвольный общий делитель чисел а и b, то r = a – bq делится на c; и наоборот, если с – произвольный общий делитель чисел b и r, то а делится на с. То есть, все общие делители пар (а; b) и (b; r) совпадают, а значит, совпадают и их наибольшие общие делители.

В частном случае, часто применяют следствие: н.о.д.(a; b) = н.о.д.(a – b; b), которое получается из общего правила при q = 1.

1. Упражнения. (письменно, на доске и в тетрадях, с фронтальным обсуждением)

1) Может ли н.о.д. трех чисел быть равен 15, если их произведение равно 3000? [нет, так как 15 = 3×5, значит, число 3 должно входить в разложение каждого из трех чисел. Но, 3000 = 2³×3×5³.]

2) Найдите а и b, если:

а) н.о.д.(a; b) = 5; н.о.к.(a; b) = 105; [5×3 = 15, 5×7 = 35 или 5, 105.]

б) н.о.д.(a; b) = 7; a×b = 294; [ н.о.к.(a; b) = 294:7 = 42. 7, 42 или 14, 21.]

в) н.о.к.(a; b) = 360, а частные от деления чисел a и b на их н.о.д. равны соответственно 3 и 5. [пусть н.о.д.(а; b) = x, тогда a = 3x; b = 5x. 3x×5x = 360x; x = 24; a = 72; b = 120.]

3) Используя алгоритм Евклида, найдите н.о.д. и н.о.к.:

а) 713 и 217; [31 и 4991]

б) двух соседних натуральных чисел; [1 и n×(n+1)]

в) двух соседних четных чисел. [2 и 2n×(n+1)]

Домашнее задание: 1) стр. 124, №675; 2) стр. 127, №694; 3) Найдите н.о.д. и н.о.к.:

а) 1073 и 407; б) двух соседних нечетных чисел.