Имеем два натуральных числа a и b, если они взаимно просты, то мультипликативная функция устанавливает число взаимно простых чисел, для произведение двух взаимно простых чисел по формуле:
т.е. при больших a и b, эта формула позволяет уменьшить вычислительную сложность.
Но если числа a и b не взаимно простые, то вычисления проводятся по обычной формуле.
Пример:
a=60 b=11. 60 и 11 – взаимно простые.
Как мы уже выяснили, для 60 число взаимно простых чисел равно 16, а для
11 равно 10.
т.е. .