2
$\begingroup$

Find the Remainder when $100!$ is divided by $97^2$?

MyApproach

I applied Wilson Theorem here

$100$.$99$.$98$.$97$.$96!\text{ mod }97^2=100$.$99$.$98$.$96!\text{ mod }97=-970200$

I am getting wrong Ans

Can Anyone guide me how to approach the problem?

$\endgroup$
4
$\begingroup$

First, compute $$a=100\cdot 99\cdot 98\pmod{97},$$ then deduce that $$-a=100\cdot 99\cdot 98\cdot 96!\pmod{97}$$ and that $$-\color{red}{97}a=100!\pmod{97^{\color{red}2}}.$$

$\endgroup$
  • $\begingroup$ What is wrong in my approach? $\endgroup$ – justin takro Nov 3 '15 at 6:45
  • $\begingroup$ Your approach says $100\cdot 99\cdot 98\cdot\color{red}{97}\cdot 96!=100\cdot 99\cdot 98\cdot 96!\pmod{97^2}$, or $97x=x\pmod{97^2}$, which is not correct. To see that, take for example $x=1$. $\endgroup$ – Quang Hoang Nov 3 '15 at 6:53
  • $\begingroup$ I edited the code $\endgroup$ – justin takro Nov 3 '15 at 10:00
  • $\begingroup$ As I said above, the answer should be $97x$, not $x$. You should multiply $-970200$ by $97$ and that's the answer. $\endgroup$ – Quang Hoang Nov 3 '15 at 10:21
3
$\begingroup$

Facts:

  • $97\text{ is prime}$
  • $P\text{ is prime}\iff(P-1)!+1\equiv0\pmod{P}$
  • The remainder of $100!$ divided by $97^2$ is equivalent to $\frac{100!}{97}\bmod{97}$

Hence: $96!+1\equiv0\pmod{97}$

Hence: $96!\equiv-1\pmod{97}$

Hence: $96!\equiv96\pmod{97}$

Hence: $\frac{100!}{97}\equiv96!\cdot98\cdot99\cdot100\equiv96\cdot98\cdot99\cdot100\equiv93139200\equiv91\pmod{97}$

$\endgroup$
  • $\begingroup$ $100!$/$97$^$2$(97 raised to power 2)You took 1? $\endgroup$ – justin takro Nov 3 '15 at 9:58
  • $\begingroup$ @justintakro: No. You asked for the remainder of the quotient of $100!$ and $97^2$, so I calculated the modulo with $97$ of the quotient of $100!$ and $97$, which is the same thing. $\endgroup$ – barak manos Nov 3 '15 at 10:24
0
$\begingroup$

What you did wrong is that you did not finish the calculation:

$$ -970200 = -970291 + 91 = 97\times(-10003) + 91$

The principal remainder is therefore $91$.

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