Архив метки: наибольший общий делитель

Вокруг наибольшего общего делителя

Евклид

Одна из простейших задач, для решения которой понадобится найти наибольший общий делитель пары натуральных чисел a и b, — это задача сокращения дроби a/b.

Напомним, что если числа a и b делятся на одно и то же натуральное число a, то число а называется общим делителем пары чисел a и b. Любая пара натуральных чисел имеет хотя бы один общий делитель (а именно, d = 1), причем любой общий делитель не превосходит каждого из этих чисел. Поэтому среди всех делителей чисел a и b можно выбрать наибольший общий делитель, который обозначается через (a, b), например (20, 100) = 20, (65, 39) = 13. Если (a, b) = 1, то числа a и b называются взаимно простыми. При этом взаимно простые числа a и b совсем не обязательно сами по себе должны быть простыми числами; так, (33, 35) = 1, но 33 = 3 × 11 и 35 = 5 × 7.

Читать далее