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$
  • 2
    $\begingroup$ $1000001\equiv-2\pmod{1000003}$. $\endgroup$ – Angina Seng 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$ – Hagen von Eitzen 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$ – Jyrki Lahtonen 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}$$

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\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$.

| cite | improve this answer | |
$\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.