Modulo arithmetic rule

Question

I remember that:

$ab \equiv n \pmod p$

can be written as:

$((a \text{ mod } p) \cdot (b \text{ mod } p)) \text{ mod } p = n \text{ mod } p$

Applying the modulo to the factors of the product and I found PDFs calling this "Homomorphic Rule" (Homomorphieregel):

http://www.math.tu-dresden.de/~ganter/inf2009/05Diskrete09Drucker.pdf http://www.math.tu-dresden.de/~ganter/inf0708/folien/inf07-Modulo.pdf

However, I cannot seem to wrap my head around why this is the case. It should even be intuitive, I think. How can I conclude that this works and remember it in an intuitive way?

I've already thought about Euklid's lemma, but don't know how to apply it to conclude what I want to conclude:

$p \mid cd \Rightarrow (p \mid c) \vee (p \mid d)$

But since there is an additional $n$ in the congruence, I think it cannot be used.

Answer 1

In this case $n \pmod p$ seems to be the remainder (Rest) operator, i.e. $n\pmod p$ is the remainder of the division $n$ divided by $p$. Stated in another way, there is an $n'$ so that

$$n'p+[n\pmod p]=n.$$

Now say we have $a,b$ and $a\pmod p$ and $b\pmod p$ are the remainders when dividing by $p$. This means there are $a',b'$ so that

\begin{align} a'p+[a\pmod p]&=a,\\ b'p+[b\pmod p]&=b. \end{align}

Let's multiply both sides to obtain

\begin{align} ab &= a'b'p^2\\ &+a'p\cdot[b\pmod p]\\ &+b'p\cdot[a\pmod p]\\ &+[a\pmod p]\cdot[b\pmod p]. \end{align}

You see that when you divide this by $p$, the first three terms divide perfectly as they are multiples of $p$. The only term that can contribute to the remainder of $ab$ divided by $p$ is the last part. Thats why

$$[ab\pmod p]=[a\pmod p]\cdot[b\pmod p].$$

As the left side is just your first line and defines $n$, the whole product on the left side is also $n$ which was exactly the equation you were asking about.

---

A word on notation: usually $\pmod p$ suggests, that the preceding equation (with an $\equiv$ sign) has to be interpreted "modulo p". This means, that the right and the left side of the equation has the same remainder when divided by $p$, but are not necessarily equal in general.

Writing $n\pmod p$ has no value (or meaning) itself, except you interpret it as the remainder itself, which is quite uncommon. One writes usually $n \text{ mod } p$ for this. I just adapted your notation for this answer but I would not suggest to use it.

General rule: $=$ means the numbers are exactly equal, while $\equiv$ means (in this case) that the remainders are equal when succeeded by $\pmod p$.

---

This equation is called homomorphy rule because it describes a ring homomorphism $\phi$ between $\Bbb Z$ and $\Bbb Z_p$, the ring consisting of the integers $0,...,p-1$ with addition and multiplication modulo $p$. When you asume $\phi(n)$ is the "remainder operator" $n\pmod p$, then the above statement can be written as

$$\phi(a\cdot b)=\phi(a)\cdot\phi(b),$$

which is a defining property of homomorphisms.