Factorial division and remainders: 100!+102! mod 100

949 Views Asked by At

I'm having some issues with factorial division. I've been asked to determine the remainder of $11!$ under division by $12$. My logic was to state that $11! = 1\cdot2\cdot3\cdot4\cdots$ stopping there as $3\cdot4=12$, thus there is a remainder of $0$. Is this correct? Is there a more math-y way of doing this?

Does my logic hold for this example: $100!+102!$ divided by $100$, where $100$ obviously divides $100!$, and $102!=102\cdot101\cdot100\cdots$ thus again there is no remainder?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes it is correct, but here exists other less descriptive ways of your proof.

$$\left(\forall n \in \mathbb{N}^{+}\right) \left(\forall a \mid n\right) \left(\exists k \in \mathbb{Z}\right) \left( n = ak \right)$$

So, $\left(100 \mid 102! \wedge 100\mid 100!\right) \Rightarrow \left(\exists k',k'' \in\mathbb{Z}\right)\left(100k' = 100! \wedge 100k'' = 102!\right)$, in accordance with this

$$100! + 102! = 100 k' + 100 k'' = 100(k'+k'') \equiv 0 \pmod{100}$$

You can also provide it other way.

$$\begin{split} \left(100 \mid 100! \wedge 100 \mid 102!\right) &\Longrightarrow \left( 100! \equiv 0 \mod{100} \wedge 102! \equiv 0 \mod{100}\right)\\ &\Longrightarrow 100! + 102! \equiv 0 \pmod{100} \end{split}$$

But it's just other words for that.


We should note, that $100 \mid 100! \wedge 100 \mid 102!$. In fact you didn't have to write so much to prove it ($102! = 102 \cdot 101 \cdot 100 \cdot 99! \Rightarrow 100 \mid 102!$) what if I ask about 1234!? We should note simple fact here.

$$\left(\forall n \in \mathbb{N}^{+}\right)\left(\forall a' \in \mathbb{N}^{+}\right) \left(a' \leq n \Longrightarrow a' \mid n!\right)$$

I think it's obvious, because $n! = 1 \cdot 2 \cdot 3 \cdot ... \cdot n$. Problematic can be question, if $291 \mid 100!$? But we can note $291 = 97 \cdot 3$, and $3,97 < 100 \wedge 3 \neq 97 $ so yes.