Integer Modulo n
when divides ; the residues form , a circular loop of .
Definition 4.16 (Integer Modulo )
Let be a natural number. Then the integer modulo , denoted or , is the set of integers with two integers regarded as the same if they differ by a multiple of . More precisely, we say that are congruent modulo , written , if .
Arithmetic
Congruence is compatible with addition and multiplication: if and , then divides , so
and similarly divides , giving
Example
Does have a solution with ? If there is a solution, then reducing modulo gives . But squares are only or modulo , so can only be or modulo , never . Thus there are no integer solutions.
Solving when the gcd exceeds one
Let . The congruence has no solution if : any solution satisfies divides , so divides , and since we must have .
If , write , , and . Then
Note that , so by the unit criterion the reduced congruence has a unique solution modulo .
Related
Stated in
- Definition 4.16 (Integer Modulo )§4.4 Modular Arithmetic