0
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ $(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\}$. $\endgroup$ – fleablood Feb 28 '18 at 17:12
  • $\begingroup$ @fleablood , still very much confused $\endgroup$ – mathmaniage Feb 28 '18 at 17:28
  • $\begingroup$ 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$. $\endgroup$ – fleablood Feb 28 '18 at 17:33
  • $\begingroup$ ok (9*15)= 135 and now mod 13 is equal to 5 , and again, 15 mod 13 is 2 and (9*2)=18 $\endgroup$ – mathmaniage Feb 28 '18 at 17:38
  • $\begingroup$ So, all the mods are already used up, but it's as if you tell to use them again. $\endgroup$ – mathmaniage Feb 28 '18 at 17:39
2
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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? $\endgroup$ – mathmaniage Feb 28 '18 at 17:35
  • $\begingroup$ 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$. $\endgroup$ – fleablood Feb 28 '18 at 17:41
  • $\begingroup$ 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. $\endgroup$ – fleablood Feb 28 '18 at 18:10
  • $\begingroup$ 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. $\endgroup$ – mathmaniage Mar 2 '18 at 17:05
  • 1
    $\begingroup$ 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. $\endgroup$ – fleablood Mar 2 '18 at 18:05
1
$\begingroup$

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\}$.

$\endgroup$
  • $\begingroup$ $\Bbb Z_{13} \neq \{0; 1; 2; \dots; 12\} $ !! $\endgroup$ – krirkrirk Feb 28 '18 at 17:24
  • $\begingroup$ @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 $\endgroup$ – mathmaniage Feb 28 '18 at 17:29
  • $\begingroup$ @mathmaniage you are not working with integers here. $\endgroup$ – krirkrirk Feb 28 '18 at 17:35
  • $\begingroup$ 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. $\endgroup$ – mathmaniage Feb 28 '18 at 17:36
  • 1
    $\begingroup$ @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. $\endgroup$ – krirkrirk Feb 28 '18 at 17:53
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Jonathan Mar 3 '18 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.