congruence

Fix an integer \( m \) called the modulus, then say \( a \equiv b \left ( \operatorname{mod} m \right ) \) if and only if \( m | b - a \)

congruence iff same remainder

\( a , b \in \mathbb{Z} \) are congruent modulo \( m \) if and only if \( a \% m \) \( = b \% m \)

note: this means that \( a \) and \( b \) have the same remainder upon division by \( m \)

Suppose that \( a \equiv b \left ( \operatorname{mod} m \right ) \), so we know \( m | b - a \), then we can write \( b = k_{b} m + r_{b} \) and \( a = k_{a} m + r_{a} \) so that \( b - a = m \cdot \left ( k_{b} + k_{a} \right ) + k_{b} - k_{a} \) thus \( m | k_{b} - k_{a} \).

Notice that \( 0 \le k_{a} , k_{b} \lt \left | m \right | \) also we know that \( k_{a} \ne k_{b} \) therefore \( k_{b} - k_{a} \ne 0 \) so then \( - \left | m \right | \lt k_{b} - k_{a} \lt \left | m \right | \)