# Calculating product of totient functions

Suppose that i need to compute product $~\phi(1) \dots \phi(n)~$ modulo prime $500009$ as fast as possible. Memory limitations are rather tough: $64$ mb so i can't just keep all the values of totient function. $n$ can be as large as $10^9$ and time given is $2$ s.

My main idea is to somehow estimate the prime factors and their exponents in factorization of this product. And then apply fast modular exponentiation. But i don't understand yet how to do such estimation.

Any ideas are highly appreciated. Thanks in advance.

P.S. This is not a hometask or a problem from a current contest. I'm just surfing number theory problem bank and solving them for fun.

Let $p=500009$ and $m=12p+1$. One possibility is to use the fact that $\phi(m) \equiv 0 \pmod{p}$, and hence it's enough to pre-calculate all values up to $m$. Storing each answer in a 32-bit integer, this is a table of size 24MB.
If you don't like pre-calculating everything, you can use in some other way the fact that only numbers below $m$ need to be considered. Be creative.
• I was trying to deduce some limit after which the product is zero modulo $p$ but didn't succeed. How did you deduce such $m$? Am i right that you were looking for the first prime of the form $kp + 1$?