Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $p$ be a prime and r an integer, $0 < r < p$. Show that $\frac{(p-1)!}{r!(p-r)!}$ is an integer.


The given number is $ \frac{\binom {p} {r}}{p}$. after tha how can I show that$p$ divides the given binomial coefficient. can somebody help me please.

share|improve this question
add comment

5 Answers 5

Write

$$p!=r! \cdot (p-r)! \cdot \binom{p}{r}$$

Since $p|p!$ then $p| r! \cdot (p-r)! \cdot \binom{p}{r}$. Using the fact that $p$ is prime you get

$$p|r! \, \mbox{or} \, p| (p-r)! \, \mbox{or} \, p|\binom{p}{r}$$

Now, the first two options cannot be true, thus....

share|improve this answer
add comment

Look at the factors in the denominator - which of these can have a common factor with $p$? - Use that $p$ is prime and you have a factorisation of the denominator into integers less than $p$.

share|improve this answer
add comment

Let your number be $q$.

Since $\gcd(r,p) = 1$, we have that there are integers $a,b$ such that $ar + bp = 1$.

Muliplying by $q$, and we get

$$a (qr) + b (pq) = q$$

Now $qr = \binom{p-1}{r-1}$ and $pq = \binom{p}{r}$, thus $q$ is an integer.

Another method is to use the fact that

$$(1+x)^p = 1 + x$$

in $F_p[x]$

share|improve this answer
add comment

Using this, $r! (p-r)!$ divides $p!$ for $1\le r<p$

$\implies r! (p-r)!$ divides $(p-1)!$ as $(p,r)=1$ for $1\le r<p$

share|improve this answer
add comment

Let $p$ be a prime and let $0<r<p$. Then $b(p,r)=\binom{p}{r}$ is an integer, because it is a binomial coefficient (which appears as a coefficient of $x^r$ in $(1+x)^p$). Moreover, $$b(p,r)=\binom{p}{r} = \frac{p!}{r!(p-r)!} = \frac{p \cdot (p-1)!}{r!(p-r)!}.$$ Since $0<r<p$, neither $r!$ nor $(p-r)!$ have a factor of $p$. Hence $p$ only appears in the numerator of the expression for $b(p,r)$, and it follows that the integer $b(p,r)$ is a multiple of $p$ or, in other words, the expression $$\frac{b(p,r)}{p}=\frac{(p-1)!}{r!(p-r)!}$$ is also an integer.

PS: The formal justification of the last step is as follows. The identity of integers $$b(p,r) \cdot r!\cdot (p-r)! = p \cdot (p-1)!$$ implies that $p$ divides the left-hand side $b(p,r)\cdot (r!(p-r)!)$. Since $p$ is prime, it divides one of the two factors: $b(p,r)$ or $r!(p-r)!$. But $0<r<p$ implies that $p$ does not divide $r!$ nor $(p-r)!$, and so $p$ is a divisor of $b(p,r)$. This means that $b(p,r)/p$ is an integer.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.