Can you substitute congruences into an expression if the conditions are right?

Question

When using a congruences can we substitute them into an expression. For example, when we look at Fermat's little theorem we notice that $a^p$ is congruent to $a\ (\text{mod}\ p)$ when $a$ is an integer and $p$ is prime, so where ever we see $a^p$ where $a$ is an integer and $p$ is prime, can we simply substitute $a\ (\text{mod}\ p)$ for $a^p$?

Answer 1

Yes in general using congruences all algebraic rules hold for for the sum and product and we can substitute them into an expression, notably for

• $A\equiv a \mod p$
• $B\equiv b \mod p$

we have that

• $A+B\equiv a+b \mod p$
• $A\cdot B\equiv a\cdot b \mod p$

Answer 2

No. It would be very bad notation in some cases.

For example, if you replace $a^p$ by $a\pmod p$ in the equation $$a^p\times5=5a^p$$ then you get $$a\pmod p\times5=5a\pmod p$$ so the RHS would be very ambiguous. Do you mean $5a\pmod p$ or $5\times[a\pmod p]$?

Answer 3

So, what about taking the Pythagorean triples as an example. We know for Pythagorean triples $x,y,$ and $z$ are integers in $x^2+y^2=z^2$. By Fermats little theorem, we know

• $a^2\equiv{a\ (\text{mod }2)}$ where $a\in{\mathbb{z}}$

So, $x^2+y^2=z^2$ yields,

• $x+y\equiv{z\ (\text{mod }2)}$