# Operations on Congruences

What operations can I perform on congruences to transform the modulo n? Specifically, in a formula such as Fermat's Little Theorem (or a generalization) $b^{p-1}$ $\equiv$ $1$ mod $p$

1. What operations can one perform on the mod $p$ part?
2. How could I manipulate this congruence: $7^{24}$ $\equiv$ $1$ mod $25$ to have a mod $10$?
-
Could you write a few sentences explaining? I cannot answer my questions from reading that article. –  CodeKingPlusPlus Sep 17 '12 at 1:43

You ask three questions. Only the third is sufficiently focussed to admit an answer. If $a\equiv b\pmod{cd}$, then $a\equiv b\pmod{c}$. It follows then from $7^{24}\equiv1\pmod{25}$, that $7^{24}\equiv1\pmod{5}$.

Moreover, $7\equiv1\pmod2$, so $7^{24}\equiv1^{24}\equiv1\pmod2$.

So $7^{24}-1$ is a multiple of both 5 and 2, thus of 10, so $7^{24}\equiv1\pmod{10}$.

-

$a\equiv b \bmod c$ means that $a = b+nc$ for some integer $n$.

So the operations that you can do in modular arithmetic are all really consequences of operations you can do to the equality.

For example, can I add $1$ to both sides of a congruence? The answer is yes because we may add $1$ to both sides of the equality $a=b+nc$ and get $a+1 = (b+1)+nc$ ... which, in congruence notation, means $a+1 \equiv b+1 \bmod c$.

Can I multiply both sides of a congruence by $3$? The answer is yes because we may multiply both sides of the equality $a=b+nc$ by $3$ and get $3a = 3b+3nc = 3b + mc$ (where $m = 3n$ is just some other integer).

In congruence notation this means $3a \equiv 3b \bmod c$, or it could even mean $3a \equiv 3b \bmod 3c$. So when it comes to multiplication we really have two types, one effecting the modulus and one not.

The main problem occurs with division in modular arithmetic since division usually leads to fractions and modular arithmetic is something about integers only. You might like to investigate when you can "cancel" things. For example can I cancel by $3$ in $3a \equiv 3b \bmod 3c$ to get $a\equiv b \bmod c$? How about in $3a\equiv 3b \bmod c$? Does it matter what $c$ is?

-