Given that a and b are integers, a ≡ 4 (mod 13), and b ≡ 9 (mod 13). Find c where c ≡ 9a (mod 13).

Question

The Problem

I had my first exposure to number theory today. Trying to work on some problems in hope that it will start to make more sense. Here is the problem (part a) I'm stuck on right now.

---

My Work

We know from the first congruence that $\frac{a-4}{13} = d $ where $d\in\mathbb{Z}$ and $\frac{b-9}{13} = e$ where $d\in\mathbb{Z}$. We also know $a = 4 + 13k$ where $k\in\mathbb{Z}$ and $b = 9+13j$ where $j\in\mathbb{Z}$. $\frac{c-9a}{13} =$ an integer.

My Question

I've derived what I can from what I was given. How can I use this information to help figure out this $c$? What is a good strategy for the rest of the questions?

Answer 1

We want to find $c \equiv 9a$ (mod $13$). But since $a \equiv 4$ (mod $13$), then we know $9a \equiv 9 \cdot 4$ (mod $13$) (do you understand why?).

But $9 \cdot 4 = 36 \equiv 10$ (mod $13$). And since $c$ should be an integer between $1$ and $12$ such that $c \equiv 9a = 36$ (mod $13$), and $36$ (mod $13$) is equivalent to $10$ (mod $13$), then $c$ must be $10$.

---

EDIT: I think the whole point of the problem is for you to know that if $a \equiv b$ (mod $x$), and $c \equiv d$ (mod $x$), then $ac \equiv bd$ (mod $x$). You should be able to prove this, and then once you understand it, you can use it freely to solve problems like this. This property is essentially saying that if you have two things that are equivalent (mod $x$), and two other things that are equivalent (mod $x$), then it doesn't matter which representative you choose from the first two things and the second two things. When you multiply the representatives together, you get the same result. This means the operation of multiplying elements of different equivalence classes is well-defined. Does this make sense?

Answer 2

We know $\color{red}{a}\equiv \color{red}{4}\pmod{13}$. We want to find an expression for $c$. Thus: \begin{align} c&\equiv 9\color{red}{a}\pmod{13}\\ &\equiv 9(\color{red}{4})\pmod{13}\\ &\equiv 36 \pmod{13}\\ &\equiv 10\pmod{13} \end{align}

Just like with normal equations, you can substitute values in congruences.

Answer 3

If you have only just started today you should probably leave the question for a couple of days until you have learned the necessary facts.

Just to give you a brief introduction: you can add, subtract and multiply congruences in the same way you can ordinary equations. (But note, this does not apply to dividing or cancelling.) So the first problem can be done this way: $$\eqalign{a\equiv4\mod{13}\quad &\Rightarrow\quad 9a\equiv9\times4\mod{13}\cr &\Rightarrow\quad c\equiv36\mod{13}\cr &\Rightarrow\quad c\equiv10\mod{13}\ .\cr}$$ The last implication is true because $36=2\times13+10$.