0
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ $1000001\equiv-2\pmod{1000003}$. $\endgroup$ Feb 4 '19 at 6:43
  • 2
    $\begingroup$ All of those should be mod $1000003$ - not mod the factorial. $\endgroup$
    – jmerry
    Feb 4 '19 at 6:43
  • 3
    $\begingroup$ 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 $\endgroup$ Feb 4 '19 at 6:45
  • 1
    $\begingroup$ $1000002! \equiv \pmod{100003}$ is not that exciting a remark. It doesn't need an exclamation point. $\endgroup$
    – fleablood
    Feb 4 '19 at 6:49
  • 3
    $\begingroup$ Possible duplicate of Calculate 2000! (mod 2003) $\endgroup$ Feb 4 '19 at 8:08
2
$\begingroup$

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}$$

$\endgroup$
2
$\begingroup$

Hint: $$500\,001\cdot 2\equiv -1$$

$\endgroup$
2
  • $\begingroup$ It's 1 000 003, not 100 003. $\endgroup$
    – jmerry
    Feb 4 '19 at 6:43
  • $\begingroup$ @jmerry I just recounted the zeroes and saw that. $\endgroup$
    – Arthur
    Feb 4 '19 at 6:45
1
$\begingroup$

The next step? $1000001\equiv -2\mod 1000003$. Now, you just have to divide $-1$ by $(-1)\cdot (-2)=2$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.