Product of Gauss Factorials

The Gauss Factorial of a number $n$ is defined as the product of all positive numbers $\leq n$ that are relatively prime to $n$. For example $g(10)=1\times 3\times 7\times 9 = 189$.
Also we define
$$\displaystyle G(n) = \prod_{i=1}^{n}g(i)$$
You are given $G(10) = 23044331520000$.
Find $G(10^8)$. Give your answer modulo $1\,000\,000\,007$.

To solve this, we need to understand the way prime numbers work with respect to factorials and modular arithmetic.

Let’s start with the Gauss Factorial of a number, g(n), as the product of all positive numbers less than or equal to n that are relatively prime (coprime) to n, which means that the greatest common divisor (gcd) of these numbers and n is 1.

Using the property of multiplicative functions, we find that g(n) is multiplicative because gcd(a, b) = 1 implies that gcd(a,b,n) = gcd(a,n) * gcd(b,n) = 1. This gives way for us to break down g(n) to its prime factors.

We continue by noticing that g(p^k) for a prime number p is just the usual factorial, but subtracting multiples of p (since they aren’t coprime). This leaves us with (p^k) – (p^(k-1)).

So we have g(p^k) = (p^k – p^(k-1))!

The product formula G(n) states that G(n) is the product from i=1 to n of g(i) which naturally breaks into prime power components modulo 1,000,000,007 due to the multiplicative property.

Now, to solve for G(10^8) mod 1,000,000,007, we can break it down using the properties we just discussed!

To solve this without computation by hand, we code-wise compute independently for each prime (using sieve for primes) the factorials ((p^k – p^(k-1))!) modulo 1,000,000,007, for the maximum k value such that p^k ≤ 10^8. We use Fast Modular Exponentiation and calculate the factorials only once and store them as needed.

Computing such a calculation would particularly be cumbersome and nearly impossible by hand but the theoretic understanding provides insight into how the result could be computed using a program or high-level math software.

This kind of problem requires quite some knowledge in number theory (specifically about multiplicative functions and their properties), and experienced coding if we want the numerical result. In a normal learning context, these operations should usually be performed on computers instead of by hand, due to their computational intensity.

Therefore, note that carrying out these calculations will require advanced code-based computation, and isn’t practically feasible by raw hand calculation.

More Answers: