Question

Натуральні числа m, n такі, що НСД(m, n) + НСK(m, n) = m + n. Доведіть, що одне з цих чисел є дільником другого.

Answer 1

m = p1^d1 * p2^d2 * p3^d3 * ... * pk^dk

n = p1^q1 * p2^q2 * p3^q3 * ... * pk^qk

Степени могут быть нулеывми.

Где p  - простое. Рядом стоящая цифра - индекс.

^ - степень.

m + n = min(p1^d1, p1^q1) * min(p2^d2, p2^q2) * ... * min(pk^dk,pk^qk) + max(p1^d1,p1^q1)* ... * max(pk^dk, pk^qk)

С другой сторноы

m+n = p1^d1*p2^d2+p3^d3*...*pk^dk+p1^q1*p2^q2*...*pk^qk

Чтоб торжество было верно d1 > q1, d2 > q2, d3>q3, ... , dk > qk;

или наоборот d1 < q1, d2 < q2, d3 < q3, ... , dk < qk. Конец решения.

Answer 2

Для доведення цієї твердження розглянемо, яким чином НСД (найменший спільний дільник) та НСK (найменше спільне кратне) пов'язані зі значеннями m та n.

Нехай НСД(m, n) = d, де d - найбільший спільний дільник m та n. Тоді ми можемо записати m та n у такому вигляді:

m = d * x n = d * y

де x і y є цілими числами, і НСД(x, y) = 1 (тобто x і y взаємно прості числа).

Тепер давайте розглянемо, як знаходяться НСК(m, n). НСК(m, n) обчислюється за формулою:

НСК(m, n) = (m * n) / НСД(m, n)

Підставимо значення m і n, які ми знайшли раніше:

НСК(m, n) = (d * x * d * y) / d = d * x * y

Тепер ми можемо переписати рівняння НСД(m, n) + НСК(m, n) = m + n:

d + (d * x * y) = d * x + d * y

Виділимо d з обох сторін рівняння:

d * (1 + x * y) = d * (x + y)

Тепер ми можемо скасувати d з обох сторін, оскільки d не дорівнює нулю (якщо б він був нулем, то m і n були б нулями, що суперечило б умові):

1 + x * y = x + y

Переносимо x * y на ліву сторону:

1 = x + y - x * y

Тепер ми побачили, що ліва сторона дорівнює 1. Це можливо, лише якщо одне з чисел x або y дорівнює 0, оскільки:

1 = x + y - x * y 1 = x * (1 - y) + y

1 може бути представлено як добуток двох чисел тільки в одному випадку: коли одне з чисел - 1, інше - 1, що означає, що одне з чисел x або y дорівнює 0.

Отже, ми показали, що одне з чисел m або n дорівнює 0, і, отже, одне з них є дільником іншого.