# Modulo arithmetic rule

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):

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.

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.

• I'll adopt how you wrote the mod. I only did not know what instead of \pmod I could use, but didn't think about something like \text {} ;) – Zelphir Kaltstahl May 2 '17 at 11:52
• I think I get it. To multiply you used binomial rule. However, I have one thing, that I am still stuck with and which is caused probably by my awkward notation: n'p + [n mod p] = n wouldn't it have to be n'p + n equiv n (mod p) in proper notation? Because if n>p then the equation seems to be wrong. – Zelphir Kaltstahl May 2 '17 at 12:22
• $n'p+n\equiv n\pmod p$ is a tautology (always true, does not contain new information) and is not equivalent to the statement before. Maybe if I use usual notation it will become clearer. Assume $n$ divided by $p$ gives $n'$ and some remainder $r$. Written clearly, this means $n'p + r = n$. $r$ is between $0$ and $p-1$. – M. Winter May 2 '17 at 12:27
• Ah, thanks! Now I understand it. Seems much of my own confusion was because of my weird notation. – Zelphir Kaltstahl May 2 '17 at 12:35