Argh... Apparently K. Rosen defines $a \mod n$ in a subtly but very different way then I do.
I definne $a \mod n$ to mean nothing in itself but just to mean "with respect to the equivalence modulo $d$". To numbers $a$ and $b$ are equivalent modulo $n$ if $n|a-b$. That relationship between integers is an equivalence relationship. (To get pedantic that means every $a$ is related to itself, if $a$ is related to $b$ then $b$ is related to $a$. , if $a$ is related to $b$ and $b$ is related to $c$ then $a$ is related to $c$. But informally, that means, in respect to this property [having their differences being divisible by $n$] thetwo numbers are intercchangeable and can, for all intents and purposes, be considered to be the same.)
K. Rosen apparently defines $a \mod n$ be be an operation that gives , as a result, the remainder when you divide $a$ by $n$. As such you are correct that $(4*9) \mod 13 = 10$ and $4*(9 \mod 13) = 39$ and $36 \ne 10$. However notice that in the example you give "$\equiv$" (with 3 lines) is not the equal sign "$=$" (with 2 lines).
$\equiv $ is the equivalence sign. And $36 \equiv 10 \mod 13$ means that $36$ although not equal to $10$ is equivalent to $10$ and in the arithmetic system of modulo 13, $36$ and $10$ are interchangable.
The equivalence relationship is defined as $a \equiv b \iff a \mod n = b\mod n$. Note that means $a \equiv b \iff a\equiv b \mod n \iff b \equiv a \mod n$.
Rosen's approach and mine lead to the exact same results.
ANyhow so using Rosen's definitions: $4*9 = 36$ and $36 \mod 13 = 10$ and $10 \mod 13 = 10$. And $9 \mod 13 = 9$. So $36 =4*9 = 4*(9 \mod 13) \equiv (4*9) \mod 13 = 36 \mod 13 = 10$
=== old answer =====
Complete Redo:
"We can do arithmetic on remainders" and $a \equiv b \mod n" can be interpreted in four different way; two are correct, one is sort of correct but technically it's wrong but it's so convenient we pretend it is correct, and the fourth is dead outright flat WRONG.
1) $a \equiv b \mod n$
is simply a statement about two numbers $a$ and $b$. It means i) the difference between the two numbers is divisible by $n$. (i.e. $n\mid (a - b)$ ,or in other words ii) the difference is a multiple of $n$. (i.e. $a - b = kn$ for some $k \in \mathbb Z$), or in other words iii) one is equal to the other plus or minus a multiple of $n$. (i.e. $a = b + kn$ for some $k \in \mathbb Z$).
The advantage to this is it is very simple. Perhaps too simple. Students aren't likely to see how important this is. Also it misses/avoids the point that $a$ and $b$ aren't just related, there are equivalent in one respect and are interchangeable with each other.
2) $a \equiv b \mod n$
read this as "$a$ is equivalent to $b$ with respect to modulus $n$".
We can divide $\mathbb Z$ into $n$ separate and complete classes depending on how $n$ divides into all the integers.
$[0] = \{...,-2n, -n, 0, n, 2n, 3n\} = \{x\in \mathbb Z| x = kx$ for some integer $k\} = \{$ all multiples of $n\}$.
$[1] = \{...,-2n+1, -n+1, 1, n+1, 2n+1, 3n+1\} = \{x\in \mathbb Z| x = kx+1$ for some integer $k\} = \{$ all integers that will have a remainder of $1$ when divided by $n\}$.
$[2] = \{...,-2n+2, -n+2, 2, n+2, 2n+2, 3n+2\} = \{x\in \mathbb Z| x = kx+2$ for some integer $k\} = \{$ all integers that will have a remainder of $2$ when divided by $n\}$.
......
$[n-1] = \{...,-2n-1, -n-1, -1, n-1, 2n-1, 3n-1\} = \{x\in \mathbb Z| x = kx-1$ for some integer $k\} = \{$ all integers that will have a remainder of $n-1$ when divided by $n\}$.
$a \equiv b \mod n$ means that if $a \in [k]$ then $b \in [k]$ as well. They both are in the same equivalence class.
We can represent each class by any representative integer in them. Since $3 \in [3]$ and $n+3\in [3]$ we can refer to $[3]$ as $[n+3]$ and they'll both be the same set. In other words, $[3] = [n+3]$.
The advantage to this is that it is more thorough and does give the idea that $a \equiv b \mod n$ is an equivalence relationship.
The disadvantage is that it is very abstract and confusing. It gives the student this is a very complicated procedure when it is is really very simple.
3) Is the way I learned and to my mind makes the most intuitive sense.
Consider $\mathbb Z_{13} = \{0,1,2,3,4,5,6,7,8,9,10,11,12\}$. These are just like the regular integers except there are only $13$ of them instead of an infinite number of them. The other difference is that "loop over' when we count. Instead of counting $...,10,11,12,13,14,15...$, we count $...,10,11,12,0,1,2,....$.
Since the numbers loop we can have many ways to refer to an number. If we count to $15$ we "loop around" so that $15 = 2 = 28 = 41 =.....$.
So $a \equiv b \mod n$ simply means $a = b$ if we are using the $\mathbb Z_n$ arithmetic system.
The advantage to this is it is EASY! And it gets across that $a$ and $b$ are equivalent and interchangable and it's very clear we can do arithmetic in this number system.
The disadvantage is that it is incorrect. $a$ and $b$ aren't the same thing in some different number system. $a$ and $b$ are two different numbers which are equivalent to each other in a specific equivalence relationship. (The relationship is that $a$~$b$ if $n|(a-b)$.)
We can actually fixe this by noticing that if we think of the $n$ equivalence sets in 2) as individual things in their own right then $\{[0],[1],...... [n-1]\}$ turns out to work the same way as $\mathbb Z_n$.
The trouble with that is very abstract and will go over any students head.
4) Let $a \%n $ be the operation of taking the remainder of $a$ when dividing by $n$. That is you take two numbers and you get a third by doing an operation on them.
So $a \mod n$ means the remainder you get when you divide $a$ by $n$. So $36 \mod 13 = 10$.
THIS IS WRONG!!!! VERY VERY WRONG!!!!!
$\mod n$ is NOT an operation but a statement about how to consider two numbers to be equivalent.
Just don't do this. Don't.
...
So if $a \equiv 4 \mod 13$ and $b \equiv 9 \mod 13$ then $a*b \equiv 4*9 \mod 13 \equiv 36\equiv 10 \mod 13$.
That is true.
Let's look at them in terms of the four interpretations.
1) $a \equiv 4 \mod 13 \implies 13\mid a-4 \implies $a = 4 + 13k$. $b \equiv 9 \mod 13\implies 13|b-9\implies b = 13j.$
So $ab = (4+13k)(9+13j) = 36 + 9*13k + 4*13 j + 13^2 kj = 36 + 13(9k + 4j + 13kj)$. So $ab \equiv 36 \mod 13$.And $36 + 13(9k + 4j + 13kj) = 10 + 13(9k + 4j + 13kj + 1)$. So $ab \equiv 10 \mod 13$.
2) $a \equiv 4\mod 13 \implies a \in \{..., 4, 17,30,....\}$ and $b \equiv 9 \mod 13 \implies b \in \{...., 9, 22,35,48,....\}$. And $ab \in \{-3, 10, 23, 36, 49, ...\}$. (We can prove that by doing what we did ni 1). so $ab \equiv 10 \equiv 36 \mod 13$.
3) $a \equiv 4 \mod 13$ means we count to $a$ by looping around $13$ and ending at $4$ so $a = 4$ and the same thing for $b \equiv 9\mod 13$. So $a*b = 4*9 = 36$ and if we count to $36$ we loop around and end up at $10$.
4) $a\equiv 4 \mod 13$ means $a \% 13=$ the remainder $= 4$. and $b \equiv 9 \mod 13$ means $b\% 13 = 9$. So $(a*b)\% 13 = ((a\%13)*(b\% 13))\%13$. That's an interesting result but not useful in applying to a great picture about the behavior of integers as a class. And typing those nested and repeated operations to make it true is a pain.
