# Show that $1000000! \equiv 500001 \mod 1000003$

I'm working in the following exercise:

Show that $$1000000! \equiv 500001 \mod 1000003$$

Trying to find a way to apply Wilson's theorem I'm trying the following:

\begin{align*} 1000002! &\equiv -1 \mod 1000003!\\ 1000002\cdot1000001! &\equiv -1 \mod 1000003!\\ 1000002\cdot1000001\cdot1000000! &\equiv -1 \mod 1000003!\\ (-1)\cdot1000001\cdot1000000! &\equiv -1 \mod 1000003! \end{align*}

This is as close as I've been able to be to the exercise, I don't know what path to follow to reach that $$500001$$, any hint or help will be greatly appreciated.

• $1000001\equiv-2\pmod{1000003}$. – Angina Seng Feb 4 '19 at 6:43
• All of those should be mod $1000003$ - not mod the factorial. – jmerry Feb 4 '19 at 6:43
• It should also be clear that one should mention the fact that $1000003$ is a prime. - For example, with an additional digit, we have $10000000!\equiv 0\pmod {10000003}$ instead – Hagen von Eitzen Feb 4 '19 at 6:45
• $1000002! \equiv \pmod{100003}$ is not that exciting a remark. It doesn't need an exclamation point. – fleablood Feb 4 '19 at 6:49
• Possible duplicate of Calculate 2000! (mod 2003) – Jyrki Lahtonen Feb 4 '19 at 8:08

As you already noticed, $$2\cdot1000000!\equiv1000000!\cdot1000001\cdot1000002=1000002!\equiv-1\pmod{1000003}$$
Now, the inverse of 2 $$\pmod{1000003}$$ is $$\frac{1000004}{2}=500002$$. So, $$1000000!\equiv-1\cdot500002=-500002\equiv500001\pmod{1000003}$$
Hint: $$500\,001\cdot 2\equiv -1$$
The next step? $$1000001\equiv -2\mod 1000003$$. Now, you just have to divide $$-1$$ by $$(-1)\cdot (-2)=2$$.