1
$\begingroup$

Find the remainder when $99!+99$ is divided by $100$

I think I'm suppose to use either Wilson's or Fermat's theorem however, both 99 and 100 are not prime numbers so I can't use their formulas

$\endgroup$

4 Answers 4

8
$\begingroup$

hint-- $99!$ is $0$ mod $100.$

$\endgroup$
2
  • $\begingroup$ I have a question, why does 99! is 0mod100 but 42! is -1(mod43). Is it because 43 is a prime and 100 is not? $\endgroup$
    – Kayy Wang
    Feb 6, 2019 at 15:41
  • $\begingroup$ Basically right. $43$ is a prime so doesn't divide evenly any number less than it, and only those numbers are factors of $42!$ In fact more precisely one has if $p$ prime that $(p-1)!$ is $-1$ mod $p,$ see Wilson's theorem via a google. [because it's prime, if it divided the factorial it would have to divide one of its factors.] $\endgroup$
    – coffeemath
    Feb 6, 2019 at 16:10
5
$\begingroup$

$99! = 1*\color{red}2*3*4*.....*47*48*49*\color{red}{50}*51*....* 99$ so .......

$100|99!$

So $99! + 99 \equiv 99 \pmod {100}$.

=====

Note: Wilson theorem is powerful if $n$ is prime. But if $n$ is not prime the equivalent is ... stupid.

If $n = j*k$ and $j< k$ then $(n-1)! = \prod_{m<n} m = (jk)*\prod_{m< n; m\ne j; n\ne k} m$ so $(n-1)! \equiv 0 \pmod n$.

And if $n = p^2$ where $p> 2$ is prime. Then $(n-1)! = \prod_{m<n} m = 2p^2*\prod_{m< n; m\ne p; m\ne 2p} m$ so $(n-1)! \equiv 0 \pmod n$.

If if $n = 4$ then well, then we have $3! = 6\equiv 2 \pmod 4$ but that's a single case.

$(n-1)! \equiv 0 \pmod n$ unless $n$ is prime, in which case you have Wilson's Th. or $n= 4$ in which case $3! \equiv 2 \pmod 4$.

It's ... that easy.

$\endgroup$
0
3
$\begingroup$

$100|98! \implies 98!+1 \equiv 1 \text{mod} 100 \implies 99(98!+1) \equiv 99 \text{mod} 100$

$\endgroup$
1
$\begingroup$

Since $2\cdot 5\cdot 10 = 100$ is a divisor of $99!$, it follows that $99!\equiv 0\mod 100$ and so $99!+99\equiv 99 \mod 100$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .