Modulus number theory (basic)

Question

I'm having some trouble understanding Modulus.

Suppose that a and b are integers, a ≡ 4 (mod 13) and b ≡ 9 (mod 13). Find the integer c with 0 ≤ c ≤ 12 such that

a) c ≡ 9a (mod 13)

b) c ≡ 11b (mod 13)

c) c ≡ a + b (mod 13)

d) c ≡ 2a +3b (mod 13)

e) c ≡a^2+b^2 (mod 13)

The book has the answers listed as

a)10

b)8

c)0

d)9

e)6

This is one of the even questions in the book, we have the odd questions in the book. This book is terrible at explaining the process, how did they get these values? I have no idea how to do this. How do you even find a and b?

Answer 1

You need to understand the basics of modulus

Let $m>1$ be fixed and $a,b,c,d \in \mathbb{Z}$. Then the following hold:

1. $a \equiv b \pmod{m}$ if and only if the remainders (non-negative) when $a$ and $b$ are divided by $m$ are the same.
2. $a \equiv a \pmod{m}$ (reflexive)
3. If $a \equiv b \pmod{m}$, then $b \equiv a \pmod{m}$ (symmetric)
4. If $a \equiv b \pmod{m}$ and $b \equiv c \pmod{m}$, then $a \equiv c \pmod{m}$ (transitive)
5. If $a \equiv b \pmod{m}$, then $ac \equiv bc \pmod{m}$
6. If $a \equiv b \pmod{m}$, then $a \pm c \equiv b \pm c \pmod{m}$
7. If $a \equiv b \pmod{m}$, then $a^n \equiv b^n \pmod{m}$ for any positive integer $n$
8. If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then $a+c \equiv b+d \pmod{m}$ (congruences with same modulus can be added)
9. If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then $ac \equiv bd \pmod{m}$ (congruences with same modulus can be multiplied)

For example to do part (a):

$c \equiv 9a \pmod{13}$ we can use properties from above to conclude $$c \equiv 9a \equiv 9(4) \equiv 36 \equiv 10 \pmod{13}.$$ Note that the last step comes from the fact that the remainder when $36$ is divided by $13$ is $10$ (hence equivalent to $36$ in mod $13$).

Now you may be able to take care of the remaining questions.

Answer 2

We already know that $a \equiv 4 \pmod{13}$ and $b \equiv 9 \pmod{13}$. Now just apply the following facts repeatedly:

Suppose $x_1 \equiv y_1 \pmod{n}$ and $x_2 \equiv y_2 \pmod{n}$. Then the following are true:

$$x_1x_2 \equiv y_1y_2 \pmod{n}$$ $$x_1 + x_2 \equiv y_1 + y_2 \pmod{n}$$

---

Now as far as the notation itself, we say $x \equiv y \pmod{n} \iff n|(x-y)$. It is possible to prove the helpful facts above using only this definition.

Answer 3

For example to do part (e):

$c \equiv a^2 + b^2 \pmod{13}$

$\Rightarrow c \equiv (16 \pmod{13}) + (81 \pmod{13}) \pmod{13}$

$\Rightarrow c \equiv (3 + 3) \pmod{13}$

$\Rightarrow c \equiv 6 \pmod{13}$

The required answer is $6$.

Answer 4

$a$ and $b$ are any integers satisfying those congruences. For example, you could have $a=4$, $a=17$, or $a=-9$; those all satisfy $a\equiv 4\pmod{13}$.

Now, looking at part (a), for example, if $a\equiv 4\pmod{13}$, that means that $a$ leaves a remainder of $4$ when divided by $13$. So $9a$ leaves a remainder of $9\cdot 4 = 36$ when divided by $13$ (make sure this is crystal clear to you). But a remainder of $36$ is the same as a remainder of $36 - 2\cdot 13 = 10$ when divided by $13$.

The other parts are similar.