See end of Sep22 notes for first part of this lecture, on primes and unique
factorization. 

Quotient-Remainder Theorem:  Let n be any integer, and let d be a non-zero
integer.  Then there are unique integers q and r such that
n = qd+r where 0<=r<d.  (r is the remainder when n is divided by d.)

Definition:  If n and m are integers and if d is a non-zero integer
such that n and m have the same remainders when divided by d, then we
say m and n are equivalent modulo d.  This can also be said as
follows: d|(m-n).

Example: 5 and 8 are equivalent mod 3 (each has remainder 2). Note
that 8-5=3, so 3|(8-5). Another way to say this is that both  and 8
are elements of the set 2+3Z: each is 2 more than a multiple of 3.

This notion of modular equivalence provides a natural classification
of integers.  For each non-zero integer d, the integers Z separate
into d types: 

  - those with no remainder upon division by d (these are
simply the elements of dZ, the multiples of d)
  - those with remainder of 1 (elements of 1+dZ)
  ...
  - those with remainder of d-1 (elements of d-1+dZ)

Examples: 
For d=2, the two classes are the evens (2Z) and odds (1+2Z)
For d=3, they are 3Z, 1+3Z, and 2+3Z.

In a picture (where d=3):

...-4..-3..-2..-1...0...1...2...3...4...5...6...7...8...9...10...
    C   A   B   C   A   B   C   A   B   C   A   B   C   A   B

Above, numbers equiv to 0 mod 3 are indicated with the letter A, those
equiv 1 mod 3 by B, and the rest (equiv 2 mod 3) by C.