Let $~p~$ be prime and $~n~$ some positive integer below $~10^9$. Is there an efficient way to compute product $~ \phi(1) \cdots \phi(n) \mod p~$? It is known that $~p > \sqrt{n}~$ (i don't know if this somehow can help). I know how to compute values $~\phi(1), \cdots, \phi(n)~$ using sieve but memory limitations are too strict to keep them all. Isn't there more efficient approach when we need to deal with such product? May be there is some nice formula for it?

Thanks in advance for any ideas.

P.P.S. The original problem is http://www.e-olymp.com/en/problems/3243

  • $\begingroup$ You are incorrect on one point: if $n = 2p$ for some prime $p \geq 3,$ then $p > \sqrt n.$ Where did you come upon this problem? $\endgroup$ – Will Jagy Mar 19 '16 at 0:39
  • $\begingroup$ Nope, i'm right. In your example $\phi(2p) = p - 1 \not\equiv 0 \mod p$ $\endgroup$ – Igor Mar 19 '16 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.