Calculation of product of all coprimes of number less than itself

Question

Is there any fast way or formula to calculate product of all coprimes of a number less than itself?

How can we do it without finding all coprimes manually?

Note : I have to find actually (product) modulo (the given number).

Answer 1

OEIS has this as A001783 where they call it the "phi-torial." They cite Apostol, "Introduction to Analytic Number Theory" in which it is an exercise to show that $$ \prod_{1\le i<n, \gcd(i,n)=1} i = n^{\varphi(n)}\prod_{d\mid n} \left(\frac{d!}{d^d}\right)^{\mu(n/d)} $$ where $\varphi$ is Euler's totient and $\mu$ is the Möbius function.

This gives you a formula that doesn't require "finding all coprimes." It probably doesn't qualify as a "fast way" to compute the exact value, since it requires computing several factorials, but it may allow you to efficiently get an approximate result e.g. using Stirling's approximation.

This is also referred to as the "Gauss factorial" and is the diagonal of OEIS A216919 where you can find additional references.