2016-10-30 00:44:00
#АПО_математика #алгебра #арифметика #ОТА #Алгоритм_Евклида
Друзья, #АПО_математика снова с вами! На этот раз мы поговорим про то, что, казалось бы, вы все знаете с начальной школы. Мы поговорим об арифметике.
Не спешите пролистывать этот пост - возможно, здесь будет что-то новое! Мы докажем утверждение, пафосно называющееся "Основной теоремой арифметики". И, конечно же, порешаем задачи - некоторые будут совсем не тривиальными!
Для начала - некоторые вспомогательные (но полезные и самостоятельно) сведения. Мы расскажем про алгоритм Евклида.
Для начала напомним (вдруг кто-то забыл!), что наибольшим общим делителем (НОД) для двух натуральных чисел m и n называется наибольший из их общих делителей, обозначаемый НОД(m, n).
Пример: для чисел 70 и 105 наибольший общий делитель равен 35.
Алгоритм Евклида:
Пусть a и b — натуральные числа, и последовательность чисел
a > b > r1 > ... >rn
определена тем, что каждое rk — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
a = bq0 + r1
b = r1q1 + r2
r1 = r2q2 + r3
...
r{k-2} = r{k-1} q{k-1} + rk
...
r{n-1} = rn qn
Тогда НОД(a, b) = rn, последнему ненулевому члену этой последовательности.
Существование таких r1, r2, ..., то есть возможность деления с остатком m на n для любого целого m и целого n != 0, доказывается индукцией по m.
Корректность этого алгоритма вытекает из следующих двух утверждений.
Лемма:
Пусть a = bq + r, тогда НОД(a, b) = НОД(b, r).
Доказательство:
Пусть k — любой общий делитель чисел a и b, не обязательно максимальный, тогда a = t1 k ; b = t2 k; где t1 и t2 — целые числа из определения.
Тогда k также общий делитель чисел b и r, так как b делится на k по определению, а r = a - bq = (t1 - t2 q)k (выражение в скобках есть целое число, следовательно, k делит r без остатка)
Обратное также верно и доказывается аналогично 2) - любой делитель b и r так же является делителем a и b.
Следовательно, все общие делители пар чисел a, b и b, r совпадают. Другими словами, нет общего делителя у чисел a, b, который не был бы также делителем b, r, и наоборот.
В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.
Лемма:
НОД(0, r) = r для любого ненулевого r.
Проще сформулировать алгоритм Евклида так: если даны натуральные числа a и b и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.
Расширенный алгоритм Евклида:
Формулы для ri могут быть переписаны следующим образом:
r1 = a + b(-q0)
r2= b - r1q1 = a(-q1)+b(1+q1q0)
...
НОД(a, b) = rn = as + bt, где s и t целые.
Это представление наибольшего общего делителя называется соотношением Безу, а числа s и t — коэффициентами Безу. Соотношение Безу является ключевым в доказательстве основной теоремы арифметики.
