Do we not have to follow Euclidean division strictly when doing modulo operations?

Question

Referring to this earlier question of mine, and in particular, the answer of Yiyuan Lee, we have that $(p-1)\equiv -1 \pmod p$, since we have that $(p - 1) : p = 1$ with a remainder of $-1$. However, $(p-1) \equiv(p - 1) \pmod p$ is an equivalent statement, since $(p-1):p = 0$ with a remainder of $p-1$. Consider $8 \pmod {16}$. Of course, $8 \pmod{16} \equiv 8$, since $8:16 = 0$ with a remainder of $8$. However, is $8 \pmod {16} \equiv -8$ an equivalent statement, since $8:16 = 1$ with a remainder of $-8$?

Answer 1

Indeed. $8 \equiv -8 \pmod {16}$ is also valid, as well as $8=8 \pmod{16}$

Adding these two yields $8+8 \equiv 0\pmod {16}$ which is certainly true.

In general $$a\equiv b \pmod c \iff (a-b)= nc \text{ where $n\in \Bbb Z$}$$

Answer 2

When performing modular arithmetic you need not limit yourself to working only with remainders (= least representative $\ge 0\,$ of the class of all congruent integers). For example, in order to compute, mod $\,n,\,$ the power $\,(n-1)^{2k}\,$ it is simplest to note $\,n\equiv 0\,\Rightarrow\,\color{#c00}{n\!-\!1\equiv -1}\,$ therefore $\,(\color{#c00}{n\!-\!1})^{2k}\equiv (\color{#c00}{-1})^{2k}\equiv 1,\,$ where we have used the Congruence Power Rule below. Generally it is more convenient to work with congruences, reducing to normal form $\in [0,n\!-\!1]$ only when need be, e.g. at the end of a calculation. Below are common congruence arithmetic rules.

---

Congruence Sum Rule $\rm\qquad\quad A\equiv a,\quad B\equiv b\ \Rightarrow\ \color{#c0f}{A+B\,\equiv\, a+b}\ \ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a) + (B\!-\!b)\ =\ \color{#c0f}{A+B - (a+b)} $

Congruence Product Rule $\rm\quad\ A\equiv a,\ \ and \ \ B\equiv b\ \Rightarrow\ \color{blue}{AB\equiv ab}\ \ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a)\ B + a\ (B\!-\!b)\ =\ \color{blue}{AB - ab} $

Congruence Power Rule $\rm\qquad \color{}{A\equiv a}\ \Rightarrow\ \color{#c00}{A^n\equiv a^n}\ \ (mod\ m)$

Proof $\ $ It is true for $\rm\,n=1\,$ and $\rm\,A\equiv a,\ A^n\equiv a^n \Rightarrow\, \color{#c00}{A^{n+1}\equiv a^{n+1}},\,$ by the Product Rule, so the result follows by induction on $\,n.$

Polynomial Congruence Rule $\ $ If $\,f(x)\,$ is polynomial with integer coefficients then $\ A\equiv a\ \Rightarrow\ f(A)\equiv f(a)\,\pmod m.$

Proof $\ $ By induction on $\, n = $ degree $f.\,$ Clear if $\, n = 0.\,$ Else $\,f(x) = f(0) + x\,g(x)\,$ for $\,g(x)\,$ a polynomial with integer coefficients of degree $< n.\,$ By induction $\,g(A)\equiv g(a)\,$ so $\, A g(A)\equiv a g(a)\,$ by the Product Rule. Hence $\,f(A) = f(0)+Ag(A)\equiv f(0)+ag(a) = f(a)\,$ by the Sum Rule.

Beware $ $ that such rules need not hold true for other operations, e.g. the exponential analog of above $\rm A^B\equiv a^b$ is not generally true (unless $\rm B = b,\,$ so it reduces to the Power Rule, so follows by inductively applying $\,\rm b\,$ times the Product Rule).