Наибольший общий делитель — различия между версиями
(→Стандартный алгоритм Евклида) |
|||
| Строка 6: | Строка 6: | ||
===Стандартный алгоритм Евклида=== | ===Стандартный алгоритм Евклида=== | ||
| + | |||
| + | Пусть <math>a</math> и <math>b</math> — целые числа, не равные одновременно нулю, и последовательность чисел | ||
| + | : <math> a,\, b,\,r_1 > r_2 > r_3 > r_4 > \cdots >r_n</math> | ||
| + | определена тем, что каждое <math>r_k</math> — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть | ||
| + | : <math>a = bq_0 + r_1</math> | ||
| + | : <math>b = r_1q_1 + r_2</math> | ||
| + | : <math>r_1 = r_2q_2 + r_3</math> | ||
| + | : <math>\cdots</math> | ||
| + | : <math>r_{k-2} = r_{k-1} q_{k-1} + r_k</math> | ||
| + | : <math>\cdots</math> | ||
| + | : <math>r_{n-1} = r_n q_n</math> | ||
| + | |||
| + | Тогда НОД(''a'',''b''), наибольший общий делитель <math>a</math> и <math>b</math>, равен | ||
| + | <math>r_n</math>, последнему ненулевому члену этой последовательности. | ||
| + | |||
| + | '''Существование''' таких <math>r_1, r_2, ...</math>, то есть возможность деления с остатком <math>m</math> на <math>n</math> для любого целого <math>m</math> и целого <math>n\ne 0</math>, доказывается [[Математическая индукция|индукцией]] по ''m''. | ||
| + | |||
| + | '''Корректность''' этого алгоритма вытекает из следующих двух утверждений: | ||
| + | * Пусть <math>a = bq + r</math>, тогда <math>\gcd (a,b) = \gcd (b,r).</math> | ||
| + | {{Hider| | ||
| + | title = '''Доказательство'''| | ||
| + | hidden = 0 | | ||
| + | title-style = text-align: left; height: auto; | | ||
| + | content-style = text-align: left; | | ||
| + | content = | ||
| + | # Пусть k — любой общий делитель чисел a и b, не обязательно максимальный, тогда <math> a = t_1 * k </math> ; <math> b = t_2 * k; </math> где <math> t_1 </math> и <math> t_2 </math> — целые числа из определения. | ||
| + | # Тогда k также общий делитель чисел b и r, так как b делится на k по определению, а <math>r = a - bq = (t_1 - t_2*q)*k </math> (выражение в скобках есть целое число, следовательно, k делит r без остатка) | ||
| + | # Обратное также верно и доказывается аналогично 2) - любой делитель b и r так же является делителем a и b. | ||
| + | # Следовательно, все общие делители пар чисел a,b и b,r совпадают. Другими словами, нет общего делителя у чисел a,b, который не был бы также делителем b,r, и наоборот. | ||
| + | # В частности, максимальный делитель остается тем же самым. Что и требовалось доказать. | ||
| + | }} | ||
| + | * <math>\gcd (0,r) = r</math> для любого ненулевого <math>r.</math> | ||
| + | |||
| + | Проще сформулировать алгоритм Евклида так: если даны натуральные числа <math>a</math> и <math>b</math> и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД. | ||
===Расширенный алгоритм Евклида=== | ===Расширенный алгоритм Евклида=== | ||
Версия 15:03, 30 июня 2010
Эта статья находится в разработке!
Содержание
Наибольший общий делитель как максимальное число, делящее два данных числа
Алгоритм Евклида
Стандартный алгоритм Евклида
Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел
определена тем, что каждое — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
Тогда НОД(a,b), наибольший общий делитель и , равен , последнему ненулевому члену этой последовательности.
Существование таких , то есть возможность деления с остатком на для любого целого и целого , доказывается индукцией по m.
Корректность этого алгоритма вытекает из следующих двух утверждений:
- Пусть , тогда
Доказательство
- Пусть k — любой общий делитель чисел a и b, не обязательно максимальный, тогда ; где и — целые числа из определения.
- Тогда k также общий делитель чисел b и r, так как b делится на k по определению, а (выражение в скобках есть целое число, следовательно, k делит r без остатка)
- Обратное также верно и доказывается аналогично 2) - любой делитель b и r так же является делителем a и b.
- Следовательно, все общие делители пар чисел a,b и b,r совпадают. Другими словами, нет общего делителя у чисел a,b, который не был бы также делителем b,r, и наоборот.
- В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.
- для любого ненулевого
Проще сформулировать алгоритм Евклида так: если даны натуральные числа и и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.
