0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 {} ;) $\endgroup$ – Zelphir Kaltstahl May 2 '17 at 11:52
  • $\begingroup$ 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. $\endgroup$ – Zelphir Kaltstahl May 2 '17 at 12:22
  • 1
    $\begingroup$ $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$. $\endgroup$ – M. Winter May 2 '17 at 12:27
  • $\begingroup$ Ah, thanks! Now I understand it. Seems much of my own confusion was because of my weird notation. $\endgroup$ – Zelphir Kaltstahl May 2 '17 at 12:35

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.