modular arithmetic solving technique

I do know that the (mod m) in
$a\equiv b\pmod m$ is not a multiplication with b, so, the following question has really confused me:

The given values are:
$a\equiv 4\ mod 13$ and $b\equiv 9\ mod 13$, now, we find the integer
0<= c <=12 such that : $c\equiv 9a\ (mod 13)$

Now, the solution is given as:

9 . 4 (mod 13) = 36 mod 13 = 10

I can see that (a mod 13) is being replaced with it's value from the given, but, if that's then how is a(mod 13) not being treated as a separate unit after replacement? It should had been indivisible, because it ought to be the multiplication of 9*a then the modulo 13. Especially this matters because, (9*a)mod13 != 9*(a mod 13)

Just to clarify, the answer from what I see should have been 36, but it's not so, because I do know (9*a)mod13 != 9*(a mod 13)

Answer

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.