Мультипликативная функция

 

Имеем два натуральных числа a и b, если они взаимно просты, то мультипликативная функция устанавливает число взаимно простых чисел, для произведение двух взаимно простых чисел по формуле:

 

 

т.е. при больших a и b, эта формула позволяет уменьшить вычислительную сложность.

Но если числа a и b не взаимно простые, то вычисления проводятся по обычной формуле.

Пример:

 

a=60 b=11. 60 и 11 – взаимно простые.

 

 

Как мы уже выяснили, для 60 число взаимно простых чисел равно 16, а для

 

11 равно 10.

 

т.е. .