# How to show that $p!+1\equiv 1 \mod k$

I am a non mathematician who is taking a self study class in number theory. I was wondering how to formally prove the following:

Let $p$ be a prime number. How can I show that $$p!+1\equiv 1 \mod k$$ for any integer $2\le k\le p.$

• What's nice here is that $p$ doesn't have to be prime for the congruence to hold. It holds for any $p, k$ with $2\leq k \leq p$ Apr 27 '13 at 21:29
• Is there any reason why you did not write directly $p!\equiv 0$ mod $k$? If it is because you have not realized yet that you can add/subtract and multiply in modular arithmetic, then maybe that would be a place to start. Because I have the feeling that it is mainly what got you stuck. When you translate this into $k$ divides $p!$, it becomes pretty transparent why it is true. Apr 28 '13 at 3:38

What you have written is true not just for prime $p$ but for all $p$ as well. All you need to show is that $p! \equiv 0 \pmod{k}$ for $p \in \{1,2,\ldots,n\}$. Write out $p!$ as $$p! = 1 \times 2 \times 3 \times \cdots \times p$$ and now...

if $2\leq k\leq p$ then by definition $k$ is in the product $1\cdot2\dots p$. This means $k|p!$ implying $p!=kn$ for some $n\in\mathbb{Z}$. This implies $p!+1=kn+1$. Therefore what you want to show follows.

You can take away 1 from both sides and not affect the congruence.

$$p! \equiv 0 \mod k$$

Note that $$p!=p \cdot (p-1)\cdot(p-2)\cdot...\cdot3\cdot2\cdot1$$ So $p!$ is a multiple of any $2 \ge k \ge p$, so $p!$ leaves a remainder of $0$ when divided by $k$.

• I believe you mean remainder of 0; otherwise nice answer. Apr 27 '13 at 21:21
• Just fixed a typo in the third factor of p! ;-) Apr 27 '13 at 21:31
• Seems I was more tired than I thought when I typed this...
– Meow
Apr 27 '13 at 21:36
• @Alyosha That is the good response if you revise the answer. Overall, nice approach. Apr 27 '13 at 21:36

It's clear that $k$ divides $p!= 1 \times 2 \times 3 \times \cdots \times p$ if $2\leq k\leq p$ so $p!\equiv 0 \mod k$ and hence $p!+1\equiv 1 \mod k$

$$p! + 1 \equiv 1 \pmod k \iff p! + 1 - 1 \equiv 1 - 1 \pmod k \iff p! \equiv 0 \pmod k$$

$$p! \equiv 0 \pmod k \iff k \mid p\,!\tag{1}$$

Since $2 \leq k \leq p$, if follows that $k$ is one of the factors in $p!$: $$p\,! = p\times (p - 1) \times \cdots \times k \times \cdots 2 \times 1$$

That is, as a factor of $p!$, $k$ divides $p!$: $\;\;k \mid p!$.

Hence by $(1),\;$ $p! \equiv 0 \pmod k \iff p! + 1 \equiv 1 \pmod k$

• Very clear ~~~ +1 Apr 28 '13 at 0:13