1
$\begingroup$

Today I stumbled upon this question: Prove $\binom{2p+1}{p}\equiv2$ mod $p$ when $p$ is any prime. While reading it, I was quite surprised that the equivalence could be true, because $\binom{2p + 1}{p} = \frac{(2p + 1)!}{p! (p + 1)!}$ and the denominator includes a $p$, which should be division by zero according to my understanding.

Let me pick a simpler example: according to that question, I should have $\frac{2p}p \equiv 2 \pmod{p}$. What I say is that, according to me, $\frac{2p}p$ is division by zero, so it cannot have any result.

If I check the definition of division in modular arithmetic, I find definitions like this from stanford.edu:

$x$ divided by $y$ modulo $n$ is only defined when there is a unique $z \in \mathbb{Z}$ such that $x = yz$

In my case, the expression $x = yz$ becomes $2p = pz$, but because we are mod $p$, the expression is valid for every $z \in \mathbb{Z}$, hence there's no unique $z$, hence division is undefined.

So my question is: where is my mistake and what is the correct definition of division I should use in such cases?

$\endgroup$
1
  • $\begingroup$ $x$ modulo $y$ is uniquely defined, but there need not be a number $z\in \mathbb Z$ with $x=yz$. The mentioned definition means that $y$ divides $x$. $\endgroup$ – Peter Mar 19 '17 at 16:50
3
$\begingroup$

You're correct about the definition of division modulo $n$, but it doesn't matter - just because division and modular arithmetic are both present in the statement doesn't mean you're doing both at once. To take an analogy, dividing an integer by $2$ to get an integer only works if the original integer is even; nevertheless, it makes perfect sense to talk about $\frac{3 - 1}{2}$.

In the example you noted, it's certainly not possible to prove the claim by doing everything modulo $p$. But nothing says you have to. For example, $\frac{p}{p} \equiv 1 \mod p$, not because we can divide $p$ by $p$ mod $p$, but because we can divide $p$ by $p$ in integers and get $1$, which is $1$ mod $p$.

The crux of the matter is this: to say that $\frac{a}{b} \equiv c \mod p$ isn't saying that $\frac{a \mod p}{b \mod p} = c \mod p$. It's saying that the number obtained by dividing $a$ by $b$ (which is perfectly well-defined as long as $b$ isn't zero) has a remainder of $c$ when further divided by $p$. The technique of considering the components of an equation modulo $p$ is a useful tool, but it loses some information and therefore sometimes doesn't give an answer; in cases like that, we have to return to the original definition.

$\endgroup$
0
$\begingroup$

Of course we have to cancel $p$ in the term $2p/p$ in the ring of integers, before we take the value modulo $p$. If we write $x\equiv y \bmod p$ for integers $x$, $y$, then we first need $x\in \mathbb{Z}$. So $x=\frac{2p}{p}=2$. Now $\binom{2p+1}{p}$ is indeed an integer, because the factorials in the denominator cancel.

$\endgroup$
2
  • $\begingroup$ But I can write $\frac{2}3 \equiv 3 \pmod{7}$. Here $\frac{2}3$ is not an integer $\endgroup$ – user1807 Mar 19 '17 at 16:57
  • 1
    $\begingroup$ The question is about integers, you said, namely $2$ and $\binom{2p+1}{p}$. Of course we can generalise the modulo notation to other rings. $\endgroup$ – Dietrich Burde Mar 19 '17 at 16:58

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.