「余り」がらみの問題では合同式が使えると見通しよく解けることが少なくありません。が，合同式を未習の生徒は非常に多い。そんなとき，簡単のため「まあ要は余りが等しいもの同士を\(\equiv\)で結ぶんだよ～」とざっくり紹介していますが厳密には違います。合同式の定義は
\[a\equiv b \pmod{p} \overset{\text{def}}{\Longleftrightarrow} \exists k\in\mathbb{Z}[a-b=pk]\]
です。なので
\[\exists k\in\mathbb{Z}[a-b=pk] \Longleftrightarrow \text{\(a\)を\(p\)で割った余りと\(b\)を\(p\)で割った余りが等しい}\]
を証明する必要があります。
証明
\(\Leftarrow\)は明らかであるから，\(\Rightarrow\)を示す．
\[a=pq_1+r_1,~b=pq_2+r_2\quad (0\leq r_1,r_2< p)\]とおくと，仮定により\((pq_1+r_1)-(pq_2+r_2)=pk~(k\in \mathbb{Z})\)と表せる．
\begin{align*}
&(pq_1+r_1)-(pq_2+r_2)=pk\Longleftrightarrow~p(q_1-q_2-k)=r_2-r_1
\end{align*}したがって\(r_2-r_1\)は\(p\)の倍数．ここで\(0\leq r_1,r_2< p\)より\(-p < r_1-r_2 < p\)であるから，\[r_2-r_1=0\]すなわち\(r_1=r_2\)．
証明終
まあ，同値ですから「余りが等しい」ことを「定義」とするという立場をとってもいいのかも知れませんが。。