# 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)

• $(a \mod 13)$ is not a number. $a \mod 13$ is a reference to a characteristic-- that $a$ is a representative of the equivalence class of integers {x} so that $x = a + 13*k; k \in \mathbb Z$. The expression $9*(a \mod 13)$ is utterly meaningless. And if you mean, $a \mod 13 = [a]$ where $[x] =\{x|x = a + k*13; k \in \mathbb Z\}$. then $9*[a] = \{9x|x = a + k*13; k \in \mathbb Z\}$. Then indeed, YES, $9*[a] = [9*a] = \{x|x = 9a + k*13\in \mathbb Z\}$. – fleablood Feb 28 '18 at 17:12
• @fleablood , still very much confused – mathmaniage Feb 28 '18 at 17:28
• Why do you think $(9a) \mod 13 \ne 9*(a \mod 13)$. Take $a = 15$. Don't you agree that $135 \mod 13= 9*(2\mod 13)=18\mod 13$? If not, why not? Isn't $135 = 18 + 13k$ for $k = 9$. – fleablood Feb 28 '18 at 17:33
• ok (9*15)= 135 and now mod 13 is equal to 5 , and again, 15 mod 13 is 2 and (9*2)=18 – mathmaniage Feb 28 '18 at 17:38
• So, all the mods are already used up, but it's as if you tell to use them again. – mathmaniage Feb 28 '18 at 17:39

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.$ = \{...,-2n, -n, 0, n, 2n, 3n\} = \{x\in \mathbb Z| x = kx$for some integer$k\} = \{$all multiples of$n\}$.$ = \{...,-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\}$.$ = \{...,-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 $and$n+3\in $we can refer to$$as$[n+3]$and they'll both be the same set. In other words,$ = [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$\{,,...... [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.

• @Could you explain also in conjunction with the original question at hand, how is the replacing being done? And how does think them as set solve the issue? – mathmaniage Feb 28 '18 at 17:35
• I don't understand your concern. $a \equiv 4 \mod 13$ means $a = 4 + 13k$. and $c \equiv 9a \mod 13$ means $c = 9a + 13j$. So $c = 9(4+13k) + 13j = 9*4 + 13(9k + j) \equiv 4*9$. So $c \equiv 4*9 \mod 13$. – fleablood Feb 28 '18 at 17:41
• Thinking of them as numbers and not as sets means that you take the number 36 and "mod 13" it to get 10 and ten is a new number and you multiply that by 2 you get 20. and 20 isn't 7 and 10 isn't 36. They are the results of "mod 13". THIS IS WRONG! If you think of them as sets then 36 is the set {...,10,23,36,...} you multiply these be 2 ans take the equivalence classes , you , get the set {...7,20,33,46,59,72,....} you see they are always the same thing. – fleablood Feb 28 '18 at 18:10
• I get what is being said, but one last question, why is a mod d being defined as: a mo d = (a-floor(a/d)*d)? Source: K. Rosen 's book on discrete maths. – mathmaniage Mar 2 '18 at 17:05
• It doesn't matter that $(9a) \mod 13 \ne 9(a \mod 13)$. WHat matters is that $(9a) \mod 13 \equiv 9(a\mod 13)$ or in other words $](9a) \mod 13]\mod 13 = [9(a\mod 13)]\mod 13$. No-one gives flying hoot what $a \mod n$ actually IS. We only care about what $a \mod n$ is equivalent to. And: if $a \equiv b \mod n$ and $c \equiv d \mod n$ then $ac \equiv bc \mod n$. Very easy to prove. – fleablood Mar 2 '18 at 18:05

I would say $(9a) \mod 13$ is equal to $9 (a \mod 13)$, though the second should probably be avoided since is is confusing. The $\mod 13$ means you are working in a number system with numbers $\{0,1, 2, \dots, 12\}$. It makes perfect sense to multiply these with any integer, and get another number in $\{0,1, 2, \dots, 12\}$.

• $\Bbb Z_{13} \neq \{0; 1; 2; \dots; 12\}$ !! – krirkrirk Feb 28 '18 at 17:24
• @Jonathan, if it means that I'm working with a number system with <13 values, and all integers, then, it makes no sense to replace the values from given – mathmaniage Feb 28 '18 at 17:29
• @mathmaniage you are not working with integers here. – krirkrirk Feb 28 '18 at 17:35
• a set? well, I don't relate what's the answer, we're sort of treating them as numbers and yet, people say we arent. – mathmaniage Feb 28 '18 at 17:36
• @Jonathan then write $\Bbb Z_{13} = \{\overline {0}, \dots \overline {12} \}$ but you really should avoid saying those are integers : you'll end up with confusions like OP's ones. – krirkrirk Feb 28 '18 at 17:53

Ok reading multiplle eyebursting resources daily, I've found another approach to explaining this stuff, dear fellows, please check this, I think it's pretty resonable:

Given: $a\equiv 4\ mod 13$
$c\equiv 9a\ mod 13$ means that 9 can be multiplied by 4 at most. So,

=> $c\equiv [9.[4mod13]]\ mod 13$
=>$c\equiv (9.4)\ mod 13$
=>$c\equiv 36\ mod 13$ which is 10.

now if you wonder how the value of c is 10, then just to stop you pondering:
$x\equiv x\ mod n$ which is obviously verifiable.

Thanks to the above answers.

• Your notation is non-standard (and might lose you points on a homework assignment). I have never seen things like $[9.[4 mod 13]] mod 13$ written. However your logic is correct. In my opinion, a better way to think of this (and write it) is that since $a \equiv 4 mod 13$, $a$ equals $4$ (in the mod 13 number system). So $9a = 9 \cdot 4=36=10$ (in the mod 13 number system), which more commonly gets expressed $9 a \equiv 9 \cdot 4 \equiv 36 \equiv 10 \mod 13$. – Jonathan Mar 3 '18 at 17:29