2
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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$ $\endgroup$
    – amWhy
    Apr 27 '13 at 21:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – Julien
    Apr 28 '13 at 3:38
6
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

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

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$

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Very clear ~~~ +1 $\endgroup$
    – Amzoti
    Apr 28 '13 at 0:13

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.