We say that \(a \equiv b \pmod{n},\) which is read as “\(a\) is congruent to \(b\) modulo \(n,”\) and is sometimes written more tersely as \(a \equiv_n b,\) if there exists some integer \(k\) such that \(a -b = kn.\) We say that \(a\) is divisible by \(n\) if \(a \equiv 0 \pmod{n}.\) For example \[ 7 \equiv 2 \pmod{5} \qquad\qquad 39 \equiv 4 \pmod{7} \qquad\qquad 8675309 \equiv 1 \pmod{2} \]
When asked about the unit’s digit (right-most digit) of an integer \(a,\) you’re being asked to consider \(a \pmod{10}.\)
Working modulo \(n,\) every integer will be congruent to one of the integers \(\{0, 1, \dotsc, n\!-\!1\};\) this is called its congruence class modulo \(n.\)
Whereas powers of a positive integer will become progressively larger, considered modulo \(n\) they will eventually cycle back to \(1,\) which can help us determine congruences of large integers. For example, working modulo \(7,\) \[ 2 \equiv 2, \qquad 2^2 \equiv 4, \qquad 2^3 \equiv 1, \qquad \text{ so }\, 2^{1234} = 2\bigl(2^3\bigl)^{411} \equiv 2(1)^{411} \equiv 2 \pmod{7} \]
Rather than thinking about modular arithmetic as some special arithmetic within the integers \(\mathbf{Z},\) it is helpful to think of it as the typical arithmetic on a different set of numbers. To say we are “working modulo \(n”\) is to say we are doing arithmetic in the set of numbers \({\mathbf{Z}/n\mathbf{Z} = \{0, 1, \dotsc, n\!-\!1\}};\) the “modular” arithmetic in \(\mathbf{Z}/n\mathbf{Z}\) is just the image of typical arithmetic in \(\mathbf{Z}\) via the quotient map \(\mathbf{Z} \twoheadrightarrow \mathbf{Z}/n\mathbf{Z}.\) Any fact in \(\mathbf{Z}\) must descend to a fact in \(\mathbf{Z}/n\mathbf{Z}\) for any \(n.\) Contrapositively, if a claim made in \(\mathbf{Z}\) is found to be false in when considered in \(\mathbf{Z}/n\mathbf{Z}\) for some \(n,\) then it is also false in \(\mathbf{Z}.\)