# Quicker way to solve 10! congruent to x (mod 11)

I am new to modular arithmetic and solving congruences and the way I went about this was to write out $10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot2$, then multiply numbers until I get a number greater than $11$, replace it with a smaller number in its congruence class and repeat. Is there a quicker way to go about this? The next question I must solve is $100!\equiv x \pmod {101}$.

Wilson's Theorem states that for any prime number $n$, you get $$(n-1)! \equiv -1 (mod\ n).$$

$10!$ makes $n = 11$, which is prime, so $10! \equiv -1 (mod\ 11) \equiv 10 (mod\ 11)$

Likewise, $100!$ makes $n = 101$, which is prime, so $100! \equiv -1 (mod\ 101) \equiv 100 (mod\ 101)$.

• en.wikipedia.org/wiki/Wilson's_theorem
– Mike
Commented Nov 1, 2013 at 22:11
• Very good way of solving the problem. On an aside Wilson's theorem is an "if and only if" statement which implies that for any $n$ such that the above is true, then $n$ is prime. Commented Nov 1, 2013 at 22:27
• What about the case when n is not prime? Commented Nov 1, 2013 at 22:33
• say 101! (mod 102) Commented Nov 1, 2013 at 22:33
• @Juan If $n$ is composite and $n>4$, then $(n-1)! \equiv 0 \pmod{n}$. Commented Nov 2, 2013 at 1:52

We can pair numbers, since $$10 \equiv -1 \pmod{11}$$ $$9 \equiv -2 \pmod{11}$$

and so on. So your product is the same as

$$(-1) (-2 \cdot 2)(-3 \cdot 3)(-4 \cdot 4)(-5 \cdot 5) \pmod{11}$$

or after dealing with signs,

$$-2^2 \cdot 3^2 \cdot 4^2 \cdot 5^2 \pmod{11}$$

Now $2^2 \equiv 4$, $3^2 \equiv -2$, $4^2 \equiv 5$ and $5^2 \equiv 3$, so this can be written as

$$-(4)(-2)(5)(3) \pmod{11}$$

or $$8 \cdot 5 \cdot 3 \pmod{11}$$

Now $40 \equiv 7$ and $21 \equiv -1$ leads to

$$\boxed{-1 \pmod{11}}$$

If you don't know Wilson's theorem you might stumble upon its idea tackling this problem using elementary facts and being lazy.

The non-zero elements in $$\displaystyle \mathbb {Z} /11\mathbb {Z}$$ form a group and each element has a unique inverse. OK, listing the elements,

$$\tag 1 {\overline {1}},{\overline {2}},{\overline {3}},{\overline {4}},{\overline {5}},{\overline {6}},{\overline {7}},{\overline {8}},{\overline {9}},{\overline {10}}$$

and you get a little excited since $$10!$$ modulo $$11$$ boils down to multiplying them all together.

So an easy first step for the lazy mathematician is to replace the list with

$$\tag 2 {\overline {2}},{\overline {3}},{\overline {4}},{\overline {5}},{\overline {6}},{\overline {7}},{\overline {8}},{\overline {9}},{\overline {-1}}$$

Looking for pairs of elements, each the multiplicative inverse of the other, you wonder if you can multiply two representative numbers together and get $$12$$. Yup, $$2 \times 6 = 12$$ and $$3 \times 4 = 12$$. Great, now looking at

$$\tag 3 {\overline {5}},{\overline {7}},{\overline {8}},{\overline {9}},{\overline {-1}}$$

How about 'multiplying out' to $$23 = 12 + 11$$. Nope.

How about 'multiplying out' to $$34 = 23 + 11$$. Nope.

How about 'multiplying out' to $$45 = 34 + 11$$. Yup, $$5 \times 9 = 45$$. New list

$$\tag 4 {\overline {7}},{\overline {8}},{\overline {-1}}$$

How about 'multiplying out' to $$56 = 45 + 11$$. Yup, $$7 \times 8 = 56$$.

ANS: $$10! \equiv -1 \pmod{11}$$

Note: If $$p$$ is a prime the solutions to $$x^2 \equiv 1 \pmod{p}$$ are $$x \in \{1,-1\}$$. So with $$p \ge 5$$ the elements in the non-empty set

$$\quad \displaystyle \mathbb {Z} /p\mathbb {Z} \setminus \{{\overline {0}},{\overline {1}}, {\overline {-1}}\}$$

can be always be '$$a\text{-}b$$ paired off' with

$$\quad \displaystyle ab \equiv 1 (\text{mod } p) \land a \ne b$$