теория-чисел - Задача по теории чисел. Числовые функции

Воспользуемся формулой для вычисления функции Эйлера. Если $%N$% -- натуральное число, и $%D$% -- множество его простых делителей, то $%\varphi(N)=k_DN$%, где коэффициент $%k_D$% равен произведению $%\prod\limits_{p\in D}(1-\frac1p)$%. Для пустого множества $%D$% коэффициент принимается за единицу.

Введём три конечных множества $%A$%, $%B$%, $%C$%, беря в качестве них множество простых делителей только $%n$%, но не $%m$% для первого; только $%m$%, но не $%m$% для второго, и множество общих простых делителей для $%m$%, $%n$% в качестве третьего. Ясно, что $%C$% будет множеством простых делителей числа $%(n,m)$%.

Теперь применяем формулу: $%\varphi(nm)=k_{A\cup B\cup C}nm=k_Ak_Bk_Cnm$%, $%\varphi(n)=k_{B\cup C}nm=k_Bk_Cn$%, $%\varphi(m)=k_{B\cup C}m=k_Bk_Cm$%, $%\varphi((n,m))=k_C(n,m)$%. Подставляя в доказываемое равенство, имеем $%k_Ak_Bk_Cnm=k_Ak_Cnk_Bk_Cm\frac{(n,m)}{k_C(n,m)}$%, что очевидным образом верно.