1
$\begingroup$

I'm working in the following excercise:

Being $2011$ prime, calculate $2009!$ divided by $2011$

By Wilson's theorem I have:

$$2010! \equiv -1 \mod 2011$$ $$2009! * 2010 \equiv -1 * 2010 \mod 2011$$ $$2009! \equiv -2010 \mod 2011 $$ $$2009! \equiv 1 \mod 2011$$

Checking the answer is correct but I'm not sure about step two, is that correct? any help will be really appreciated.

$\endgroup$
  • 1
    $\begingroup$ It's perfectly correct. $\endgroup$ – Bernard Jan 30 '19 at 22:21
  • 1
    $\begingroup$ No. It's not $2009*2010 = 2010! \equiv -1 \pmod {2011}$. Why did you multiply it by $2010$ when you don't know $2009! \not \equiv -1 \pmod {2011}$. $\endgroup$ – fleablood Jan 30 '19 at 22:23
  • 1
    $\begingroup$ It should be noted that 2011 is prime $\endgroup$ – J. W. Tanner Jan 30 '19 at 22:41
  • 1
    $\begingroup$ Perhaps a lemma to wilsons thereom should be: For $p > 2$ a prime. $(p-1)! \equiv -1 \pmod p$ so $(p-2)! = -(p-2)!(-1) \equiv -(p-2)!(p-1)=-(p-1)! \equiv -(-1) \equiv 1 \pmod p$. $\endgroup$ – fleablood Jan 30 '19 at 22:49
2
$\begingroup$

No. It's not. $2009*2010 = 2010! \equiv -1 \pmod {2011}$. Why did you multiply it by $2010$ when you don't know $2009! \not \equiv -1 \pmod {2011}$.

And then when you had $2009!* 2010 \equiv -2010$ you went to $2009! \equiv -2010$ by simply dropping the $2010$ out of nowhere. You dropped it in for no reason. And then you dropped it out for no reason.

That won't work. Two wrongs frequently make a right and they did in this case. But they did so for the wrong reasons.

$$\color{blue}{2010!} \equiv \color{blue}{-1}\pmod{2011}$$

$$\color{blue}{2009!*2010}\equiv \color{blue}{-1}*\color{red}{2010} \pmod{2011}$$ (This is wrong! The blue colors are all equivalent but the red $\color{red}{2010}$ came from absolutely nowhere.)

$$\color{orange}{2009!} \equiv \color{blue}{-}\color{red}{2010}\pmod{2011}$$

(This is wrong! The $\color{blue}{2009!*2010}$ simply turned into $\color{orange}{2009!}$ for no reason! What happened to the $\color{blue}{2010}$? Where did it go?)

....

Instead do:

$2010! \equiv -1 \pmod {2011}$

$2009!*2010 = 2010! \equiv -1 \pmod {2011}$.

Now notice $2010 \equiv -1 \pmod {2011}$ so

$2009!*(-1) \equiv - 1\pmod {2011}$ and

$2009!*(-1)*(-1) \equiv (-1)(-1) \pmod {2011}$ and so

$2009! \equiv 1 \pmod {2011}$.

$\endgroup$
3
$\begingroup$

The right side on the second line should still be $-1$ because you just split the product on the left. Now note that $2010 \equiv -1 \pmod {2011}$ so multiply both sides by $2010$ $$2009! * 2010 \equiv -1 \pmod {2011}\\2009!\cdot 2010^2\equiv -1\cdot 2010 \pmod {2011}\\ 2009!\equiv 1 \pmod {2011}$$ You also just removed a factor $2010$ from the left between the second and third lines, which canceled out the error from the first to the second.

$\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.