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

Question

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

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?

Answer 1

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.

Answer 2

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