36. Найбільший спільний дільник і найменше спільне кратне

Найбільший спільний дільник (НСД) двох або більше невід'ємних цілих чисел - це найбільше натуральне число, на яке ці числа ділиться без остачі.

Приклад

Число 54 може бути виражене як добуток двох інших цілих чисел кількома способами:

Отже дільники числа 54 є:

Аналогічно дільники числа 24 є:

Числа, які є у обох цих списках, є спільними дільниками чисел 54 та 24:

Найбільшим серед них є число 6. Воно найбільшим спільним дільником чисел 54 та 24. Можна записати:

Скорочення дробів

Найбільший спільний дільник використовується для скорочення дробів. Наприклад, НСД(42, 56) = 14, тому,

Властивості

НСД є комутативною функцією: НСД(a, b)= НСД(b, a).

• НСД(a, b)

НСД(a, b, c, d) = НСД(НСД(a, b), НСД(c, d))

НСД(a, b) =|ab|/НСК(a, b), де НСК(a, b) найменше спільне кратне чисел a, b.

Обчислення НСД методом розкладу на прості множники

Нехай розклад чисел на прості множники:

Тоді

НДС

Найменше спільне кратне (НСК) двох цілих чисел a, b називаємо найменше натуральне число, яке є кратним обох цих чисел. Позначаємо НСК(a, b), в англомовній літературі LCM(a, b). Отже НСК(a, b) є найменшим натуральним числом, яке ділиться без залишку на обидва числа a, b. Означення можна – очевидним способом – узагальнити на довільну кількість аргументів.

Властивості

НСК(a, b)= НСК(b, a) (перестановка аргументів не змінює НСК).

НСК(a, b, c, d) = НСК(НСК(a, b), НСК(c, d) )

НСК(a, b) =|ab|/НСД(a, b), де НСД(a, b) найбільший спільний дільник чисел a, b.

Обчислення НСК методом розкладу на прості множники

Нехай розклад чисел на прості множники:

Тоді

НСК

НСК можна теж обчислити за допомогою рівності НСК(a, b) =|ab|/НСД(a, b), використавши для обчислення НСД ефективний алгоритм Евкліда

37. Ознаки подільності на складені числа

Числа 4, 26, 81 — складені, тому що мають дільники крім 1 і самих себе:

Кожне складене число можна розкласти на прості множники – записати дане складене число у вигляді добутку простих чисел.

38. Алгоритми Евкліда

Алгоритм Евкліда (також називається евклідів алгоритм) — ефективний метод обчислення найбільшого спільного дільника (НСД). Названий на честь грецькогоматематика Евкліда, котрий описав його в книгах VII та X Начал.^[1]

Найбільший спільний дільник двох чисел це найбільше число, що ділить обидва дані числа без залишку. Алгоритм Евкліда оснований на тому, що НСД не змінюється, якщо від більшого числа відняти менше. Наприклад, 21 є НСД чисел 252 та 105 (252 = 21 × 12;105 = 21 × 5); оскільки 252 − 105 = 147, НСД 147 та 105 також 21. Оскільки більше з двох чисел постійно зменшується, повторне виконання цього кроку дає все менші числа, поки одне з них не дорівнюватиме нулю. Коли одне з чисел дорівнюватиме нулю, те, що залишилось, і є НСД. Обертаючи кроки алгоритму Евкліда в зворотній порядок, НСД можна виразити як лінійну комбінацію даних чисел помножених на цілі коефіцієнти, наприклад21 = 5 × 105 + (−2) × 252. Ця важлива властивість відома як лема Безо.

Найдавніший опис алгоритму знаходиться в Началах Евкліда (біля 300 до н. е.), що робить його найдавнішим чисельним алгоритмом, яким користуються і нині. Оригінальний варіант алгоритму описував роботу лише з натуральними числами та геометричними довжинами (дійсними числами), алгоритм було узагальнено в XIX столітті на роботу з іншими типами чисел, такими як Гаусові цілі та поліноми з однією змінною. Це призвело до появи сучасних алгебраїчних понять, таких як Евклідові класи. Алгоритм Евкліда було узагальнено ще далі для роботи з іншими математичними структурами, такими як вузли та поліноми від багатьох змінних. Алгоритм евкліда має багато застосувань на практиці, та в теорії. З його допомогою можна згенерувати практично всі найважливіші музичні ритми різних культур у всьому світі. Алгоритм Евкліда відіграє ключову роль в алгоритмі RSA, поширеному методі криптографії з відкритим ключем. Його також використовують для пошуку розв'язків Діофантових рівнянь