How do I solve this divisibility problem?

151 Views Asked by At

Question 23: Which one of following statements holds true if and only if $n$ is a prime number? $$ \begin{alignat}{2} &\text{(A)} &\quad n|(n-1)!+1 \\ &\text{(B)} &\quad n|(n-1)!-1 \\ &\text{(C)} &\quad n|(n+1)!-1 \\ &\text{(D)} &\quad n|(n+1)!+1 \end{alignat} $$

I ruled out choices C and D because $n$ is a natural factor of $(n+1)!$, so $n$ won't divide $n(n+1)! -1 $ or $n(n+1)!+1 $(that could be the case if $n$ is $1$ but this question concerns only primes).
I would like to know how to choose between choices A and B. Alternative ways to approach the problem are equally welcome.

2

There are 2 best solutions below

0
On BEST ANSWER

Contrary to what is suggested in the other answer, it is better to gain at least a basic understanding of the material.

This is Wilson's Theorem, which states that if $p$ is a prime number, then $(p-1)!\equiv-1\bmod p$.

For $p=2$ or $p=3$, this is verified by direct computation. For larger $p$, every factor in $(p-1)!=1×2×3×...×(p-1)$ except $1$ and $p-1$ is paired with its multiplicative inverse which is another one of the factors. For instance, with $p=5$ the factor $2$ is paired with $3$; with $p=7$ we pair $2$ with $4$ and $3$ with $5$. These multiplicative-inverse pairs then each have product $1\bmod p$, so the factorial including all factors must be $(p-1)\equiv-1\bmod p$.

Thus (a).

0
On

Given that it's a multiple choice question, and you're not required to present an actual proof, you can proceed by elimination. Which of the following are true:

3|2!+1
3|2!-1
3|4!+1
3|4!-1