# Trouble learning how to manipulate congruences

• Jun 6th 2010, 02:55 PM
jamesgregory
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,
• Jun 6th 2010, 03:49 PM
jamesgregory
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).
• Jun 6th 2010, 04:05 PM
Bacterius
$\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.
• Jun 6th 2010, 04:22 PM
jamesgregory
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.
• Jun 6th 2010, 04:51 PM
Bacterius
Ah, I see. Are you allowed to substract $\displaystyle a$ from both sides ?
• Jun 6th 2010, 05:11 PM
jamesgregory
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.
• Jun 6th 2010, 05:21 PM
Bacterius
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 ?
• Jun 6th 2010, 05:34 PM
jamesgregory
Thanks! I knew it had to be something staring me in the face!