17
$\begingroup$

Let $p$ be a prime larger than $7$. What is the remainder when $p!$ is divided by $p+1$?

I tried plugging in the next prime (11), which doesn't help with such big numbers. Then I tried writing $\frac{p!}{p+1} = p(p-1)(p-2).../(p+1)$. Dividing each of $p$, $(p-1)$ etc individually by $(p+1)$, I always get $(p+1)$ as a remainder, and multiplying all those remainders together and dividing again by $p+1$ will give $0$, which I'm not sure is right. How can I solve this?

$\endgroup$
  • 2
    $\begingroup$ Hint: Consider the prime factorisation of $p+1$ $\endgroup$ – Mark Bennet Sep 16 '17 at 9:52
  • 2
    $\begingroup$ $p=5$ and $p=7$ work too. $\endgroup$ – user228113 Sep 16 '17 at 9:54
  • $\begingroup$ You seem to post (what looks like) your homework on here rather frequently.… $\endgroup$ – gen-z ready to perish Sep 16 '17 at 11:15
  • 1
    $\begingroup$ Actually, they're not. I do them for fun :) $\endgroup$ – space Sep 16 '17 at 12:35
16
$\begingroup$

Hint: Both $2$ and $(p+1)/2$ appear as factors in $p!$.

$\endgroup$
  • 1
    $\begingroup$ ah... so the denominator wholly cancels out and leaves a remainder of 0, am I right? $\endgroup$ – space Sep 16 '17 at 10:13
  • 3
    $\begingroup$ Correct, @Helena. You do need $p>3$ because for $p=3$ we have $2=(p+1)/2$, and these two factors won't appear in $p!$ separately. $\endgroup$ – Jyrki Lahtonen Sep 16 '17 at 10:15
  • 3
    $\begingroup$ Your (hinted) proof shows that, actually, one can relax the requirement to "Let $p$ be an odd integer larger than 3". $\endgroup$ – Luca Citi Sep 16 '17 at 12:56
6
$\begingroup$

Remember that if $p > 7$, then $p! = 1 \times 2 \times 3 \times \ldots \times (p - 1) \times p$.

The smallest prime factor of $p + 1$ is less than $\sqrt{p + 1}$ and clearly $\lceil \sqrt{p + 1} \rceil < p$. The largest prime factor of $p + 1$ is at most $\frac{p + 1}{2}$, which is also less than $p$.

This means that all the prime factors of $p + 1$ are included among the prime factors of $p!$, and in greater numbers. Therefore $(p + 1) \mid p!$.

For example, given $p = 11$, we have $p! = 39916800 = 2^8 \times 3^4 \times 5^2 \times 7 \times 11$. By contrast, $p + 1 = 12 = 2^2 \times 3^{(1)}$, so $$\frac{39916800}{12} = 3326400 = 2^6 \times 3^3 \times 5^2 \times 7 \times 11.$$

$\endgroup$
  • $\begingroup$ I think you need to exercise a bit more care. When $p=3$ all the prime factors of $p+1=4$ are included in the prime factors of $p!=6$ yet $4$ is not a factor of $6$. This does not happen with larger $p$, but an answer should explain why that is the case. $\endgroup$ – Jyrki Lahtonen Sep 17 '17 at 21:15
  • 2
    $\begingroup$ @JyrkiLahtonen By contrast I take issue with the first line, in which the second clause applies even when $p < 7$. $\endgroup$ – Mr. Brooks Sep 18 '17 at 21:42
4
$\begingroup$

$p+1$ won't be a prime number. So $p+1=ab$ where $2\le a\le b\le p$. Obviously $a$ divides $p!$ and $b$ divides $p!$. Is it obvious that $ab$ divides $p!$? Is it even true?

$\endgroup$
  • 1
    $\begingroup$ A small bias: this reasoning can be done for $p=3$ as well, but the result does not hold for that. The reason being that $3+1$ is the square of a prime, so the only options appear with $a=b$. $\endgroup$ – user228113 Sep 16 '17 at 9:55

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.