# Thread: Trouble learning how to manipulate congruences

1. ## Trouble learning how to manipulate congruences

I am having some trouble learning how to manipulate congruences, and have two questions on things I don't understand:

1. I understand that the following:

$\displaystyle a +_n (b +_n c) \equiv a + (b +_n c) \pmod{n}$

comes directly from the definition of the rule for $\displaystyle +_n$
But why is the following also true?:

$\displaystyle a + (b +_n c) \equiv a + (b + c) \pmod{n}$

2. Why is the following true?

$\displaystyle 3^{18*3+1} \equiv (3^{18})^3 * 3 \pmod{19}$

Thanks,

2. OK, I've just realised (2) has nothing to do with congruences and just comes from manipulation of powers. I still don't get (1).

3. $\displaystyle a + (b +_n c) \equiv a + (b + c) \pmod{n}$

Remember this is just addition so you don't need those brackets :

$\displaystyle a + b +_n c \equiv a + b + c \pmod{n}$

By simplifying :

$\displaystyle _n c \equiv c \pmod{n}$

Which must be true.

~~~~

Basically, in a congruence you can do about everything except using logarithms, you need care when working with square roots, and to divide you must multiply by the inverse modulo n. Here are the formulae :

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

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

$\displaystyle a \equiv b \pmod{n} \ \implies \ a^c \equiv b^c \pmod{n}$

$\displaystyle \frac{a}{b} \equiv a \times b^{-1} \pmod{n}$ if and only if $\displaystyle \gcd{(b, n)} = 1$.

This is about everything to begin. You'll see that we can also simplify powers using various powerful tools.

4. I should have said this originally, but the result I am having trouble with comes from a proof in a textbook of why $\displaystyle +_n$ is associative, so I can't just remove the brackets on the basis of $\displaystyle +_n$ being associative.

5. Ah, I see. Are you allowed to substract $\displaystyle a$ from both sides ?

6. Yes, you can subtract a congruent number from both sides, or add a congruent number to both sides, or multiply both sides by a congruent number, or raise both sides to a power.

7. Well then you could just substract $\displaystyle a$ from both sides, and then the brackets could be removed because they would be clearly useless regardless of whether you proved the associativity theorem. What do you think ?

8. Thanks! I knew it had to be something staring me in the face!