6

Please excuse me if the answer is obvious because I'm a beginner.

Why can we exchange numbers when working with modulo expressions?

For example:

$$4^2 \equiv (-1)^2 \pmod{5}$$

You may say the replacement between $4$ and $-1$ is justified because:

$$4\equiv -1 \pmod{5}$$

I understand that equality, when you divide $4$ by $5$ you get a remainder $4$ and if we subtract $5$ from that we get $-1$. But I still don't understand why we can replace $4$ with $-1$.

Furthermore if $a\equiv c \pmod{b}$ are we justified in replacing $a$ with $c$ in every occasion?

Bill Dubuque
  • 272,048
Ahmed S. Attaalla
  • 18,518
  • 1
    Use \pmod{a} to generate $\pmod{a}$. – Zain Patel Jul 10 '16 at 22:40
  • 3
    One proves a theorem, and then one uses it freely, usually without explicit mention. The general relevant theorem here is that if $a\equiv b\pmod{m}$ and $c\equiv \pmod{m}$ then $ac\equiv bd\pmod{m}$. The proof is not difficult. There is a similar theorem for addition. A consequence is that for any polynomial $P(x_1,\dots,x_n)$, if $b_i\equiv a_i\pmod{m}$ then $P(a_1,\dots,a_n)\equiv P(b_1,\dots,b_n)\pmod{m}$. – André Nicolas Jul 10 '16 at 22:58
  • Thanks for the knowledge and for editing my question @ZainPatel – Ahmed S. Attaalla Jul 10 '16 at 23:03
  • 1
    @AhmedS.Attaalla: You are welcome. As I mentioned earlier, most of the time when we use these facts we don't mention why, just like when doing arithmetic one does not give step by step justification. – André Nicolas Jul 10 '16 at 23:05

1 Answers1

3

You need the function you are dealing with to preserve multiplication. In fancier language, that means it is a homomorphism from $(\mathbb{Z},\cdot)$ to $(\mathbb{Z}/n\mathbb{Z},\cdot)$. In simpler language, that means that if $x,y$ are integers then $f(x \cdot y)=[x] \cdot [y]$, where the first $\cdot$ is integer multiplication, $[z]$ denotes the equivalence class of $z$ mod $n$, and the second $\cdot$ represents multiplication mod $n$. (Note that we often represent $[z]$ by the remainder of $z$ after division by $n$.)

For example $f : \mathbb{Z} \to \mathbb{Z}/n\mathbb{Z},f(x)=[x^2]$ is such a homomorphism, so $a^2 \equiv b^2 \mod n$ whenever $a \equiv b \mod n$. (Here $[y]$ denotes the equivalence class of $y$ mod $n$.) On the other hand, although $4 \equiv 9 \mod 5$, $2^4$ and $2^9$ are not equivalent mod 5.

Ian
  • 101,645
  • Although I don't know what that means, and have tried to understand, I will probably understand in the future. Do you happen to know when is the term "homomorphism" taught? Furthermore, is every polynomial a "homomorphism"? – Ahmed S. Attaalla Jul 10 '16 at 23:00
  • @AhmedS.Attaalla The word "homomorphism" is taught in abstract algebra. Its meaning is simple, let me edit. – Ian Jul 10 '16 at 23:01