Отношения GCD и LCM - PullRequest
       32

Отношения GCD и LCM

5 голосов
/ 10 апреля 2011

Следующее отношение работает только для двух (3, 12) чисел, оно не дает правильного ответа при использовании для трех чисел (3,12,10).Просто интересно, если это мое понимание или это только для двух чисел, и для меня то же самое верно и для алгоритма Евклида.

Ответы [ 2 ]

4 голосов
/ 10 апреля 2011

Аналогичные формулы к

LCM(a, b) = (a x b) / GCD(a,b) or GCD(a,b) = (a x b) / LCM(a, b) 

с тремя переменными просто недопустимы, как показывает ваш пример с (3, 12, 10).

Произведение этих трех чисел равно 360. GCD равно 1. LCM равно 60.

1 голос
/ 22 декабря 2013

Наша общая природа - пытаться упрощать / обобщать вещи, находя закономерности. Тем не менее, хотя мне может показаться интуитивно понятным попытаться применить эту идею, распространяя ее на общий случай n переменных, в этом случае это не работает. Я постараюсь разбить аргументы в пользу формулы.

Сначала мы должны понять, как могла появиться формула LCM (x, y) * GCD (x, y) = x * y. Чтобы найти LCM или GCD, один из способов - разбить каждое из чисел на их основные факторы. Пусть х = 84, у = 30

x = 2 * 2 * 3 * 7 = (2 * 3) * 2 * 7

y = 2 * 3 * 5 = (2 * 3) * 5

Часть в скобках является общей частью. Итак, мы говорим, что хорошо, 2 * 3, то есть 6 должно быть способным делить и x, и y и называть это НАИБОЛЬШИМ общим делителем. Имейте в виду, только 2 или только 3 также являются общими делителями x и y, но не САМЫМИ БОЛЬШИМИ общими делителями.

Чтобы найти наименьшее общее кратное, мы берем GCD и умножаем его на все оставленные числа. Таким образом, наш LCM равен (2 * 3) * 2 * 7 * 5 = 420. Я не описываю интуицию, стоящую за этим, поскольку она проста и также не имеет прямого отношения.

Таким образом, если вы умножите x и y, вы получите 84 * 30 = (2 * 3 * 2 * 7) * (2 * 3 * 5) = (2 * 3) * ((2 * 3) * 2 * 7 * 5) = GCD (x, y) * LCM (x, y) = (2 * 3) * (2 * 3) * (2 * 7 * 5) = [общая часть возведена в степень 2, поскольку она повторяется в обоих числах] * [остальные оставшиеся факторы во всех числах].

Теперь перейдем к вашему вопросу, если вы берете еще одну переменную z = 18 = (2 * 3) * 3, GCD всех 3 чисел является общей частью (2 * 3), т. Е. 6, а LCM равен (2 *). 3) * 2 * 7 * 5 * 3, что бы это ни было.

Теперь x * y * z = (2 * 3) * (2 * 3) * (2 * 3) * (2 * 7 * 5 * 3) = [общая часть возведена в степень 3, поскольку она повторяется во всех 3 числах] * [остальные оставшиеся факторы во всех числах]. Но если вы используете несколько GCD и LCM, вы получите только (2 * 3) * ((2 * 3) * 2 * 7 * 5 * 3) = (2 * 3) * (2 * 3) * (2 * 7 *) 5 * 3), то есть общая часть учитывается только дважды, а не трижды.

Однако, это также может быть случай, когда некоторые из факторов между некоторыми числами (не все, то есть не могут быть включены в GCD) являются общими. В общем случае n переменных GDD (x [1], x [2], ... x [n]) = c [1] c [2] .. c [k], где каждый из c [i] 1 <= i <= k существует один раз во всех числах. LCM ((x [1], x [2], ... x [n]) = GCD (x [1], x [2], ... x [n]) * ((h (p [1] ]) * h (p [2]) * ... h (p [l])), где каждый p [j], 1 <= j <= l - простое число в списке оставшихся факторов, не являющихся частью GCD и h (p [i]) - наивысшая степень p [i], присутствующего в любом из них. </p>

Теперь, когда мы умножаем LCM и GCD на n чисел, кроме потери коэффициентов GCD на что-либо более чем в два раза, мы также теряем факторы, которые частично являются общими для некоторых чисел, и можем найти только результат из высших сил, которые присутствуют, умножаются на GCD.

...