Having trouble understanding a property of modular congruence

Question

I am given that $$a \equiv 11 \pmod {19}$$ and $$ c \equiv 13a \pmod {19}$$ and I am asked to solve for a $c$ that is between $0$ and $18$ inclusive.

From looking at problems online, it seems that the easiest way to do this is as follows:

$$ c \equiv 13(11) \pmod {19}$$ $$ c \equiv 143 \pmod {19}$$ $$ 143 = 19(7) + 10$$ therefore $$ c = 10$$ because $$ 19 \mid (143-10). $$

So I have two questions: how is it possible to substitute $11$ as $a$, as my book does not prove this nor mention it and I have a very hard time with proving things myself?

And is that last step (solving for $c$) a trial and error approach, as it seems to be that way?

Answer 1

Why does your book proceed this way? That's because congruences, like equalities, are compatible with addition and multiplication, i.e. $$a\equiv a',\quad b\equiv b'\pmod n\implies\begin{cases} a+b\equiv a'+b',\\ab\equiv a'b'\pmod n \end{cases}$$ As to the explicit value of $c$, it is not at all obtaind by trial and error, but by a plain old euclidean division of $143$ by $19$.

Answer 2

Modulo arithmetic is nothing more or less than doing arrithmetics on remainders.

And if $a$ and $11$ have the same remainder, then it must true that $13a$ will have the same remainder as $13*11$.

And $143$ must have some remainder when divided by $19$. What is it?

...........

A fundamental aspect of modulo classes is that the relationship, ($a \equiv b \mod n \iff $n|a-b$ \iff a = b + kn$ for some integer $k\iff a$ and $b$ have the same remainder when divided by $n$) is an equivalence relationship.

In essence this means if $a\equiv b \mod n$ then $a$ and $b$ are interchangeable in terms of modulo arithmetic.

This can be proven by if $a \equiv \alpha \mod n$ and $b \equiv \beta \mod n$ then $a*b = (\alpha + kn)(\beta + jn) = \alpha*\beta + n(k\beta + j\alpha + jkn)$ and $a + b = (\alpha + \beta) + n(j+k)$. So $ab \equiv \alpha\beta\mod n$ and $a+b \equiv \alpha + \beta \mod n$.

So if $a \equiv 11 \mod 19$ then and $f(a) \equiv f(11) \mod 19$ so long as $f$ is a combination of addition and multiplication.

So $c \equiv 13a\equiv 13*11 \mod 19$ because $a \equiv 11 \mod 19$.

And as for $13*11 = 143 \equiv 10 \mod 19$ being trial and error... well, yes, and no. $a\div n = b$ with $r$ remainder means we can find a $b$ and $r$ so that $a = b*n + r$ and $0 \le r < n$. That's basic division from the third grade.

So $143\div 19 = 7\frac {10}{19}$. So $143 = 7*19 + 10$. So $143 \equiv 10 \mod 19$.

.....

Answer 3

$a\equiv 11\pmod{19}$ means that $19\, |\, (a-11)$.
Note that it implies $19\, |\, (a-11)13\, =13a-11\cdot13$, which translates back to $13a\equiv 11\cdot13$.

In addition, $11\cdot13= 147$ gives remainder $10$ when dividing by $19$, so we will have $c= 13a\equiv147\equiv10\pmod{19}$.

Also note that sometimes calculating by negative values can yield shorter calculations. In your case $11\equiv -8$ and $13\equiv -6$, so they can be exchanged $\pmod{19}$, use the above argument (if not convinced yet), and they of course give the same result: $(-8)\cdot(-6)=48=2\cdot19+10\equiv 10\pmod{19}$.