11x - 7 = 0 (mod 13), What is this?

Question

The answer is 11x/13 = 13n + 3, for n = 0,1,2,3

But what is that (mod 13) means. Does this mean that you are taking the mod on both side of the equation or what?

This is very standard notation...see this article, for example, for a discussion. — lulu, Oct 11 '18 at 16:37
This is essentially just stating that 11X-7 is a multiple of 13. If it said 1 (mod 13), then you'd be looking for a number that is one greater than a multiple of 13. If it said 11 (mod 13), you'd be looking for a number that is 11 greater than a multiple of 13. Obviously if something is, say, 14 (mod 13), then it is the same thing as 1 mod(13) — , Oct 11 '18 at 16:50
I'm guessing that you learned about mod in a "discrete math for computer science" course where they treat it as a binary operation in a computer language, but in math, it means something else. It's an equivalence relation, and the equation $x\equiv y\pmod{z}$ means that $x$ and $y$ have the same remainder on division by $z$, or equivalently, $(x-y)$ is divisible by $z$. In the terms you've learned, yes, the mods of both sides are equal. — saulspatz, Oct 11 '18 at 17:03

score 2 · Answer 1 · answered Oct 11 '18 at 17:23

In mathematics, if $a$ and $b$ have the same remainder when divided by $n$, then we say that $a$ and $b$ are congruent modulo $n$. The notation for this is $$a \equiv b \pmod n \tag 1$$

It sounds like you have seen the modulo operator in computer science: a % n produces the remainder after dividing $a$ by $n$. It is important to distinguish this from the notation above; in $(1)$ we are not "taking the mod of both sides", but rather making a statement on the relationship between $a$ and $b$.

You could write $(1)$ in many programming languages like so: (a - b) % n == 0.

score 1 · Answer 2 · answered Oct 11 '18 at 17:24

$a\equiv b \pmod{n}$ is defined to mean that $a-b$ is an integer multiple of $n$. It is a standard exercise in elementary-set-theory to prove that this is an equivalence relation and satisfies the following nice properties:

$a\equiv b\pmod{n}\implies a+c\equiv b+c\pmod{n}$

$a\equiv b\pmod{n}\implies a\times c \equiv b\times c\pmod{n}$

These essentially imply that we can manipulate these equivalencies just like we could do so ordinarily for equations like we are used to.

This is related to the computer science meaning of mod, one has $a\equiv b\pmod{n}$ iff $a\%n = b\%n$

$11x-7\equiv 0\pmod{13}$

$11x \equiv 7\pmod{13}$

$11x \times 11^{-1} \equiv 7\times 11^{-1}\pmod{13}$

$x \equiv 7\times 11^{-1}\pmod{13}$

Now, we need to figure out what $11^{-1}$ is. This can be done from inspection or you can use the extended euclidean division algorithm. Here I'll just do it by inspection., $11$ is the same as $-2$ and $-2\times -7 \equiv 14\equiv 1\pmod{13}$ so $11^{-1}\equiv -7\equiv 6\pmod{13}$

So, $x\equiv 7\times 6\equiv 42\equiv 3\pmod{13}$

Cart's before the horse: you used the inverse before you proved it exists. — Bill Dubuque, Oct 11 '18 at 17:28
It is a common exercise to prove that every number has a multiplicative inverse other than those equivalent to zero when considering it modulo a prime so it should be relatively common knowledge that $11^{-1}$ exists. Further, you could just move that $11\times 6 \equiv 1\pmod{13}$ earlier in the proof to show the same thing. I arranged it as I did for readability. — JMoravitz, Oct 11 '18 at 17:56
You should be writing that above in your answer, not to me in a comment. Given that the OP doesn't know mod notation, it is not likely they know that. — Bill Dubuque, Oct 11 '18 at 18:30

11x - 7 = 0 (mod 13), What is this?

2 Answers2