0

I'm reading the Wiki page on congruence relation and am trying to figure out

"Do I take the mod(x) before or after the addition or multiplication operation"

BTW - When I tried to figure this out on my own, I realized that n in mod n would be congruent all it's factors, but if n was prime (say 3 or 5) I wasn't sure of the order of operations for doing simple algebra.

Can someone fill in the blanks of what a sample a` (prime) value would be on the right hand side of the congruent sign?

makerofthings7
  • 567
  • Your question is rather confusing. Can you give a concrete example of what you don't understand? – EuYu Oct 22 '13 at 12:09
  • @euyu I don't know how to write the symbols, but in the Wiki article "basic sample" there is an equation prefaced by the text Congruence modulo n (for a fixed n) is compatible with both addition and multiplication on the integers. That is, if ... how is a' computed? ... when do I take the mod(n) .. before or after the sum or the product? – makerofthings7 Oct 22 '13 at 12:15
  • I think I see what you are getting at now. Let me write something up and hopefully that'll answer a few questions. – EuYu Oct 22 '13 at 12:24

1 Answers1

2

The $a$ in the equation $$a\equiv b \pmod n\tag{*}$$ is simply the integer $a$. The congruence above establishes a relationship between the forms of $a$ and $b$. We say that two integers are congruent to each other modulo $n$ precisely when $n\mid a-b$. From this, it follows that for a fixed integer $a$, we can write the set of all integers congruent to $a$ modulo $n$ as $$[a]_n = \{a,\ a\pm n,\ a\pm 2n,\ a\pm 3n,\ \cdots\}$$ The set $[a]_n$ is called the congruence class of $a$ modulo $n$. The total number of distinct congruence classes is finite. In fact, $$\{[0]_n,\ [1]_n,\ \cdots,\ [n-1]_n\}\tag{**}$$ forms the complete set of congruence classes.

In this language, equation $*$ says that $a$ and $b$ belong in the same congruence class. Modular arithmetic is really an algebraic system working with congruence classes of integers rather than the integers themselves. When working with equations in modular arithmetic, we are therefore free to replace any integer with any member of its congruence class. Since any integer necessarily belongs to one of the congruence classes in equation $**$, we typically pick one of the integers between $0$ and $n-1$ as a representative of the congruence class. This representative is the remainder of the number when divided by $n$ or the value of the modulo operator $a \% n$.

In practice, we always reduce any formula in terms of these (or other convenient) representatives.

Let's look at an example with some arbitrary numbers. We know that $849 \equiv 9 \pmod {10}$ and $3483 \equiv 3 \pmod {10}$ and so we are free to replace $849$ by $9$ and $3483$ by $3$ in any equations where they occur. For example so we can say that $$849 + 3483 \equiv 9 + 3 \equiv 12 \equiv 2\pmod{10}$$ or that $$849\times 3483 \equiv 9\times 3 \equiv 27 \equiv 7\pmod{10}$$ When viewed in this manner, the question of "order" disappears. It doesn't matter whether you add first and then reduce or reduce first and then add because the underlying congruence classes do not change but rather your choice of integers representing them.

EuYu
  • 41,421
  • I got lost at $n\mid a-b$ ... will try to keep reading and see if I can infer what the pipe symbol means (unless it's logical bitwise OR). EDIT: I intuitively know what it means from the expanded A sample, but would love to know exactly what it's called. – makerofthings7 Oct 22 '13 at 15:41
  • w.r.t. "order of operations" in your final sample you have $9\times 3\equiv 27 \equiv 7\pmod{10}$ why is it not written as $9\pmod{10} \times 3 \pmod{10} \equiv 27\pmod{10} \equiv 7\pmod{10}$ ... in other words, when looking at one half of a congruence it's not immediately clear if $\pmod{10}$ has been applied or not. – makerofthings7 Oct 22 '13 at 15:50
  • @makerofthings7 The pipe symbol is divides. With respect to your last question, what exactly do you mean by $9 \pmod{10}$ or $3 \pmod{10}$? Note that $a \pmod{n}$ is not the same as the modulus operator in computer science $a%n$. The $\pmod n$ symbol is not an operator that you apply, it's an indicator that we are working in modular arithmetic. – EuYu Oct 22 '13 at 18:06
  • Yes, I'm coming from a CompSci background. So (mod n) is a descriptor for all congruent symbols near it. (in this case on the same horizontal line). (also please pardon me if I seem pedantic, I just want to "get it right") – makerofthings7 Oct 22 '13 at 18:25
  • 1
    @makerofthings7 Yes $\pmod n$ is just a descriptor for the congruence relation. We can write $a \equiv b \pmod n$ as $a\equiv_n b$ for example. This is just a change of notation, but I think it illustrates the fact that the $\pmod n$ symbol really doesn't do anything. – EuYu Oct 22 '13 at 19:11